All numbered problems are from West, 2nd edition.

Homework 11 (due Apr 15)

Defined on pg. 166: For $X, Y ⊆ V (G)$, an $X, Y$ -path is a path having first vertex in $X$, last vertex in $Y$, and no other vertex in $X ∪ Y$. In the following, you will prove the $S, T$-path theorem: for any k-connected graph G, if S and T are disjoint subsets of V (G) with size at least k, then we can find k pairwise disjoint S, T -paths in G. Note: these paths are not just internally disjoint; they cannot share endpoints either.
1. Read the Expansion Lemma 4.2.3 in the book, pg. 162. Add a new vertex $u$ adjacent to every vertex in S and a new vertex v adjacent to every vertex in T and call the resulting graph $G′$ . What does the expansion lemma tell us about $G ′$?
2. Apply Menger’s theorem to $u, v$ in $G′$ and finish the proof of the $S, T$ -path theorem.
Given a (undirected) graph G, recall that the line graph L(G) is defined as the simple graph whose vertex set V (L(G)) is the same as the edge set of G, E(G). Two distinct edges e, f in G viewed as vertices of L(G) are adjacent in L(G) if and only if e and f are incident to a common vertex in G.
1. Characterize the graphs G which have line graph L(G) equal to the empty graph.
2. Let $n ≥ 3$. What standard graphs are $L(P_n)$ , and $L(C_n)$ and $L(K_{1,n})$ isomorphic to?
3. For the graph below, draw the line graph.

hw9fig1

Homework 10 (due Apr 8)

Let $G$ be a connected graph in which for every edge $e$, there are cycles $C_1$ and $C_2$ containing $e$ whose only common edge is $e$. Prove that $G$ is 3-edge-connected.
1. Use this to show that the Petersen graph is 3-edge-connected.
2. Use Proposition 4.1.12 and Theorem 4.1.11 from the textbook to prove that the Petersen graph is 3-connected.
We showed that $κ(Q_k ) = k$ for $k ≥ 2$, where $Q_k$ is the hypercube graph.
1. Given a pair of non-adjacent vertices $x, y$ in $Q_k$, what is the maximum number of pairwise internally disjoint $x, y$-paths? Fully justify.
2. Explicitly show by example that your answer is correct on $Q_3$
Find the smallest 3-regular simple graph having connectivity $1$.
Let $n,k$ be positive integers with $n$ even, $k$ odd and $n > k > 1$. Let $G$ be the $k$-regular simple graph formed by placing $n$ vertices on a circle and making each vertex adjacent to the oppositve vertex and to the $(k-1)/2$ nearest vertices in each direction. Prove that $\kappa(G) = k$.
Prove that every vertex of a graph has even degree if and only if every block is Eulerian.

Homework 9 (due Apr 2)

Using the Hungarian algorithm, solve the assignment problem for the following matrix

$W = \begin{pmatrix} 7 & 8 & 9 & 8 & 7 \\ 8 & 7 & 6 & 7 & 7 \\ 9 & 6 & 5 & 4 & 6 \\ 8 & 5 & 7 & 6 & 4 \\ 7 & 6 & 5 & 5 & 5 \end{pmatrix}$
Two people play a game on a graph $G$, alternately choosing distinct vertices. Player 1 starts by choosing any vertex. Each subsequent choise must be adjacent to the preceding choice (of the other player). Thus they follow a path. The last player able to move wins. Prove that the second player has a winning strategy if $G$ has a perfect matching, and otherwise the first player has a winning strategy. (Hint: For the second part, the first player should start with a vertex omitted by some maximum matching.)
A permutation matrix is a $0,1$ matrix having exactly one 1 in each row and each column. Prove that a square matrix of nonnegative integers can be expressed as the sum of $k$ permutation matrices iff all row sums and all column sums are equal to $k$.
Determine the stable matchings resulting from the Proposal Algorithm run with both men proposing and women proposing, given the preference lists below:

