A graph \( G \) consists of a vertex set \( V(G) \), whose elements are called vertices and an edge set \( E(G) \), where elements in \( E(G) \) are unordered pairs of vertices.
The elements of \(E(G)\) are called edges.
Remarks: Recall that an unordered pair is just any two-element set \(\{ u , v \}\), where \(u\ne v.\) For brevity, we often write such an edge more simply as \( uv \).
In various contexts, it is common to denote an edge by the ordered pair \( (u,v) \).
This leads to an alternative definition of a graph, equivalent to ours, as a relation on the vertex set \(V(G)\) that is both symmetric (meaning that \( (u,v) \) is an edge if and only if \( (v,u) \) is an edge) and irreflexive (meaning that \( (u,u) \) is never an edge.)
Example 1:
The picture shown above is a visual representation of a graph with the \(6\) vertices and \(8\) edges given below.
For any edge \( uv \in E(G) \), the vertices \( u, v \in V(G) \) are said to be adjacent and/or neighbors in \( G \). The vertices \( u, v \) are called the ends of the edge \( uv \), and any edge is said to be incident at either of its ends.
For any vertex \( u \in V(G) \), we define its neighborhood as the set
$$ \Gamma(u) = \{ v \in V(G) \mid uv \in E(G) \}. $$
The degree of \( u \) is the integer \( d(u) = \#\Gamma(u) \), which counts the number of \(u\)'s neighbors.
Our notation for neighborhood and degree suppress the dependence on the graph \(G,\) which is usually clear from the context. In cases where we must consider multiple graphs, we may instead write \(\Gamma_G\) and \(d_G.\)
If we sort the degrees of a graph's vertices in descending order, \( d(v_1) \ge \ldots \ge d(v_n) \), we obtain a sequence of nonnegative integers, written \( d(v_1) d(v_2) \cdots d(v_n) \), which is called the degree sequence of the graph.
Example 1 (cont.):
Let us determine the degrees of all vertices in our running example:
Notice what happens if we sum over all six vertices' degrees: \( 2+2+4+3+2+3 = 16 = 2 \cdot \#E(G). \) This reflects a general fact called the handshaking lemma, which we prove below.
Variations on the Definition of a Graph
Our definition of a graph given above can be qualified by describing it as a simple, undirected graph.
Directed Graph (Digraph): Edges are ordered pairs, often denoted \( \overrightarrow{uv} \) (an edge directed from \( u\) to \( v \). Digraphs allow the possibility of loops, which are edges of the form \( \overrightarrow{uu} \). A digraph with no loops is essentially a graph if it has the property that \( \overrightarrow{uv} \) is a directed edge if and only if \( \overrightarrow{vu} \) is.
Multigraph: The same edge can appear more than once. More formally, an (undirected) multigraph consists of a vertex set \( V(G) \), edge set \( E(G) \), and incidence function \( \psi \) that takes edges to unordered pairs of vertices: if ordered pairs are used, one obtains a directed multigraph. In addition to loops, in a multigraph it is possible to have parallel edges, meaning \( e, e' \in E(G) \) such that \( \psi (e) = \psi (e') = uv. \) A multigraph is simple if it has no loops or parallel edges.
In this course, "graph" always means a simple, undirected graph. When the need to consider digraphs or multigraphs arises, we will explicitly use these terms.
The Handshaking Lemma
Theorem: For any graph \( G \),
$$ \sum_{v \in V(G)} d(v) = 2 \cdot \#E(G) $$
One consequence of this result is the saying that "at any party, an even number of hands are shaken."
Proof: Consider the set of ordered pairs
$$ S = \{ (u,v) \in V(G) \times V(G) \mid uv \in E(G) \} $$
We will count the elements of \( S \) in two different ways.
First way: For any vertex \( v \in V(G) \), there are exactly \( d(v) \) pairs \( (u,v) \in S \). Thus, \( \#S = \sum_{v \in V(G)} d(v) \).
Second way: Any edge \( uv \in E(G) \) contributes exactly two elements to \( S \), namely \( (u,v) \) and \( (v,u) \). Thus, \( \#S = 2 \cdot \#E(G) \).
Combining these finishes the proof.
Exercise How does the handshaking lemma generalize to digraphs and/or multigraphs?
2. Subgraphs, Isomorphism, and Connected Graphs
Two Notions of Subgraph
A graph \( G' \) is a subgraph of \( G \) if \( V(G') \subseteq V(G) \) and \( E(G') \subseteq E(G) \). We write \( G' \subset G \).
For any subset of vertices \( U \subseteq V(G) \), we may form the induced subgraph \( G[U] \) with vertex set \( U \) and edge set \( \{ uv \in E(G) \mid u,v \in U \} \). "Induced subgraph" is a stronger condition than "subgraph."
Consider the graph \( G \) shown below:
Two of the induced subgraphs of \( G \) are shown below.
The next graph is a subgraph of \( G \) which is not induced.
Complete Graphs and Isomorphism
We say a graph is complete if any two of its vertices are adjacent.
Thus, the number of edges in a complete graph on \( n \) vertices is equal to the binomial coefficient \( \binom{n}{2} = \frac{n (n-1)}{2}. \) An \( n \)-vertex complete graph is also called an \(n \)-clique. The images below show \( n \)-cliques for \(n \in \{ 1,2,3,4 \} \).
\(K_1\)
\(K_2\)
\(K_3\)
\(K_4\)
Here is another image of a \(4\)-clique:
\(K_4\)
Notice that both \( 4 \)-cliques are labeled as \( K_4 \), despite two notable differences between the pictures: namely, (1) the two graphs have different vertex labels, and (2) one clique is drawn with edge crossings, and the other is not.
Note, however, that we could also draw the first four-clique without any crossings.
Indeed, if we simply relabel the vertices \(5,6,7,8\), respectively, by \(1,2,3,4\), we will get the same vertices and edges.
All cliques of a given size are exactly the same up to relabeling: this is formalized by the notion of graph isomorphism.
Recall that a bijection between two sets is a function that is one-to-one and onto.
Two graphs \( G, H \) are isomorphic if there exists a bijection of vertex sets \( \iota : V(G) \to V (H) \) that preserves adjacency: $$ uv \in E(G) \quad \Leftrightarrow \quad \iota (u) \iota (v) \in E(H).$$
It is not always obvious when two graphs are isomorphic: consider, for example, the two isomorphic graphs shown below, where we may construct the following isomorphism:
$$\iota (1)= 8,
\quad
\iota (2) = 10, \quad \iota (3) = 9, \quad \iota (4) = 6, \quad \iota (5) = 7.
$$
For the \( 5 \)-clique shown below, it turns out we cannot draw all \( 10 \) edges in the plane without crossings. Graphs which can be drawn in this way are said to be planar. Planar graphs are characterized by a theorem of Kuratowski, which we will discuss later in the course.
\(K_5\)
Paths, Cycles, and Connectivity
A path is a graph \( P \) of the form \( V(P) = \{x_0, \dots, x_l\} \) and \( E(P) = \{x_0x_1, x_1x_2, \dots, x_{l-1}x_l\} \), where all vertices \( x_i \) must be distinct.
The number of edges \( l \) is the length of \( P \). A path may also be denoted by \( x_0 \dots x_l \). The vertices \( x_0, x_l \) are the ends of the path \( P \), which is also said to be a \( x_0 x_l \)-path, or a path from \( x_0 \) to \( x_l) \). The ends of a path are the two unique degree-1 vertices: any other vertices must have degree 2.
Similarly, a cycle of length \( l \) is a graph \( C \) with vertex set \( V(C) = \{ x_1, \dots, x_l\} \) and edge set \( E(C) = \{ x_1x_2, \dots, x_{l-1}x_l, x_l x_1 \}. \) All vertices in a cycle must have degree 2.
When we refer to a "path" or a "cycle" in a graph, one should think of a subgraph isomorphic to the path and cycle graphs defined above.
In an \( n \)-vertex graph, a Hamiltonian path is any path of length \( n-1 \), and a Hamiltonian cycle is any cycle of length \( n \). Currently, there is no known algorithm for efficiently detecting Hamiltonian paths or cycles in a graph: this is related to the famous unsolved P vs NP problem.
A graph \( G \) is connected if it contains a \( uv \)-path for any \( u, v \in V(G) \). A maximal connected subgraph is a called a connected component. In most circumstances, if we have a graph with multiple connected components, it is better to think of the connected components separately as connected graphs.
Census of Small Graphs
For each \( n \in \{ 1, 2 \} \), there is exactly one connected graph up to isomorphism, the complete graphs \( K_1, K_2 \).
For \( n = 3 \) vertices, there are two nonisomorphic connected graphs: the triangle \( K_3 \) and the length-2 path:
For \( n = 4 \) vertices, there are exactly 6 isomorphism classes of connected graphs, shown below:
The number of \(n \)-vertex connected graph isomorphism classes has been tabluated for small values by the Online Encyclopedia of Integer Sequences (OEIS). This number grows exponentially in \( n .\)
For \( n=5 \) vertices, we find an example of two connected nonisomorphic graphs with the same degree sequence \( 33222 \).
Thus, two isomorphic graphs must have the same degree sequence, but not conversely.
A Connectivity Criterion
Proposition If \( G \) is a graph on \( n \) vertices where every vertex has degree at least \( \frac{n-1}{2} \), then \( G \) is connected.
In fact, our proof will show something stronger: such a graph will contain, for any \( u, v \in V(G) \), a \(uv\)-path of length at most 2. Note additionally that the converse of this proposition does not hold (take \( G \) to be a path of length at least 4.) This proposition can be viewed as a "local-to-global" principle ("local" information like the degrees of vertices gives us connectivity, a "global" property of the graph.)
Proof: Let \( u, v \in V(G) \) be distinct vertices. If \( uv \in E(G) \), we are done, so suppose not. We show \( \Gamma(u) \cap \Gamma(v) \neq \emptyset \), implying a path \(uwv \) for any \( w \in \Gamma (u) \cap \Gamma (v) \).
Consider the set \( A = \{ e \in E(G) \mid u \text{ or } v \text{ is an end of } e \} \).
We have \( \# A = d(u) + d(v) \ge \frac{n-1}{2} + \frac{n-1}{2} = n-1 \).
Next set \( B = V (G) \setminus \{ u, v \} \), and a function \( f : A \to B \) by the rule that \( f(e) = w\), where \( w \) is the end of \( e\in A\) not equal to \( u \) or \( v \).
By the Pigeonhole Principle, since \( \#A \ge n-1 > n-2 = \#B \), there must be a vertex \( w \in B\) with \( w \in \Gamma (u) \cap \Gamma (v)\).
3. Walks, Trails, Circuits and All That
Basic Definitions
Throughout this section, \( G \) will denote a multigraph.
A walk in a multigraph \( G \) is an alternating sequence of vertices and edges
$$
W = ( v_0, e_1, v_1, e_2, v_2, \ldots , v_{k-1}, e_k, v_k ),
$$
where \(v_0, \ldots , v_k \in V(G) \) and \( e_1, \ldots , e_k \in E(G) \) with \( e_i = v_{i-1} v_i \) for all \( i \). The integer \( k \ge 1\) is called the length of \( W \), and the vertices \( v_0 = v_k \) are its ends.
A walk is said to be closed if all of its ends are equal, \( v_0 = v_k \). A trail is a walk with no repeated edges, \( e_i \ne e_j \) for all \( i\ne j \). A circuit is a closed trail. One can essentially view the previously-defined notion of a path as being a trail with no repeated vertices. Similarly, a cycle is more-or-less the same as a circuit with no repeated vertices except the ends.
Example:
Consider the 5-vertex "house graph" with the following labeling:
There is a closed walk of length \( 7 \) given by
\(
W = (b, bd, d, de, e, ce, c, bc, b, ba, a, ac, c, bc, b).
\)
Since the edge \( bc \) is repeated, the walk \( W \) is not a circuit.
The walk
\(
T = (c, bc, b, bd, d, de, e, ce, c, ac, a, ab, b )
\)
is a trail that visits every edge of the house graph exactly once. This is called an Eulerian trail.
Finding paths and cycles in walks
Lemma
For any multigraph \( G \), the following hold:
Every walk with ends \( u, v\in V(G), u \ne v \) includes the edge set of a \( uv \)-path.
Every circuit includes the edge set of a cycle.
Every closed walk of odd length includes the edge set of an odd-length cycle.
Note: Any edge \(uv \in E(G) \) gives a closed walk \( W = (u, uv, v, uv, u ) \) of length 2. We may form even-length walks that can be arbitrarily long by taking \( (W, \ldots , W) \). Observe that walks of this form contain neither any even nor any odd cycle. This explains necessity of our hypotheses in parts 2 and 3 of this Lemma.
Proof: We will prove part 1, and leave parts 2 and 3 as an exercise for you.
We prove part 1 by induction on the length of the walk \( W \).
Base case A walk of length \( 1 \) has the form \( (u, uv, v) \), and \( \{ uv \} \) is the edge-set of a \( uv \)-path.
Inductive Step Let \( W \) be a \( uv \)-walk of length greater than \( 1 \). We assume the inductive hypothesis that our claim holds for all \(uv\)-walks of length strictly less than the length of \( W \). If \( W \) contains no repeated vertices, then all edges of \( W \) form the edge-set of a \( uv \)-path.
Otherwise, \( W \) has a repeated vertex \( w \). This means it has the form
$$
W = (W', w, e, \ldots , e', w, W''),
$$
where \( W' \) is a walk beginning at \( u \), \( W '' \) is a walk ending at \( v \), and \( (w, e, \ldots , e', w) \) is a closed walk of length at least \( 1 .\) By deleting this closed walk, we obtain a new \( uv \)-walk, $$(W' , W''),$$ whose length is strictly less than that of \( W \). By inductive hypothesis, this walk contains the edge set of a \( uv \)-path. Since all of this walk's edges belong to \( W \) we are done.
Bipartite Graphs
Theorem: The following are equivalent for a multigraph \( G \):
\( G \) contains no cycles of odd length.
\( V(G)=A \sqcup B \) is the union of two disjoint sets \( A \) and \( B \), such that every edge in \( G \) has one end in \( A \) and one in \( B \). (Such a multigraph is said to be bipartite).
Remark: The notation \(A \sqcup B\) is used when taking the union \( A \cup B \) of two sets which are disjoint, \( A \cap B = \emptyset \).
Proof
(2) \(\Rightarrow\) (1): Consider any cycle \( C \subset G \), \(C= x_1 x_2 \dots x_l x_1 \).
Either \( x_1 \in A \) or \( x_1 \in B \); assume \( x_1 \in A \) without loss of generality.
Then \( x_2 \in B \), \( x_3 \in A \), etc. Vertex colors alternate. Since the cycle returns to \( x_1 \in A \) after \( l \) steps, the length of the cycle \( l \) must be even.
(1) \(\Rightarrow\) (2): It is enough to consider the case where \( G \) is connected. (If \( G \) has components \( G_1, \dots, G_c \) with vertex bipartitions \( V(G_i) = A_i \sqcup B_i \), we may then take \( A = \bigcup_{1\le i \le c} A_i \) and \( B = \bigcup_{1\le i \le c} B_i \)).
Fix a vertex \( v \in V(G) \) and define:
$$ A = \{ u \in V(G) \mid \exists \text{ even } uv \text{-walk in } G \} $$
$$ B = \{ u \in V(G) \mid \exists \text{ odd } uv \text{-walk in } G \} $$
Since \( G \) is connected, we have \( V(G) = A \cup B \).
Claim: \( A \cap B = \emptyset \).
If not, then for any \( u \in A \cap B \), we have an even \( uv \)-walk \( W_1 \) and an odd \( vu \)-walk \( W_2 \), the latter of which can be obtained by reversing a \( uv \)-walk promised by the definition of \(B \).
Gluing the two walks gives us \( (W_1, W_2) \), which is an odd closed walk from \( u \) to \( u \).
By the previous lemma, this contains an odd cycle, which would contradict our starting assumption that the graph \( G \) contains only even cycles.
Thus \( V(G) = A \sqcup B \). Finally, we check that all edges cross between \(A \) and \(B \). If there were an edge \( uw \) with both ends in one of the sets \( A \) or \( B \), we could combine \(vu\)-walk \( W \) with the edge \( uw \) to create a \(vw\)-walk \( W ' = (W, uw, w ) \) such that \( W \) and \( W' \) have opposite parity (meaning that either \( W \) is even and \( W' \) is odd or vice-versa.) This, however, would contradict the previously-established disjointness of \( A \) and \( B \). Thus every edge of \( G\) has one end in \( A \) and the other in \( B \).
We've already encountered several examples of bipartite graphs. One of them is the "UFO graph" shown below, better known as the complete bipartite graph \( K_{2,3} \).
A suitable vertex bipartition is indicated by the red and blue vertices below. Observe that every cycle in this graph has length \( 4 \).
More generally, for any integers \( m,n \ge 1 \), there is a complete bipartite graph \( K_{m,n} \) on \( m+n \) vertices which can be defined as folllows:
$$
V(K_{m,n})= \{ a_1, \ldots , a_m, b_1, \ldots , b_n \}, \quad E (K_{m,n} ) = \{ a_i b_j \mid a_i \in A , b_j \in B \}.
$$
Eulerian Trails and Circuits
A trail in a multigraph \( G \) that visits every edge is said to be an Eulerian trail. Similarly, we define an Eulerian circuit to be a circuit which visits every edge exactly once.
A graph is Eulerian if it contains an Eulerian circuit.
Eulerian circuits are named after Leonhard Euler, who solved in 1736 a famous problem known as the Seven Bridges of Königsberg. The image below shows the city of Königsberg (now Kaliningrad, Russia.) Notice there are 7 bridges separating 4 landmasses. Can we cross all 7 bridges without using the same bridge twice?
Naturally, we will model this problem by constructing a multigraph, whose four vertices correspond to the landmasses, and whose seven edges correspond to the bridges.
The degree sequence is \( 5333 \). The following theorem provides a negative answer to the 7 bridges problem.
Theorem: A connected multigraph \( G \) has an Eulerian circuit if and only if every vertex has even degree.
Similarly, it has an Eulerian trail from \( u \) to \( v \) iff \( u \) and \( v \) are the only odd-degree vertices.
Proof of Necessity:
Suppose \( G \) is a graph containing an Eulerian circuit \( C \). Every time a vertex of \( G \) appears in \( C \), this accounts for an two number of edges (1 in and 1 out). Since \( C \) is a circuit, none of the edges in \( C \) are repeated. Furthermore, since \( C \) is Eulerian, every edge of \( G \) appears in \(C \). Finally, since \( G \) is connected, every vertex must appear in \( C \). Altogether, these facts show that every vertex of \( G \) has even degree.
A similar argument shows if \(G \) has an Eulerian trail from \( u \) to \( v \), then \( \text{deg}(u) \) and \( \text{deg}(v) \) are odd, and all other vertices even.
Proof of Sufficiency:
First, consider the case where \( G \) is a connected graph such that every vertex has even degree. We will prove that \( G \) has an Eulerian circuit using induction on the number of edges \( \# E( G) \).
As a base case, we may assume \( \# E(G) = 0.\) In this case, connectedness implies that \( G \) is a graph with one vertex \( v \), and the sequence \( C = (v) \) is an Eulerian circuit, since there are no edges in \(G \) to visit.
Now, suppose \( G \) is a graph with \( \# E(G) > 0\). We establish two claims.
Claim 1: \( G \) contains a circuit.
Proof: Let \( P \subseteq G \) be a path of maximal length, with ends \( u \) and \( v \). Since \( \text{deg}(u) \ge 2 \), \( u \) must have an incident edge \( e=uw \notin E(P) \). However, we cannot have \( w \notin V(P) \), since then we could get a path longer than \( P \). Thus, \( w \in V(P) \), and following \( P \) from \( u \) to \( w \) and then \( e \) gives us a circuit (in fact, a cycle.) (Note: this argument will give you a hint about how to solve Homework 1's Problem 5).
Claim 2: A maximal circuit \( C \) in \( G \) is Eulerian.
Proof: Suppose not, and consider the subgraph \( G' \subseteq G \) obtained by deleting edges in \( C \). If \( C\) was not Eulerian, then \(G ' \) would have a connected component \( H \) with at least one edge. Since every vertex in \( H \) has lost an even number of edges from \( C\), we may apply the inductive hypothesis to see that \( H \) has an Eulerian circuit \( D \). The circuits \( C \) and \( D \) are both edge-disjoint. They also have a common vertex \( u \in V(C) \cap V(D) \): this follows from the connectivity of \( G \). Without loss of generality, we may assume that \( u \) is the starting vertex for both circuits; with this assumption, we could then obtain a new Eulerian circuit by gluing, namely \( (C, D) \), whose length is strictly longer than that of \( C \). This is a contraction, so the claim that \( C \) is an Eulerian circuit must hold.
Trail Case:
Suppose now that \( G \) is connected and \( u, v \in V(G) \) are the only vertices of odd degree. Construct a new graph \( G^* \) with \( V(G^*) = V(G) \cup \{w\} \), where \( w \) is a new vertex not already in \( V(G) \), and \( E(G^*) = E(G) \cup \{uw, vw\} \). By our previous arguments, the graph \( G^* \) contains an Eulerian circuit. Finally, we may observe that removing the edges connected to \( w \) from this circuit produces a \( uv\)-Eulerian trail in the original graph \( G \).
Hamiltonian Graphs
We have seen that Eulerian graphs have a characterization which can be checked efficiently: examine each vertex and check if it has even degree.
In fact, our inductive proof of this characterization already suggests an algorithm for constructing an Eulerian circuit, given that the graph is in fact Eulerian: find a circuit, delete the edges, and recurse on some smaller connected component.
The Seven Bridges Problem that motivated our study of Eulerian graphs is superficially similar to the Traveling Salesperson Problem (TSP), which relates to Hamiltonian graphs, those graphs which contain a cycle through every vertex. Suppose a salesperson must visit \( n \) cities, labeled \( 1, 2, \dots, n \).
The cost of traveling from city \( i \) to city \( j \) is given by a nonnegative number \( c (i,j) \ge 0 \).
The TSP then asks: what is the minimum cost trip that visits all cities and returns back to the original city?
Recognizing Hamiltonian graphs is a special case of TSP. To see this, let \( G \) any graph on \( V(G)=\{1, \dots, n\} \). We define a set of \( \binom{n}{2} \) costs as follows: whenever \( 1 \le i < j \le n \),
$$ c(i,j) = \begin{cases} 0 & \text{if } ij \in E(G) \\ 1 & \text{if } ij \notin E(G) \end{cases} $$
With this choice of costs, observe that
\( G \) has a Hamiltonian cycle \( \iff \) Salesperson has a free trip.
As we have already noted, an efficient characterization of Hamiltonian graphs is currently unknown: providing one would be a major breakthrough.
On the other hand, it is possible to give some sufficient conditions implying Hamiltonicity.
Ore's Theorem: Let \( G \) be a connected graph with \( \#V(G) \ge 3 \) and such that \( d(u) + d(v) \ge \#V(G) \) whenever \( uv \notin E(G) \). Then \( G \) has a Hamiltonian cycle.
Note that the converse of Ore's theorem is false: there are many Hamiltonian graphs where \( d(u) + d(v) < \# V(G) \) for some non-edge \( uv \notin E(G) \). The simplest example is the cycle \( C_5 \), shown below.
Our proof of Ore's Theorem will rely on the lemma below.
Lemma 1: If \( G \) is connected and non-Hamiltonian, then the length of a longest path in \( G \) is at least the length of a longest cycle.
In contrapositive form, Lemma 1 states that if a longest path in a connected graph \( G \) is shorter than a longest cycle, then \( G \) is Hamiltonian.
Indeed, in any Hamiltonian graph \(G \) on \( n \) vertices, the longest cycle has length \( n \) and a longest path has \( n- 1 \).
Proof: Let \( C \) be a longest cycle in \( G \). Since we assumed \( G \) is not Hamiltoninan, the cycle has length \( \ell < \#V(G) \).
Since \( G \) is connected, there exists some vertex \( v \notin V(C) \).
For any \( v_0 \in V(C) \), there exists an \( v_0 \)-path \( P = v_0 v_1 \dots v \).
Pick the smallest index \( i \) such that \( v_i \notin V(C) \), so that \( v_{i-1} \in V(C) \).
We may write our cycle as \( C = (v_{i-1} , u_1, \ldots ,u_{\ell -1 }, v_{i-1} ) \). From this description of \( C \), we may obtain a path of length \( \ell \), namely \( (v_i, v_{i-1} , u_1, \ldots , u_{\ell -1 }) \).
Proof of Ore's Theorem:
Assume \( G \) satisfies the assumptions of Ore's theorem: \( \# V(G) \ge 3 \), and \( d(u) + d(v) \ge \# V(G)\) for any nonedge \(uv \in E(G) \). Using the pigeonhole principle as in our "Connectivity Criterion" from Section 2, we obtain that \( G \) that is connected.
Suppose now that \(G \) is non-Hamiltonian. Consider a longest path in \( G \), \( P = v_0 \dots v_\ell \).
Note that \( \# V(G) \ge 2 \) implies \( \ell \ge 2 \). Having assumed that \( G \) is not Hamiltonian, it follows from Lemma 1 that \( G \) contains no cycle of length greater than \( \ell \).
In particular, this implies \( v_0 v_\ell \notin E(G) \).
Consider the sets:
$$ A = \{ i \mid 1 \le i \le \ell, \quad v_0 v_i \in E(G) \} $$
$$ B = \{ i \mid 1 \le i \le \ell, \quad v_{i-1} v_\ell \in E(G) \} $$
We make the following two observations:
\( \Gamma(v_0) \cup \Gamma(v_\ell) \subseteq V(P) \) (otherwise, we could get longer path)
\( A \cap B = \emptyset \) (otherwise, could get a cycle of length greater than \( \ell \): to see this, note that if \( i\in A \cap B \), then we could construct the a cycle \( v_0 \dots v_{i-1} v_{\ell} v_{\ell -1} \dots v_i v_0 \), which has length \( \ell + 1\), see below.)
Our assumptions on \( G \) and the two observations above imply that $$
\# V(G) \le d(v_0) + d(v_\ell) = \#A + \#B \le \ell < \ell +1 = \# V(P),$$ which is a contradiction since the path \( P \subset G \) cannot have strictly more vertices than \( G \). Thus, our asumption that \( G \) was non-Hamiltonian cannot hold.
Shortest Paths
Graph Distance: On a connected graph, for \( u, v \in V(G) \), \( d(u,v) \) is the length of a shortest \( uv \) path.
Finding a longest path has played a role in the proofs of several of our results so far. Unfortunately, this is yet another problem that is difficult to solve in practice.
Surprisingly, it is much easier to find shortest paths in a graph \( G \).
This is true even if we attach nonegative weights/costs to the edges of \(G \).
Dijkstra's Algorithm finds a shortest \( s-v \) path for some fixed \( s \in V(G) \), and all \( v \in V(G) \setminus \{s\} \).
More generally, this algorithm works for graphs with cost function on edges, \( c: E(G) \to \mathbb{R}_{\ge 0} \).
$$ d(u,v) = \displaystyle\min_{P: \text{ a } uv\text{-path}} \Bigg( \displaystyle\sum_{e \in P} c(e)\Bigg)$$
Algorithm: Dijkstra(G, s, c)
Input: Connected graph \( G \), source \( s \in V(G) \), costs \( c \)
Output: Shortest path distances \( d(s,v) \) for all \( v \in V(G) \)
1
\( V \leftarrow \{s\} \), \( d(s,s)=0 \) // Initialize set of "visited" vertices and distances
2
while \( V \neq V(G) \):
3
Select \( u \in V(G) \setminus V \) and \( v \in V \) that minimize:
\( \text{cost} = d(s,v) + c(v,u) \)
4
update \( V \leftarrow V \cup \{u\} \)
5
\( d(s,u) \leftarrow \text{cost} \)
6
return all distances \( d \)
To illustrate Dijkstra's algorithm, let us consider an example of an undirected graph \( G \), with numeric labels indicating the cost \( c(u,v) \) on each edge \( uv \in E(G) \):
We consider each iteration of the "while" loop in Dijkstra's algorithm below.
First iteration
\( V = \{ s \} \)
Total costs of cut edges: sa (cost 6), sb (cost 2).
Second iteration
\( V = \{ s , b\} \)
Total costs of cut edges: sa (cost 6), bd (cost 2+2=4 ), be (cost 2+5=7).
Third iteration
\( V = \{ s , b, d\} \)
Total costs of cut edges: sa (cost 6), da (cost 1+4=5), dc (cost 4+4=8), de (cost 4+2=6), be (cost 2+5=7)
Fourth iteration
\( V = \{ s , b, d, a\} \)
Total costs of cut edges: ac (cost 5+2=7), dc (cost 4+4=8), de (cost 4+2=6), be (cost 2+5=7)
Fifth iteration
\( V = \{ s , b, d, a, e\} \)
Total costs of cut edges: ac (cost 5+2=7), ec (cost 6+4=10), dc (cost 4+4=8)
Upon termination, all vertices are visited, and Dijkstra's Algorithm has generated a search tree in which every vertex is labeled by its distance from the source.
Theorem: Dijkstra's algorithm finds all shortest paths from \( s \) to all other vertices of \( G \).
Proof: Induction on the number of visited vertices. The base case \( \# V = 1 \) is trivial, so suppose \( \# V > 1 \). Let \( v \in V \) be the most recently visited vertex, and suppose \( uv \) is the corresponding cut edge. By inductive hypothesis, Dijkstra's algorithm has already generated a shortest \( su \)-path, which we denote by \( P_u \). Now suppose \( P \) is an arbitrary \( sv \)-path. Let \( y \in V(P) \) be the closest non-visited vertex to \( s \), and \( x \in V(P) \) its left-neighbor on \( P \). The update rule in Dijkstra's algorithm then tells us that $$d(s, x) + c(x,y) \ge d(s,u) + c(u,v) .$$ Since all costs along edges are nonengative, this then implies that the total cost of \( P\) is at least \(d(s,u) + c(u,v)\). Thus, the path \( (P_u, uv) \) is a shortest \( sv \)-path.
4. Trees
Basic Facts and Examples
Trees are an important class of graphs, which admit several different characterizations.
Tree Theorem: Let \( G \) be a graph. The following are equivalent:
\( G \) is a connected, acyclic graph.
\( G \) is a maximally acyclic graph (adding any edge creates a cycle).
\( G \) is a minimally connected graph (deleting any edge disconnects the graph).
A tree is any graph satisfying the equivalent conditions of this theorem.
Proofs:
For convenience, we assume that \( \# V(G) \ge 3 \). The three conditions of the Theorem are easily seen to hold for graphs on one and two verteices.
(1) \(\Rightarrow\) (2): Suppose \( G \) is connected and acyclic. Since \( G \) cannot be a complete graph, there exist distinct vertices \( u, v \in V(G) \) with \( uv \notin E(G)\).
Consider the graph \( G + uv \) obtained by adding this edge to \( G \). By assumption, there exists a \(uv\)-path \(P\) in \( G\), so it follows that \( G + uv \) contains the cycle \( (P, uv) \). Thus, we see that \(G \) is maximally acyclic.
(2) \(\Rightarrow\) (3):
Suppose \( G \) is maximally acyclic, let \( uv \in E(G) \) be an arbitrary edge, and consider the subgraph \( G - uv \subset G \) obtained by removing this edge from \( G \). If \( G - uv \) contained a \( uv \)-path, then we could use it to construct a cycle in \( G \). Thus, \( G - uv \) does not contain any \( uv \)-path, implying it is disconnected, and thus that \( G \) is minimally connected.
(3) \(\Rightarrow\) (1): It suffices to show a minimally connected graph is acyclic. We prove the contrapositive; a connected graph containing a cycle is not minimally connected. Indeed, if \( G \) is a connected graph containing a cycle \( C \), let \( uv \) be any edge along that cycle, so that \( C = (P, uv) \) for some \(uv \)-path \( P \). We claim that the subgraph \( G - uv \subset G \) is still connected.
Indeed, any two vertices in this graph can be connected by a path in \( G \): if that path contains the edge \( uv \), we can "detour along \( P\)", replacing \( uv \) with \( P \) to get a path with the same ends in \( G - uv \).
Properties of Trees Let \( T \) be a tree.
\( \#E(T) = \#V(T) - 1 \).
\( T \) contains at least two leaves (vertices of degree 1) provided \( \# V(T) \ge 2 \).
First, notice that any tree contains one leaf: if all vertices had degree at least two, we could construct a cycle, contradicting the tree theorem.
Now, one can prove that any tree on \( n \ge 1 \) vertices has \( n- 1 \) edges by induction on \( n \): the case \(n=1\) is trivial, and for \( n > 1 \) one can delete any leaf and apply the inductive hypothesis on the resulting subtree.
Finally, supposing that \( T \) was a tree on \( n \ge 2 \) vertices with a unique leaf \( v \in V(T) \), we would then have
$$
2n - 2 = 2\#E(T) = \sum d(u) = d(v) + \sum_{u\ne v} d(u) \ge 1 + 2(n-1),
$$
which after simplifying would yield the contradiction \( 0 \ge 1 \).
Minimum Spanning Trees (MST) & Kruskal's Algorithm
Problem: You work for an airline, trying to create a network connecting all cities, where each flight has a fixed nonnegative cost, such as in the example below. Your task is to minimize the total cost of all flights while ensuring all cities are connected. The solution to this problem is to run only the flights in a spanning tree.
For any graph \(G \), a subgraph \( T \subseteq G \) is a spanning tree of \( G\) if \( T \) is a tree with \( V(T) = V(G) \).
The Tree Theorem of the previous section has the important corollary that any connected graph \( G \) contains a spanning tree. Indeed, the spanning trees of \( G \) are precisely its minimally-connected subgraphs.
In general, we may pose the following Minimum Spanning Tree (MST) Problem:
Input: Connected graph \( G \), cost function \( c: E(G) \to \mathbb{R} \).
Goal: Find a spanning tree \( T \subset G \) minimizing \( \sum_{e \in E(T)} c(e) \).
Remark: In practice, costs are usually nonnegative. However, unlike our solution for shortest-paths using Dikstra's algorithm, we will be able to find a minimum spanning tree even without this assumption.
We have already encountered spanning trees in our study of Dikstra's algorithm. However, it is important to note that Dijkstra's algorithm does not solve the MST problem. To see this, consider the example shown below. Check for yourself that there are multiple solutions to the MST problem attaining the minimum cost \( 6 \), yet Dijkstra's algorithm will always generate a spanning tree of cost \( 7\), regardless of the source vertex.
Kruskal's algorithm, given below, is similar to Dijktra's algorithm in the sense that it is a "greedy algorithm", which makes a locally optimal choice during each step. But, unlike Dijkstra's algorithm, Kruskal's algorithm yields a globally optimal solution to the MST problem.
\( F \leftarrow (V(G), \emptyset) \) // Initialize graph with no edges
2
Sort edges such that \( c(e_1) \le c(e_2) \le \dots \le c(e_m) \)
3
for \( i = 1 \) to \( m \):
4
if \( F + e_i \) has no cycles:
5
\( F \leftarrow F + e_i \)
6
return \( F \)
Note: an acyclic graph (not necessarily connected) is often called a forest. Thus, Kruskal's algorithm on an \(n \)-vertex graph updates a forest \( F \), initially the empty graph, for \( n-1 \) iterations, until \( F \) is a (minimum) spanning tree.
The correctness of Kruskal's algorithm is the content of our next theorem.
Theorem: Kruskal's Algorithm solves the MST problem.
Proof:
By induction on the number of edges in \( F \), we prove that \( F \) is contained in some minimum spanning tree of \( G \).
Upon termination of Kruskal's algorithm, this will imply that \( F \) itself is a minimum spanning tree.
The base case when \( \# E (F) = 0\) is easy: the empty graph is contained in every (minimum) spanning tree.
In general, suppose inductively that the forest \( F \) is contained in some minimum spanning tree \( T \).
If \( \# E (F) = \# E(T) \), we must have that \(F \) itself is a minimum spanning tree.
Otherwise, let \( e \in E(G) \setminus E(F) \) be the next edge chosen by Kruskal's algorithm.
If \( e \in T \), we are done.
Otherwise, since \(T \) is maximally acylic, the graph \( T+e \) contains a cycle \( C \).
Moreover, since \( F+e \) is acyclic, there exists an edge \( e' \in E(C) \setminus E(F) \).
The update rule of Kruskal's algorithm implies that \( c (e') \ge c(e). \)
Thus, replacing \( e' \) with \( e \) in \( T \) creates a new tree \( T' = T - e' + e \) whose cost is at least that of \( T\).
Since \(T \) is an MST, \( T' \) is also an MST, which contains \( F \) by construction, completing the proof.
Application to the Metric TSP
The Metric Traveling Salesperson Problem (Metric TSP) is a special case of TSP that can be posed as follows: can we find the least-costly Hamiltonian cycle in a complete graph \( G \) equipped with costs on edges \( c : E(G) \to \mathbb{R}_{\ge 0} \) which satisfy the triangle inequality,
$$
c(u,v) \le c(u, w) + c(w, v) \quad \text{ for all } u,v,w \in V(G)?
$$
For an instance of the metric TSP problem, let us consider the following four points in the plane
$$w = (-1, 0), x = (1, 0), y = (0, 0), z = (0, 1) \in \mathbb{R}^2.$$
The distances between these four points give us a weighted 4-clique which is an instance of the metric TSP.
This instance of metric TSP has a unique solution given by the Hamiltonian cycle \(C_* = wyxzw\), with cost of \(c(C_*) = 1 + 1 + \sqrt{2} + \sqrt{2} = 2 + 2\sqrt{2} \approx 4.828\). This can be verified by comparing the cost of \( C_* \) to the other two Hamiltonian cycles: for example, the cycle \( C = wxzyw \), which has total cost \( c(C) = 2 + \sqrt{2} + 1 + 1 \approx 5.414. \) The cycle \( C \) was constructed using the heuristic procedure below.
\( T \leftarrow \) an MST of \( G\) // Can use Kruska's algorithm
2
\( \widetilde{G} \gets \) a multigraph on \( V (G) \) where each edge of \( G \) is "doubled" with the same cost
3
\( \widetilde{C} \gets \) Eulerian circuit in \widetilde{G} // exists because every vertex in \( \widetilde{G} \) has even degree
4
return Hamiltonian cycle \(C \subset G\) with vertex order specified by \( \widetilde{C} \).
We may observe that although the cycle \( C\), despite being sub-optimal, is not that much more costly than \( C_* \). More precisely, the cost of \( C\) is less than twice the cost of \( C_* \), which turns out to be a general property of this metric TSP heuristic.
Metric TSP Factor-2 Approximation For any instance of metric TSP, letting \( C_* \) denote the optimal Hamiltonian cycle and \(C \) the Hamiltonian cycle returned by the heuristic above, we have
$$
c(C_*) \le c(C) \le 2 c(C_*).
$$
Thus, the 2-factor heuristic gives us a "solution" to metric TSP which is at most twice the cost of the optimal solution.
Note that the first inequality in the statmement of this theorem is obvious from the definition of \( C_* \), so we focus on the proving the second inequality.
Proof:
First observe that the optimal Hamiltonian cycle \( C_* \) contains some spanning tree \( T' \), namely the path obtained by deleting any edge from \( C_* \). Since \( T \) is a MST and the costs are nonnegative, we have
$$
c(T) \le c(T') \le c(C_*).
$$
Second, observe that our doubling construction implies
$$
c(\widetilde{C}) = 2 \cdot c(T).
$$
Finally, we must make use of the triangle inequality, which implies that
$$
c(C) \le c(\widetilde{C}),
$$
since each edge within \(C \) may be viewed as a "shortcut" along the path connecting its ends in \( \widetilde{C} \).
Putting it all together, we have
$$
c(C) \le c(\widetilde{C}) = 2 c(T) \le 2 c(C_*).
$$
Cayley's Formula
How many trees are there on \( n \) vertices? The question as we have posed it is vague: one must distinguish between labeled and unlabeled trees.
In general, the number of unlabeled objects is less than the number of labeled objects, but producing formulas for the number of labeled objects is much easier.
For example, the number of unlabeled graphs on \( n \) vertices equals \( 2^{\binom{n}{2}} \).
For \( n = 4 \), this tells us there are \( 64 \) labeled graphs.
However, many of these graphs are isomorphic; the number of unlabeled \( 4 \)-vertex graphs is just \( 11 \).
Returning to the problem of counting trees, let us start by considering the case of \( n = 4 \).
First, we determine the number of unlabeled trees.
We know that \( 4 \)-vertex tree must have at least two leaves.
Notice that the number of leaves cannot equal \( 4 \), as the sum over all vertex degrees must equal \( 6 \).
If the number of leaves is exactly \( 2 \), the only possibility up to isomorphism is a path of length \( 3 \).
If the number of leaves is exactly \( 3 \), the only possibility is a star.
Since there are just two isomorphism classes of \( 4 \)-vertex trees, it remains to count the number of ways in which we can assign labels from the set \( \{ 1,2,3,4 \} \) to the vertices.
For the star, a labelling is determined by the choice of the degree-\( 3 \) vertex; thus, there are \( 4 \) labeled stars.
For the paths, a labelling is determined by a sequential ordering of the labels; although there are \( 4! = 24 \) such orderings, reversing the order produces the same labeled tree, so there are exactly \( 12 \) labeled paths.
We show all \( 16 \) labeled trees below.
Our count of \( 16 = 4^{4-2} \) labeled \( 4 \)-vertex trees produced above is an instance of the following result.
Theorem (Cayley's Formula): For \( n \ge 2\), there are exactly \( n^{n-2} \) labeled \( n \)-vertex trees.
Prüfer Sequences
In this section, we will describe a bijective proof of Cayley's theorem, which establishes a one-to-one correspondence between the set of labeled trees on \( n \) vertices and the set of sequences of length \( n-2 \) with entries from \( \{1, 2, \dots, n\} \). Such a sequence will called a Prüfer sequence.
For ease of notation, we write \( [n] = \{ 1,\ldots , n \} \) and \( [n]^{(n-2)} \) for the set of all such sequences.
(In the next section, we will see a different proof of Cayley's theorem based on matrix algebra.)
Both the bijective correspondence described above and its inverse can both be described by simple algorithms. We we refer to these algorithms below as Prüfer encoding and the Prüfer decoding, respectively.
Prüfer Encoding (Tree to Sequence)
Let \( T \) be a tree with vertices labeled \( \{1, 2, \dots, n\} \). We construct a sequence \( S \) of length \( n-2 \) as follows:
Find the leaf (vertex of degree 1) with the smallest label.
Record the label of its unique neighbor as the next element in the sequence \( S \).
Delete the leaf and the edge connecting it to its neighbor from \( T \).
Repeat this process until exactly two vertices remain in the tree.
Because a tree on \( n \ge 2 \) vertices always has at least two leaves, this process is well-defined and always stops after \( n-2 \) steps, producing a sequence of length \( n-2 \).
Example: Constructing a Prüfer Sequence
Let's find the Prüfer sequence \( P(T) \) for the 7-vertex tree \( T \) shown below. Because there are \( n = 7 \) vertices, our final sequence will have exactly \( 7 - 2 = 5 \) elements.
We repeatedly find the leaf (degree-1 vertex) with the smallest label, record its unique neighbor, and then remove the leaf from the graph:
Step 1: The initial leaves are {2, 3, 5, 7}. The smallest is 2. Its neighbor is 1. We record \( 1 \) and delete vertex 2. Sequence so far: (1)
Step 2: The remaining leaves are {3, 5, 7}. The smallest is 3. Its neighbor is 4. We record \( 4 \) and delete vertex 3. Sequence so far: (1, 4)
Step 3: The remaining leaves are {5, 7}. The smallest is 5. Its neighbor is 4. We record \( 4 \) and delete vertex 5. Notice that deleting 5 turns vertex 4 into a new leaf! Sequence so far: (1, 4, 4)
Step 4: The current leaves are {4, 7}. The smallest is 4. Its neighbor is 6. We record \( 6 \) and delete vertex 4. Now vertex 6 becomes a leaf. Sequence so far: (1, 4, 4, 6)
Step 5: The current leaves are {6, 7}. The smallest is 6. Its neighbor is 1. We record \( 1 \) and delete vertex 6. Sequence so far: (1, 4, 4, 6, 1)
Exactly two vertices remain ({1, 7}), so the algorithm terminates. The final Prüfer sequence for this tree is \( S = (1, 4, 4, 6, 1) \).
Notice that the degree of any vertex in the tree is exactly one more than the number of times it appears in the sequence (e.g., vertex 4 appears twice in the sequence and has a degree of 3 in the original graph).
To produce a tree from an arbitrary sequence \( S = (u_1, \ldots , u_{n-2}) \in [n]^{n-2} \), we use the following algorithm.
Prüfer Decoding (Sequence to Tree)
Intialize a set of labels \( L \gets [ n ] \).
For each element \( i=1, \ldots , n-2 \):
Find the smallest \( v \in L \) not appearing in the partial sequence \( (u_i, \ldots , u_{n-2}) \).
Add an edge between \( v \) and \( u_i \).
Update \( L \gets L \setminus \{ v \} \).
After processing the entire sequence, exactly two vertices will have a degree of 1. Add a final edge between them.
Proof of Cayley's Formula (sketch): By induction on \( n \), one may check that, for any labeled tree \( T \), if we apply the Prüfer Encoding followed by the Prüfer Decoding, then we recover \( T \).
Similarly, for any sequence \( S \in [n]^{(n-2)} \), applying Prüfer Decoding and then Prüfer Encoding gives us back \( S \).
Thus, these procedures define bijective inverses of each other, and the number of labelled \( n \)-vertex trees equals the cardinality of the sequence space \( [n]^{(n-2)} \), which equals \( n^{n-2} \).
Deletion-Contraction and Kirchoff's Matrix-Tree Theorem
Let \( \tau(G) \) denote the number of spanning trees of a multigraph \( G \).
We define the edge contraction \( G/e \) as the multigraph obtained by deleting \( e \) and identifying its ends.
Note that this operation may produce loops or parallel edges.
Proposition: Let \( G \) be a multigraph, and let \( e \) be an edge that is not a loop. Then \( \tau(G) = \tau(G \setminus e) + \tau(G/e) \).
Proof: We can partition the spanning trees of \( G \) into two disjoint sets based on whether they contain the edge \( e \). The number of spanning trees of \( G \) that do not use \( e \) is exactly \( \tau(G \setminus e) \), and the number of spanning trees of \( G \) that use \( e \) is \( \tau(G/e) \). Summing these disjoint cases completes the proof.
While this recursive formula provides an algorithm to compute the number of spanning trees, it is exponential and thus not a very efficient method in practice. We will see a better way using matrix determinants.
The Adjacency and Laplacian Matrices
Let \( G \) be a multigraph with \( V(G)=\{1,2,\dots,n\} \). The adjacency matrix of \( G \) is an \( n \times n \) matrix \( A=(a_{ij})_{i,j=1}^n \) defined by \( a_{ij} = \# \) edges with ends \( i, j \).
The Laplacian matrix of a graph is defined by \( L=(l_{ij}) \), where:
$$ l_{ij} = \begin{cases} \sum_{k \neq i} a_{ik} & \text{if } i=j \\ -a_{ij} & \text{otherwise} \end{cases} $$
Note that the rows and columns of the Laplacian sum to 0, and hence \( \det L = 0 \).
Kirchhoff's Matrix Tree Theorem: Let \( G \) be a multigraph, let \( L \) be its Laplacian matrix, let \( k \in \{1,2,\dots,n\} \), and let \( L(k) \) denote the matrix obtained from \( L \) by deleting the \( k^{\text{th}} \) row and \( k^{\text{th}} \) column. Then \( \tau(G) = \det L(k) \).
Notice that \( \det L(k) = 0 \) if \( G \) is disconnected.
Example
Consider a "diamond" graph \( G \) on 4 vertices with a central edge \( e \).
We can observe by counting that \( \tau(G) = 8 \) (there are 4 spanning trees containing \( e \), and 4 not containing \( e \)).
The Laplacian matrix \( L \) and the submatrix \( L(1) \) (obtained by deleting the first row and column) are given by:
$$ L = \begin{pmatrix} 3 & -1 & -1 & -1 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 2 & 0 \\ -1 & -1 & 0 & 2 \end{pmatrix}, \quad L(1) = \begin{pmatrix} 3 & -1 & -1 \\ -1 & 2 & 0 \\ -1 & 0 & 2 \end{pmatrix} $$
Calculating the determinant yields \( \det L(1) = 3(4-0) - (-1)(-2-0) + (-1)(0-(-2)) = 12 - 2 - 2 = 8 \), verifying the theorem.
Proof of Kirchhoff's Matrix Tree Theorem
First, we establish a useful lemma regarding determinants.
Lemma: For any square matrix \( M \in \mathbb{R}^{n\times n} \) and any index \( 1\le v \le n\), we have \( \det(M + E_{vv}) = \det(M) + \det M(v) \), where \( E_{vv}\in \mathbb{R}^{n\times n} \) is the with 1 in entry \( (v,v) \) and 0 elsewhere.
Proof: For convenience (and without loss of generality), we assume \( v=1 \).
The proof we gave in class used cofactor expansion along the first row. Alternatively, we may utilize a standard formula for the determinant as an alternating sum over all \( n! \) permutations \( \sigma \) of the columns:
$$ \det(M+E_{11}) = \sum_{\sigma} \operatorname{sgn}(\sigma) \prod_{i=1}^{n}(M+E_{11})_{i\sigma(i)} $$
(Here, \( \Pi_{i=1}^n a_i = a_1 \cdot a_2 \cdots \cdot a_n \) denotes an iterated product.)
We can split the sum above into two parts: permutations where \( \sigma(1)=1 \), and permutations where \( \sigma(1) \neq 1 \).
$$ = \sum_{\sigma:\sigma(1)=1} \operatorname{sgn}(\sigma)(M_{11}+1) \prod_{i=2}^{n} M_{i\sigma(i)} + \sum_{\sigma:\sigma(1) \neq 1} \operatorname{sgn}(\sigma) \prod_{i=1}^{n} M_{i\sigma(i)} $$
Distributing the \( +1 \) and recombining the sum over all permutations for the \( M \) terms yields:
$$ = \sum_{\sigma} \operatorname{sgn}(\sigma) \prod_{i=1}^{n} M_{i\sigma(i)} + \sum_{\sigma:\sigma(1)=1} \operatorname{sgn}(\sigma) \prod_{i=2}^{n} M_{i\sigma(i)} $$
This evaluates exactly to \( \det(M) + \det M(1) \).
Proof of Matrix Tree Theorem: If \( G \) is disconnected, then \( \tau(G)=0=\det L(k) \).
Thus, we may assume \( G \) is connected and loopless.
If \( |E(G)|=0 \), then \( \tau(G)=1=\det L(k) \).
We proceed by induction on the number of edges, \( |E(G)| \).
Recall the deletion-contraction identity: \( \tau(G) = \tau(G \setminus e) + \tau(G/e) \).
To finish the induction, it is enough to show that \( \det L_G(u) = \det L_{G \setminus e}(u) + \det L_{G/e}(w) \), where \( e=uv \) and \( w \) is the new vertex of \( G/e \).
Notice that the Laplacian matrices satisfy \( L_G(u) = L_{G \setminus e}(u) + E_{vv} \).
Applying our determinant lemma, we have:
$$ \det L_G(u) = \det[L_{G \setminus e}(u) + E_{vv}] = \det L_{G \setminus e}(u) + \det L_{G \setminus e}(u,v) $$
Observe that \( \det L_{G \setminus e}(u,v) \) is precisely the determinant of the Laplacian of the contracted graph, \( \det L_{G/e}(w) \).
This matches the deletion-contraction structure and completes the proof.
Proof of Cayley's Formula via Matrix-Tree Theorem: We can compute \( \tau(K_n) \) by taking the determinant of the Laplacian matrix of the complete graph, with one row and column removed. This leaves an \( (n-1) \times (n-1) \) matrix with \( n-1 \) on the main diagonal and \( -1 \) everywhere else:
$$ \tau(K_n) = \det \begin{pmatrix} n-1 & -1 & \dots & -1 \\ -1 & n-1 & \dots & -1 \\ \vdots & \vdots & \ddots & \vdots \\ -1 & -1 & \dots & n-1 \end{pmatrix} $$
We can simplify this matrix using row operations. By adding rows \( 2, 3, \dots, n-1 \) to row 1, we obtain a top row consisting entirely of 1s:
$$ = \det \begin{pmatrix} 1 & 1 & \dots & 1 \\ -1 & n-1 & \dots & -1 \\ \vdots & \vdots & \ddots & \vdots \\ -1 & -1 & \dots & n-1 \end{pmatrix} $$
Next, by adding row 1 to all other rows, we clear out the negative ones below the first row, resulting in an upper triangular matrix:
$$ = \det \begin{pmatrix} 1 & 1 & \dots & 1 \\ 0 & n & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & n \end{pmatrix} $$
The determinant of an upper triangular matrix is the product of its diagonal entries. The diagonal consists of a single 1 and \( n-2 \) copies of \( n \). Therefore, the determinant is \( n^{n-2} \).
