All numbered problems are from West, 2nd edition.

Homework 6 (due Mon 03)

(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?
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.

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)