$\begin{align*} \text{Men}: & \{u,v,w,x,y,z\} \\ u: & a > b > d > c > f > e \\ v: & a > b > c > f > e > d \\ w: & c > b > d > a > f > e \\ x: & c > a > d > b > e > f \\ y: & c > d > a > b > f > e \\ z: & d > e > f > c > b > a \end{align*}$ $\begin{align*} \text{Women}: & \{a,b,c,d,e,f\} \\ a: & z > x > y > u > v > w \\ b: & y > z > w > x > v > u \\ c: & v > x > w > y > u > z \\ d: & w > y > u > x > z > v \\ e: & u > v > x > w > y > z \\ f: & u > w > x > v > z > y \end{align*}$

Homework 8 (due Mar 26)

Let $Q_k$ be the k-dimensional hypercube.
1. Use induction to prove that for $k ≥ 2$, $Q_k$ has at least $2^{2^{k−2}}$ perfect matchings.
2. The Hamming weight of a vertex in $Q_k$ is the number of 1s in its label. For example, in $Q_3 , v = (0, 0, 0)$ has Hamming weight $0$ and $w = (1, 0, 1)$ has Hamming weight $2$. How many vertices of $Q_k$ have Hamming weight $j$?
3. Prove that for every perfect matching in $Q_k$ , the number of edges matching vertices with Hamming weight $i$ to vertices with Hamming weight $i + 1$ is $\binom{k-1}{i}$, for $0 ≤ i ≤ k − 1$. Hint: Use induction on $i$. If a vertex with Hamming weight $i$ is not matched to a vertex with Hamming weight $i + 1$ then it is matched to a vertex with Hamming weight $i − 1$.
Recall that $\maxM(G)$ denotes the maximum size of a matching in G. Suppose that $\tilde{M}$ is a matching in $G$ with less than $\maxM(G)/2$ edges. Show that if $M$ is a maximum matching in $G$, then there is an edge $e ∈ M$ such that $\tilde{M} + e$ is a matching in $G$. Explain why every maximal matching in $G$ must have $\maxM(G)/2$ edges.
Using nonnegative edge weights, construct a 4-vertex weighted graph in which the matching of maximum weight is not a matching of maximum size.
Use the augmenting path algorith to find a maximum matching and minimum vertex cover in the bipartite graph whose adjacency matrix is:

$\begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\ \end{bmatrix}$

Note: Be sure to use augmenting path algorithm even though it may be possible to find a maximum matching simply by inspection since this graph is small.

Homework 7 (due Mar 19)

An up/down labeling is a graceful labeling for which there exists a critical value $\alpha$ such that every edge joints vertices with labels above and below $\alpha$. Prove that every caterpillar has an up/down labeling. Prove that the 7-vertex tree that is not a caterpillar has no up/down labeling. solution
There are five cities in a network. The travel time for traveling directly from $i$ to $j$ is the entry $a_{ij}$ in the matrix below. The matrix represents a directed graph. Determine the least travel time and quickest route from $i$ to $j$ for each pair $i,j$.

$\begin{bmatrix} 0 & 10 & 20 & \infty & 17 \\ 7 & 0 & 5 & 22 & 33 \\ 14 & 13 & 0 & 15 & 27 \\ 30 & \infty & 17 & 0 & 10 \\ \infty & 15 & 12 & 8 & 0 \end{bmatrix}$
Assign integer weights to the edges of $K_n$. Prove that on every cycle the total weight is even iff the subgraph consisting of the edges with odd weight is a spanning complete bipartite subgraph. Hint: Show that every component of the subgraph consisting of the edges with even weight is a complete graph.
Prim’s algorithm grows a spanning tree from a given vertex of a connected weighted graph $G$ iteratively adding the cheapest edge from a vertex already reached toa vertex not yet reached, finishing when all the vertices of $G$ have been reached. (Ties are broken arbitrarily). Prove that Prim’s algorithm produces a minimum-weight spanning tree of $G$. Due to Jarnik [1930], Prim [1957], Dijstra [1959]

Homework 6 (due Mar 04)

