5.E: Graph Theory (Exercises)

5.1: The Basics

Exercise $\PageIndex{1.1}$

The complement $\overline G$ of the simple graph $G$ is a simple graph with the same vertices as $G$, and $\{v,w\}$ is an edge of $\overline G$ if and only if it is not an edge of $G$. A graph $G$ is self-complementary if $G\cong \overline G$. Show that if $G$ is self-complementary then it has $4k$ or $4k+1$ vertices for some $k$. Find self-complementary graphs on 4 and 5 vertices.

Exercise $\PageIndex{1.2}$

Prove that if $\sum_{i=1}^n d_i$ is even, there is a graph (not necessarily simple) with degree sequence $d_1,d_2,\ldots,d_n$.

Exercise $\PageIndex{1.3}$

Suppose $d_1\ge d_2\ge\cdots\ge d_n$ and $\sum_{i=1}^n d_i$ is even. Prove that there is a multigraph with degree sequence $d_1,d_2,\ldots,d_n$ if and only if $d_1\le \sum_{i=2}^n d_i$.

Exercise $\PageIndex{1.4}$

Prove that $0,1,2,3,4$ is not graphical.

Exercise $\PageIndex{1.5}$

Is $4,4,3,2,2,1,1$ graphical? If not, explain why; if so, find a simple graph with this degree sequence.

Exercise $\PageIndex{1.6}$

Is $4,4,4,2,2$ graphical? If not, explain why, and find a graph with this degree sequence; if so, find a simple graph with this degree sequence.

Exercise $\PageIndex{1.7}$

Prove that a simple graph with $n\ge 2$ vertices has two vertices of the same degree.

Exercise $\PageIndex{1.8}$

Prove the "only if'' part of Theorem 5.1.2.

Exercise $\PageIndex{1.9}$

Show that the condition on the degrees in Theorem 5.1.2 is equivalent to this condition: $\sum_{i=1}^n d_i$ is even and for all $k\in \{1,2,\ldots,n\}$, and all $\{i_1,i_2,\ldots, i_k\}\subseteq [n]$, $$\sum_{j=1}^k d_{i_j}\le k(k-1)+ \sum_{i\notin \{i_1,i_2,\ldots, i_k\}} \min(d_i,k).\nonumber$$ Do not use Theorem 5.1.2.

Exercise $\PageIndex{1.10}$

Draw the 11 non-isomorphic graphs with four vertices.

Exercise $\PageIndex{1.11}$

Suppose $G_1\cong G_2$. Show that if $G_1$ contains a cycle of length $k$ so does $G_2$.

Exercise $\PageIndex{1.12}$

Define $v\sim w$ if and only if there is a path connecting vertices $v$ and $w$. Prove that $\sim$ is an equivalence relation.

Exercise $\PageIndex{1.13}$

Prove the "if'' part of Theorem 5.1.2, as follows:

The proof is by induction on $s=\sum_{i=1}^n d_i$. This is easy to see if $s=2$, so suppose $s>2$. Without loss of generality we may suppose that $d_n>0$. Let $t$ be the least integer such that $d_t>d_{t+1}$, or $t=n-1$ if there is no such integer. Let $d_t'=d_t-1$, $d_n'=d_n-1$, and $d_i'=d_i$ for all other $i$. Note that $d_1'\ge d_2'\ge\cdots d_n'$. We want to show that the sequence $\{d_i'\}$ satisfies the condition of the theorem, that is, that for all $k\in \{1,2,\ldots,n\}$, $$\sum_{i=1}^k d_i'\le k(k-1)+\sum_{i=k+1}^n \min(d_i',k).\nonumber$$ There are five cases:

1. $k\ge t$
2. $k< t$, $d_k< k$
3. $k< t$, $d_k=k$
4. $k< t$, $d_n>k$
5. $k< t$, $d_k > k$, $d_n\le k$

By the induction hypothesis, there is a simple graph with degree sequence $\{d_i'\}$. Finally, show that there is a graph with degree sequence $\{d_i\}$.

This proof is due to S. A. Choudum, A Simple Proof of the Erdős-Gallai Theorem on Graph Sequences, Bulletin of the Australian Mathematics Society, vol. 33, 1986, pp. 67-70. The proof by Paul Erdős and Tibor Gallai was long; Berge provided a shorter proof that used results in the theory of network flows. Choudum's proof is both short and elementary.

5.2: Euler Circuits and Walks

Exercise $\PageIndex{2.1}$

Suppose a connected graph $G$ has degree sequence $d_1,d_2,\ldots,d_n$. How many edges must be added to $G$ so that the resulting graph has an Euler circuit? Explain.

Exercise $\PageIndex{2.2}$

Which complete graphs $K_n$, $n\ge 2$, have Euler circuits? Which have Euler walks? Justify your answers.

Exercise $\PageIndex{2.3}$

Prove that if vertices $v$ and $w$ are joined by a walk they are joined by a path.

Exercise $\PageIndex{2.4}$

Show that if $G$ is connected and has exactly $2k$ vertices of odd degree, $k\ge1$, its edges can be partitioned into $k$ walks. Is this true for non-connected $G$?

5.3: Hamilton Cycles and Paths

Exercise $\PageIndex{3.1}$

Suppose a simple graph $G$ on $n$ vertices has at least ${(n-1)(n-2)\over2}+2$ edges. Prove that $G$ has a Hamilton cycle. For $n\ge 2$, show that there is a simple graph with ${(n-1)(n-2)\over2}+1$ edges that has no Hamilton cycle.

Exercise $\PageIndex{3.2}$

Prove Theorem 5.3.2.

Exercise $\PageIndex{3.3}$

The graph shown below is the Petersen graph. Does it have a Hamilton cycle? Justify your answer. Does it have a Hamilton path? Justify your answer.

Figure $\PageIndex{1}$

5.4: Bipartite Graphs

Exercise $\PageIndex{4.1}$

Prove that there is a bipartite multigraph with degree sequence $d_1,\ldots,d_n$ if and only if there is a partition $\{I,J\}$ of $[n]$ such that $$\sum_{i\in I}d_i=\sum_{i\in J} d_i.\nonumber$$

Exercise $\PageIndex{4.2}$

What is the smallest number of edges that can be removed from $K_5$ to create a bipartite graph?

Exercise $\PageIndex{4.3}$

A regular graph is one in which the degree of every vertex is the same. Show that if $G$ is a regular bipartite graph, and the common degree of the vertices is at least 1, then the two parts are the same size.

Exercise $\PageIndex{4.4}$

A perfect matching is one in which all vertices of the graph are incident with an edge in the matching. Show that a regular bipartite graph with common degree at least 1 has a perfect matching. (We discussed matchings in Section 4.6.)

5.5: Trees

Exercise $\PageIndex{5.1}$

Suppose that $G$ is a connected graph, and that every spanning tree contains edge $e$. Show that $e$ is a bridge.

Exercise $\PageIndex{5.2}$

Show that every edge in a tree is a bridge.

Exercise $\PageIndex{5.3}$

Show that $G$ is a tree if and only if it has no cycles and adding any new edge creates a graph with exactly one cycle.

Exercise $\PageIndex{5.4}$

Which trees have Euler walks?

Exercise $\PageIndex{5.5}$

Which trees have Hamilton paths?

Exercise $\PageIndex{5.6}$

Let $n\ge 2$. Show that there is a tree with degree sequence $d_1,d_2,\ldots,d_n$ if and only if $d_i>0$ for all $i$ and $\sum_{i=1}^n d_i=2(n-1)$.

Exercise $\PageIndex{5.7}$

A multitree is a multigraph whose condensation is a tree. Let $n\ge 2$. Let $d_1,d_2,\ldots,d_n$ be positive integers, and let $g$ be the greatest common divisor of the $d_i$. Show that there is a multitree with degree sequence $d_1,d_2,\ldots,d_n$ if and only if $\sum_{i=1}^n d_i/g\ge 2(n-1)$ and for some partition $I$, $J$ of $[n]$, $\sum_{i\in I}d_i=\sum_{i\in J} d_i$.

Exercise $\PageIndex{5.8}$

Suppose $T$ is a tree on $n$ vertices, $k$ of which have degree larger than $1,\: d_1,\: d_2,\cdots d_k$. Of course, $T$ must also have pendant vertices. How many pendant vertices? Your answer should depend only on $k$ and $d_1,\: d_2,\cdots d_k$.

5.6: Optimal Spanning Trees

Exercise $\PageIndex{6.1}$

Kruskal's Algorithm is also a greedy algorithm that produces a minimum cost spanning tree for a connected graph $G$. Begin by choosing an edge in $G$ of smallest cost. Assuming that edges $e_1, e_2,\ldots,e_i$ have been chosen, pick an edge $e_{i+1}$ that does not form a cycle together with $e_1, e_2,\ldots,e_i$ and that has smallest cost among all such edges. The edges $e_1, e_2,\ldots,e_{n-1}$ form a spanning tree for $G$. Prove that this spanning tree has minimum cost.

Exercise $\PageIndex{6.2}$

Prove that if the edge costs of $G$ are distinct, there is exactly one minimum cost spanning tree. Give an example of a graph $G$ with more than one minimum cost spanning tree.

Exercise $\PageIndex{6.3}$

In both the Jarník and Kruskal algorithms, it may be that two or more edges can be added at any particular step, and some method is required to choose one over the other. For the graph below, use both algorithms to find a minimum cost spanning tree. Using the labels $e_i$ on the graph, at each stage pick the edge $e_i$ that the algorithm specifies and that has the lowest possible $i$ among all edges available. For the Jarník algorithm, use the designated $v_0$ as the starting vertex. For each algorithm, list the edges in the order in which they are added. The edge weights $e_1,e_2,\ldots,e_{10}$ are $6,7,8,2,3,2,4,6,1,1$.

Figure $\PageIndex{2}$

5.7: Connectivity

Exercise $\PageIndex{7.1}$

Suppose a simple graph $G$ on $n\ge 2$ vertices has at least ${(n-1)(n-2)\over2}+1$ edges. Prove that $G$ is connected.

Exercise $\PageIndex{7.2}$

Suppose a general graph $G$ has exactly two odd-degree vertices, $v$ and $w$. Let $G'$ be the graph created by adding an edge joining $v$ to $w$. Prove that $G'$ is connected if and only if $G$ is connected.

Exercise $\PageIndex{7.3}$

Suppose $G$ is simple with degree sequence $d_1\le d_2\le\cdots\le d_n$, and for $k\le n-d_n-1$, $d_k\ge k$. Show $G$ is connected.

Exercise $\PageIndex{7.4}$

Recall that a graph is $k$-regular if all the vertices have degree $k$. What is the smallest integer $k$ that makes this true:

If $G$ is simple, has $n$ vertices, $m\ge k$, and $G$ is $m$-regular, then $G$ is connected.

(Of course $k$ depends on $n$.)

Exercise $\PageIndex{7.5}$

Suppose $G$ has at least one edge. Show that $G$ is 2-connected if and only if for all vertices $v$ and edges $e$ there is a cycle containing $v$ and $e$.

Exercise $\PageIndex{7.6}$

Find a simple graph with $\kappa(G)< \lambda(G)< \delta(G)$.

Exercise $\PageIndex{7.7}$

Suppose $\lambda(G)=k>0$. Show that there are sets of vertices $U$ and $V$ that partition the vertices of $G$, and such that there are exactly $k$ edges with one endpoint in $U$ and one endpoint in $V$.

Exercise $\PageIndex{7.8}$

Find $\lambda(K_{m,n})$, where both $m$ and $n$ are at least 1.

Exercise $\PageIndex{7.9}$

Suppose $G$ is a connected graph. The block-cutpoint graph of $G$, $BC(G)$ is formed as follows: Let vertices $c_1,c_2,\ldots,c_k$ be the cutpoints of $G$, and let the blocks of $G$ be $B_1,\ldots,B_l$. The vertices of $BC(G)$ are $c_1,…,c_k,B_1,\ldots,B_l$. Add an edge $\{B_i,c_j\}$ if and only if $c_j\in B_i$. Show that the block-cutpoint graph is a tree.

Note that a cutpoint is contained in at least two blocks, so that all pendant vertices of the block-cutpoint graph are blocks. These blocks are called endblocks.

Exercise $\PageIndex{7.10}$

Draw the block-cutpoint graph of the graph below.

Figure $\PageIndex{3}$

Exercise $\PageIndex{7.11}$

Show that the complement of a disconnected graph is connected. Is the complement of a connected graph always disconnected? (The complement $\overline G$ of graph $G$ has the same vertices as $G$, and $\{v,w\}$ is an edge of $\overline G$ if and only if it is not an edge of $G$.)

5.8: Graph Coloring

Exercise $\PageIndex{8.1}$

Suppose $G$ has $n$ vertices and chromatic number $k$. Prove that $G$ has at least $k\choose2$ edges.

Exercise $\PageIndex{8.2}$

Find the chromatic number of the graph below by using the algorithm in this section. Draw all of the graphs $G+e$ and $G/e$ generated by the alorithm in a "tree structure'' with the complete graphs at the bottom, label each complete graph with its chromatic number, then propogate the values up to the original graph.

Figure $\PageIndex{4}$

Exercise $\PageIndex{8.3}$

Show that a graph is bipartite if and only if it can be properly colored with two colors.

Exercise $\PageIndex{8.4}$

Show that $\chi(G-v)$ is either $\chi(G)$ or $\chi(G)-1$.

Exercise $\PageIndex{8.5}$

Prove Theorem 5.8.3 without assuming any particular properties of the order $v_1,\ldots,v_n$.

Exercise $\PageIndex{8.6}$

Prove Theorem 5.8.4 as follows. By Corollary 5.8.1 we need consider only regular graphs. Regular graphs of degree 2 are easy, so we consider only regular graphs of degree at least 3.

If $G$ is not 2-connected, show that the blocks of $G$ may colored with $\Delta(G)$ colors, and then the colorings may be altered slightly so that they combine to give a proper coloring of $G$.

If $G$ is 2-connected, show that there are vertices $u$, $v$, $w$ such that $u$ is adjacent to both $v$ and $w$, $v$ and $w$ are not adjacent, and $G-v-w$ is connected. Given such vertices, color $v$ and $w$ with color 1, then color the remaining vertices by a greedy algorithm similar to that in Theorem 5.8.4, with $u$ playing the role of $v_n$.

To show the existence of $u$, $v$, $w$ as required, let $x$ be a vertex not adjacent to all other vertices. If $G-x$ is 2-connected, let $v=x$, let $w$ be at distance 2 from $v$ (justify this), and let a path of length 2 be $v,u,w$. Use Theorem 5.7.2 to show that $u$, $v$, $w$ have the required properties.

If $G-x$ is not 2-connected, let $u=x$ and let $v$ and $w$ be (carefully chosen) vertices in two different endblocks of $G-x$. Show that $u$, $v$, $w$ have the required properties.

Brooks proved the theorem in 1941; this simpler proof is due to Lovász, 1975.

5.9: The Chromatic Polynomial

Exercise $\PageIndex{9.1}$

Show that the leading coefficient of $P_G$ is 1.

Exercise $\PageIndex{9.2}$

Suppose that $G$ is not connected and has components $C_1,\ldots,C_k$. Show that $P_G=\prod_{i=1}^k P_{C_i}$.

Exercise $\PageIndex{9.3}$

Show that the constant term of $P_G(k)$ is 0. Show that the coefficient of $k$ in $P_G(k)$ is non-zero if and only if $G$ is connected.

Exercise $\PageIndex{9.4}$

Show that the coefficient of $k^{n-1}$ in $P_G$ is $-1$ times the number of edges in $G$.

Exercise $\PageIndex{9.5}$

Show that $G$ is a tree if and only if $P_G(k)=k(k-1)^{n-1}$.

Exercise $\PageIndex{9.6}$

Find the chromatic polynomial of $K_n$ with one edge removed.

5.10: Coloring Planar Graphs

Exercise $\PageIndex{10.1}$

Show $K_{3,3}$ is not planar. (Prove a lemma like Lemma 5.10.1 for bipartite graphs, then do something like the proof of Theorem 5.10.2.) What is the chromatic number of $K_{3,3}$?

5.11: Directed Graphs

Exercise $\PageIndex{11.1}$

Connectivity in digraphs turns out to be a little more complicated than connectivity in graphs. A digraph is connected if the underlying graph is connected. (The underlying graph of a digraph is produced by removing the orientation of the arcs to produce edges, that is, replacing each arc $(v,w)$ by an edge $\{v,w\}$. Even if the digraph is simple, the underlying graph may have multiple edges.) A digraph is strongly connected if for every vertices $v$ and $w$ there is a walk from $v$ to $w$. Give an example of a digraph that is connected but not strongly connected.

Exercise $\PageIndex{11.2}$

A digraph has an Euler circuit if there is a closed walk that uses every arc exactly once. Show that a digraph with no vertices of degree 0 has an Euler circuit if and only if it is connected and $\text{d}^+(v)=\text{d}^-(v)$ for all vertices $v$.

Exercise $\PageIndex{11.3}$

A tournament is an oriented complete graph. That is, it is a digraph on $n$ vertices, containing exactly one of the arcs $(v,w)$ and $(w,v)$ for every pair of vertices. A Hamilton path is a walk that uses every vertex exactly once. Show that every tournament has a Hamilton path.

Exercise $\PageIndex{11.4}$

Interpret a tournament as follows: the vertices are players. If $(v,w)$ is an arc, player $v$ beat $w$. Say that $v$ is a champion if for every other player $w$, either $v$ beat $w$ or $v$ beat a player who beat $w$. Show that a player with the maximum number of wins is a champion. Find a 5-vertex tournament in which every player is a champion.