Math 55 Graph Theory Practice Solutions

1. Prove that every simple graph with
   $n$ vertices and
   $k$ edges has at least
   $n-k$ connected components (hint: induction on
   $k$).

Proof 1. We proceed by induction. Fix

$n\ge 1$ and let

$P(k)$ be the statement that every
simple graph with

$n$ vertices and

$k$ edges has at least

$n-k$ connected
components. We will show that

$P(k)$ is true for all

$k\ge 0$.

Basis Step:

$P(0)$ says that a graph with no edges has at least

$n$ connected components, and this is true since each vertex is its own connected component.

Inductive Step: Assume

$P(k)$ is true. Let

$G$ be a graph with

$n$ vertices and

$k+1$ edges. Let

$e=uv$ be an arbitrary edge of

$G$, and let

$G^{\prime }=G-e$ be the graph obtained by deleting

$e$. Let

$G_1,\dots ,G_{\ell }$ be the connected components of

$G^{\prime }$ and note that

$\ell \ge n-k$ by the inductive hypothesis. Notice that if

$u$ and

$v$ are in the same connected component of

$G^{\prime }$, then adding it does not change the connected
components, so in this case

$G$ also has

$\ell$ connected components.
On the other hand if

$u\in G_i$ and

$v\in G_j$ for some

$i\ne j$
then

$G_i\cup G_j$ is a connected component of

$G$, since there is a path from
every

$x\in G_i$ and

$y\in G_j$ by concatenating a path from

$x$ to

$u$, the
edge

$uv$, and a path from

$v$ to

$y$. The other connected components of

$G^{\prime }$
remain connected components in

$G$. Thus, the number of connected components
decreases by at most one upon adding

$e$, so the number of connected components in

$G$ is at least

$\ell -1=n-k-1=n-(k+1)$, as desired.

Proof 2. By contradiction. Assume

$G$ is a simple graph with

$n$ vertices and

$k$ edges. Assume

$G$ has at most

$n-k-1$ connected components. Let the connected components be

$G_1,\dots ,G_m$, and suppose they have

$n_1,n_2,\dots ,n_m$ vertices, where

$n=n_1+n_2+\dots +n_m$ Each connected component must contain a spanning tree, and these trees have

$n_1-1,n_2-1,\dots ,n_m-1$ edges. Since these sets of edges are disjoint, the total number of edges in

$G$ is at least

$$(n_1-1)+(n_2-1)+\dots (n_m-1)=(n_1+n_2+\dots +n_m)-m$$

$$=n-m\ge n-(n-k-1)=k+1,$$
since

$m\le n-k-1$, which is a 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.
   Solution. (i) Let
   $x,y$ be two vertices of
   $G$. Let
   $m=x-y$. We will show that there is an integer
   $k$ such that
   $m\equiv 2k(modp)$, which will imply that
   $x,x+2,x+4,\dots ,x+2k=y$ is a path in
   $G$ between
   $x$ and
   $y$ if
   $k\ge 0$ and otherwise
   $x,x-2,x-4,\dots ,x+2k$ is a path in
   $G$ between
   $x$ and
   $y$ if
   $k<0$. To see that such a
   $k$ exists, observe that
   $2$ and
   $p$ are relatively prime since
   $p\ge 3$. Thus
   $2$ has an inverse modulo
   $p$, and any
   $k$ satisfying
   $k\equiv 2^{-1}m(modp)$ is sufficient. (ii) Let
   $x\in V$. Observe that
   $xy$ is an edge if
   $x-y\equiv 2(modp)$ or
   $x-y\equiv -2(modp)$. Each of these equations has a unique solution in
   $V$, so the degree of every vertex is
   $2$. By Euler's theorem, this means that
   $G$ has an Eulerian circuit.

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.
   Solution. As stated, this question has a pretty boring answer: notice that for any subset
   $S\subseteq [n]$ of size
   $k$ and any other subset
   $T\ne S$, we must have
   $|(S-T)\cup (T-S)|\ge 2$ since
   $S$ must contain an element not in
   $T$ and
   $T$ must contain an element not in
   $S$ (as they are the same size). Thus, the edge set of this graph is empty, and the graph is simply the empty graph. The degrees are zero. The graph is not connected. The graph does not have an Eulerian circuit for any value of
   $k$. The graph is
   $2-$colorable for every value of
   $k$.

4. A much more interesting version of the previous question is to consider the graph with edges
   

   $$E=\{\{S,T\}:|(S-T)\cup (T-S)|=2\}.$$

Solution. In this case: the degrees are

$k(n-k)$ since for any vertex

$S$ there are

$k$ choices of elements of

$S$ to delete and

$(n-k)$ choices of vertices outside

$S$ to replace it with to obtain a neighbor

$T$. The graph is connected for all

$k\le n/2$, since we can construct a path between any distinct

$S$ and

$T$ by beginning with

$S$ and deleting one element of

$S-T$ and adding one element of

$T-S$ at a time (corresponding to traversing a single edge). The graph has an Eulerian circuit iff the degree

$k(n-k)$ is even.

To determine whether the graph is

$2-$colorable, we will determine whether it has an odd circuit. It turns out that if

$n\ge 3$ then this graph always contains a triangle: if

$k=1$ the vertices

$\{1\},\{2\},\{3\}$ form a triangle, and if

$k>1$ then by choosing any set

$A$ satisfying

$|A|=k-1$ and

$A\cap \{1,2,3\}=\mathrm{\varnothing }$ we obtain a triangle

$\{1\}\cup A,\{2\}\cup A,\{3\}\cup A$ (such a set

$A$ exists since

$n\ge 2k\ge (k-1)+3$ when

$k\ge 2$). Thus, when

$n\ge 3$ the graph is not

$2-$colorable since it contains an odd circuit. The only remaining possibility is that

$n=2$, in which case

$k=1$ and the graph consists of a single edge, which is

$2-$colorable.