(Problem 2.1.62 in West). Given a connected graph $G$ with $n$ vertices, a new graph $G'$ is constructed as follows: for each spanning tree of $G$, we draw a vertex in $G'$. Vertices in $G'$ are adjacent if and only if the corresponding spanning trees in $G$ have exactly $n-2$ common edges (or equivalently, only differ by one edge). Answer the questions below (do not do 2.1.62 as written, although it might be helpful to consider the example drawn there).
1. Suppose $G=C_3$ with edges $e_1, e_2, e_3$. There are 3 spanning trees (obtained by deleting one edge) leading to 3 vertices in $G': t_1=\{e_1,e_2\}, t_2=\{e_1,e_3\}, t_3=\{e_2,e_3\}$. All pairs $t_i, t_j$ are adjacent since they only differ by one edge, therefore $G'=C_3$. Show more generally that if $G=C_n$, then $G'=K_n$.
2. Show more generally that if $C_m$ is a subgraph of $G$, then $G'$ contains the clique $K_m$. (Careful here: If $\vert V(G)\vert >m$ you need to think more about how spanning trees can differ).
3. Find $G'$ for the path $G=P_n$. Now finish the following sentence appropriately: “If $G$ is a tree, then…”
4. Prove that if $\vert V(G')\vert \geq 2$, then $G'$ has no isolated vertex.
5. Prove that $G'$ is connected. Hint: let $t_1, t_2$ be vertices in $G'$ corresponding to spanning trees $T_1\neq T_2$ of $G$. To walk from $t_1$, cut an appropriate edge from $T_1$, then add an appropriate edge from $T_2$. If you do not arrive at $t_2$, what do you do?
solution
In general, a metric space is a set $X$ with a metric defined on the set. A metric $d$ is a notion of distance which must satisfy the following three properties:
1. $d(u,v)\geq 0$ for all $u,v \in X$ with equality iff $u=v$.
2. $d(u,v)=d(v,u)$ for all $u,v \in X$.
3. $d(u,v)\leq d(u,z)+d(z,v)$ for all $u,v,z \in X$. (triangle inequality)
1. For a graph $G$, the distance $d(x,y)$ defined for $x, y \in V(G)$ on page 71 is a metric. Verify that (i) and (ii) are satisfied. Show that the triangle inequality $(iii)$ holds.
2. Use part (a) to prove that for any graph $G$, $\mbox{diam}(G)\leq 2\mbox{rad}(G)$.
Let $G$ be the 3-regular graph with $4m$ vertices formed from $m$ pairwise disjoint kites by adding $m$ edges to link them in a ring. Prove that $\tau(G) = 2m8^m$. See Problem 2.2.6 for a picture.
Use Cayley’s Formula to prove that the graph obtained from $K_n$ by deleting an edge has $(n-2)n^{n-3}$ spanning trees.
Prove that a $d$-regular simple graph $G$ has a decomposition into copies of $K_{1,d}$ iff it is bipartite. solution

Homework 5 (due Feb 25)

Prove that every $n$ vertex graph with $m$ edges has at least m - n + 1 cycles. solution
Let $k\geq 2$. Suppose $T$ is a tree with $n$ vertices, $k$ leaves, and $\Delta(T)=k$.
1. Show that $T$ decomposes into $k$ paths with a common endpoint.
2. Find the minimum and maximum values of $\mbox{diam}(T)$ in terms of $n$ and $k$ and draw representative examples attaining these values.
Let $T$ be a tournament with no vertex of indegree $0$ (i.e. no player beat every other player).
1. Prove that if $x$ is a king in $T$, then $T$ has another king in $N^{-}(x)=\{ \text{ predecessors of } x \}$.
2. Use this to prove $T$ has at least $3$ kings.
3. For each $n \geq 3$ construct a tournament with $\delta^{-}(T) > 0$ and only $3$ kings.
For a loopless (undirected) graph $G$, a matrix that comes up often is the Laplacian matrix $\mathbb{L} = \mathbb{D} - \mathbb{A}$ where $\mathbb{D}$ is a diagonal matrix with diagonal entries the degrees of vertices in $G$ (with respect to some vertex ordering) and $\mathbb{A}$ is the adjacency matrix of $G$ (with respect to the same vertex ordering).
1. Show that $\begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix}$ is an eigenvector of $\mathbb{L}$. What is the corresponding eigenvalue? Explain how your result shows that $\mathbb{L}$ is always singular i.e. $det(\mathbb{L})=0$.
2. If $G$ is a $d$-regular graph, explain why the spectrum of $\mathbb{L}$ and the spectrum of $\mathbb{A}$ are related by $Spectrum(\mathbb{L}) = d - Spectrum(\mathbb{A})$ i.e., $\lambda$ is an eigenvalue of $\mathbb{A}$ of multiplicity $m$ if and only if $d-\lambda$ is an eigenvalue of $\mathbb{L}$ of multiplicity $m$.
(The Laplacian comes up in applications of graph theory to probability and physics - it is always good to check when reading an application involving the spectrum of a graph to see whether the spectrum of the adjacency matrix or Laplacian is meant. When the graph is regular you have shown that they are easily obtainable from each other but for general graphs the relationship is more subtle. We will see one application of the Laplacian in the Matrix Tree Theorem coming up soon in the chapter on Trees.)

