# 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).
3. Let $p\ge 3$ be a prime. Consider the graph $G=(V,E)$ with $V=\{0,1,2,\ldots, (p-1)\}$ and
$$E=\{\{x,y\}:x-y\equiv 2(mod p)\lor x-y\equiv -2 (mod p)\}$$
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,\ldots,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,\ldots,n\}: |S|=k\}$ and
$$E = \{\{S,T\}:|(S-T)\cup (T-S)|=2\}.$$