Math 55 Graph Theory Practice Questions

1. Prove that every simple graph with

   $n$ vertices and
   $k$ edges has at least
   $n-k$ connected components (hint: induction, or contradiction).

2. Let

   $p\ge 3$ be a prime. Consider the graph
   $G=(V,E)$ with
   $V=\{0,1,2,\dots ,(p-1)\}$ and
   
   $$E=\{\{x,y\}:x-y\equiv 2(modp)\vee x-y\equiv -2(modp)\}$$
   Show that
   $G$ is connected. Does
   $G$ have an Euler circuit? Prove your answer.

3. Let

   $n\ge 1$ be an integer and let
   $k\le n/2$. Consider the graph
   $G=(V,E)$ with
   $V=\{S\subseteq \{1,2,\dots ,n\}:|S|=k\}$ and
   
   $$E=\{\{S,T\}:|(S-T)\cup (T-S)|=1\}.$$
   What are the degrees of the vertices in
   $G$? Is
   $G$ connected? For which values of
   $n$ and
   $k$ does
   $G$ have an Eulerian circuit? For which values of
   $n$ and
   $k$ is
   $G$
   $2-$colorable? Prove your answers.

4. Do #3 but with the graph defined by

   $V=\{S\subseteq \{1,2,\dots ,n\}:|S|=k\}$ and
   
   $$E=\{\{S,T\}:|(S-T)\cup (T-S)|=2\}.$$