solution

Homework 4 (due Feb 18)

Let $u$ and $v$ be adjacent vertices in a simple graph $G$. Prove that $uv$ belongs to at least $d(u) + d(v) - n(G)$ triangles in $G$.
Let $G$ be a graph with at least two vertices. Prove or disprove:
1. Deleting a vertex of degree $\Delta(G)$ cannot increase the average degree
2. Deleting a vertex of degree $\delta(G)$ cannot reduce the average degree
Let $d_1, \dots, d_n$ be a list of nonnegative integers with even sum and whose largest entry is strictly less than $n$ and differs from the smallest entry by at most $1$, e.g., $4,4,4,3,3,3,3$ or $5,5,5,5,4,4,4,4,4$. Show that any such sequence is a graphic sequence i.e., is the degree sequence of some simple graph.

solution
Let $d_1 \geq \ldots \geq d_n \geq 0$ be integers. Prove that there is a loopless graph (multiple edges allowed) with degree sequence $d_1,\ldots,d_n$ if and only if $\sum_i d_i$ is even $d_1 \leq d_2 + \cdots + d_n$.

solution
Let $G$ be an $n$-vertex digraph with no cycles. Prove that the vertices of $G$ can be ordered as $v_1,\ldots,v_n$ so that if $v_i v_j \in E(G)$ then $i < j$

Homework 3 (due Feb 11)

Prove that every $n$ vertex graph with at least $n$ edges contains a cycle.
Let $G$ be a connected even graph. At each vertex, partition the incident edges into pairs (each edge appears in a pair for each of its endpoints). Starting along a given edge $e$, form a trail by leaving each vertex along the edge paired with the edge just used to enter it, ending with the edge paired with $e$. This decomposes $G$ into closed trails. As long as there is more than one trail in the decomposition, find two trails with a common vertex and combine them into a longer trail by changing the pairing at a common vertex. Prove that this procedure works and produces an Eulerian circuit as its final trail. (Tucker [1976]).
Prove or disprove: if $u$ and $v$ are the only vertices of odd degree in a graph $G$, then $G$ contains a $u,v$-path.
In a class with nine students, each student sends valentine cards to three others. Determine whether it is possible that each student receives cards from the same three students to whom he or she sent cards.

solution
Let $u$ and $v$ be adjacent vertices in a simple graph $G$. Prove that $uv$ belongs to at least $d(u) + d(v) - n(G)$ triangles in $G$.

Homework 2 (due Feb 4)

Let $G$ be a graph. For a vertex $v$ and edge $e$, describe the adjacency matrices of $G - e$ and $G - v$.
Let $v$ be a vertex of a connected simple graph $G$. Prove that $v$ has a neighbor in every component of $G - v$. Conclude that no graph has a cut vertex of degree $1$.
Prove that a graph $G$ is bipartite iff every subgraph $H$ of $G$ has an independent set consisting of at least half of $V(H)$.

Inductive solution for problem 3 (1.2.26 from west

Homework 1 (due Jan 28)

Solutions

1.1.4 (Two graphs are isomorphic iff their complements are)
1.1.11 (Determine maximum size in a clique and maximum size of an independent set in a particular graph)
1.1.14 (Removing opposite corners of a checkerboard, and then domino tiling it)
1.1.15 (Determine isomorphism classes of graphs that are both paths and cycles, complete graphs that are also bipartite, and so on. A total of 6 pairs)
1.1.29 (Prove that every set of six people have at least 3 mutual acquaintances or 3 mutual strangers)