Admin: Create page from Chapter 2 notes on Trees and Distance (via create-page on MediaWiki MCP Server)

2026-06-14T19:09:52Z

Create page from Chapter 2 notes on Trees and Distance (via create-page on MediaWiki MCP Server)

New page

'''Chapter 2: Trees and Distance'''

''Source: [[Introduction to Graph Theory]], 2nd Edition, by Douglas B. West''

==Overview==

Chapter 2 of West's ''Introduction to Graph Theory'' develops the theory of trees, one of the most fundamental structures in graph theory. Trees arise naturally in applications involving data storage, searching, communication networks, and optimization. The chapter is organized into three sections: basic structural properties and distance concepts (2.1), enumeration and counting of spanning trees (2.2), and optimization problems involving trees such as minimum spanning trees and shortest paths (2.3).

==2.1 Basic Properties==

===Definitions===

* '''Acyclic graph''': A graph with no cycle.
* '''Forest''': An acyclic graph.
* '''Tree''': A connected acyclic graph.
* '''Leaf (pendant vertex)''': A vertex of degree 1.
* '''Spanning subgraph''': A subgraph of G with vertex set V(G).
* '''Spanning tree''': A spanning subgraph that is a tree.

Examples: A tree is a connected forest, and every component of a forest is a tree. Paths are trees; a tree is a path if and only if its maximum degree is 2. A '''star''' is a tree consisting of one vertex adjacent to all others (the biclique K1,n-1).

===Properties of Trees===

'''Lemma 2.1.3.''' Every tree with at least two vertices has at least two leaves. Deleting a leaf from an n-vertex tree produces a tree with n − 1 vertices.

'''Theorem 2.1.4 (Characterization of Trees).''' For an n-vertex graph G (with n ≥ 1), the following are equivalent (and characterize trees):

* A) G is connected and has no cycles.
* B) G is connected and has n − 1 edges.
* C) G has n − 1 edges and no cycles.
* D) For every u, v in V(G), G has exactly one u,v-path.

This is one of the most important results in the chapter. Any two of the three properties {connected, acyclic, n − 1 edges} imply the third.

'''Corollary 2.1.5.'''
* (a) Every edge of a tree is a cut-edge.
* (b) Adding one edge to a tree forms exactly one cycle.
* (c) Every connected graph contains a spanning tree.

'''Proposition 2.1.6 (Edge exchange in spanning trees).''' If T, T' are spanning trees of a connected graph G and e is in E(T) − E(T'), then there exists an edge e' in E(T') − E(T) such that T − e + e' is a spanning tree.

'''Proposition 2.1.7.''' The symmetric version: if e is in E(T) − E(T'), there exists e' in E(T') − E(T) such that T' + e − e' is also a spanning tree.

'''Proposition 2.1.8.''' If T is a tree with k edges and G is a simple graph with minimum degree δ(G) ≥ k, then T is a subgraph of G. This means that graphs with sufficiently high minimum degree contain all small trees as subgraphs.

===Distance in Trees and Graphs===

'''Definition 2.1.9.'''
* '''Distance''' d(u,v): The least length of a u,v-path (infinity if no such path exists).
* '''Diameter''' diam(G): max over all u,v of d(u,v).
* '''Eccentricity''' ε(u): max over all v of d(u,v).
* '''Radius''' rad(G): min over all u of ε(u).

'''Example 2.1.10.''' The Petersen graph has diameter 2. The hypercube Qk has diameter k. The cycle Cn has diameter ⌊n/2⌋. For n ≥ 3, the n-vertex tree of least diameter is the star (diameter 2, radius 1), and the one of largest diameter is the path (diameter n − 1, radius ⌈(n−1)/2⌉).

'''Theorem 2.1.11.''' If G is a simple graph with diam(G) ≥ 3, then diam(G̅) ≤ 3 (where G̅ is the complement of G).

'''Definition 2.1.12.''' The '''center''' of a graph G is the subgraph induced by the vertices of minimum eccentricity.

'''Theorem 2.1.13 (Jordan, 1869).''' The center of a tree is a vertex or an edge. The proof uses induction: deleting all leaves preserves the center, and the process reduces the tree until one or two vertices remain.

===Wiener Index===

'''Definition.''' The '''Wiener index''' D(G) = sum of d(u,v) over all pairs u,v. This quantity has applications in chemistry (studying boiling points of paraffin molecules).

'''Theorem 2.1.14.''' Among trees with n vertices, the Wiener index D(T) is:
* Minimized uniquely by the star K1,n−1, with value (n−1)2.
* Maximized uniquely by the path Pn, with value C(n+1, 3).

'''Lemma 2.1.15.''' If H is a subgraph of G, then dG(u,v) ≤ dH(u,v) for all u, v.

'''Corollary 2.1.16.''' If G is a connected n-vertex graph, then D(G) ≤ D(Pn).

===Disjoint Spanning Trees (optional)===

Edge-disjoint spanning trees provide alternate routes when an edge in the primary tree fails. The section discusses the Tutte [1961a] and Nash-Williams [1961] characterization of graphs having k pairwise edge-disjoint spanning trees.

An application to the game '''Bridg-it''' is presented:

'''Theorem 2.1.17.''' Player 1 has a winning strategy in Bridg-it. The proof uses the existence of two edge-disjoint spanning trees and Proposition 2.1.6 to show that Player 1 can always reconnect after Player 2's cuts.

==2.2 Spanning Trees and Enumeration==

===Enumeration of Trees===

The section addresses the counting question: among the 2C(n,2) simple graphs with vertex set [n], how many are trees?

With small vertex sets: vertex set [3] yields 3 trees, [4] yields 16 trees, [5] yields 125 trees. The pattern is nn−2.

'''Cayley's Formula (Theorem 2.2.3, 1889).''' For a set S of size n in the natural numbers, there are nn−2 trees with vertex set S.

The proof uses '''Prüfer codes''', establishing a bijection between labeled trees on n vertices and sequences of length n − 2 from the vertex set.

===Prüfer Code===

'''Algorithm 2.2.1 (Prüfer code production).''' Given a tree T with vertex set S:
* At each step, delete the least remaining leaf and record the neighbor of that leaf.
* After n − 2 iterations, a list f(T) = (a1, ..., an−2) of length n − 2 is produced.

The code can be reversed to reconstruct the tree: starting with the set S of isolated vertices, edges are added one at a time using the code entries and the current set of unmarked vertices.

'''Corollary 2.2.4.''' Given positive integers d1, ..., dn summing to 2n − 2, there are exactly (n−2)! / Π((di − 1)!) trees with vertex set [n] such that vertex i has degree di. This follows because vertex x appears dT(x) − 1 times in the Prüfer code.

===Spanning Trees in Graphs===

'''Definition 2.2.7 (Contraction).''' Contraction of edge e with endpoints u, v replaces u and v with a single vertex whose incident edges are the edges other than e that were incident to u or v.

'''Proposition 2.2.8 (Deletion-Contraction Recurrence).''' Let τ(G) denote the number of spanning trees of G. If e in E(G) is not a loop, then:

:τ(G) = τ(G − e) + τ(G · e)

where G − e is edge deletion and G · e is edge contraction. This gives a recursive method for computing spanning tree counts.

'''Remark 2.2.10.''' If G is a connected loopless graph with no cycle of length at least 3, then τ(G) is the product of the edge multiplicities.

===The Matrix Tree Theorem===

'''Theorem 2.2.12 (Matrix Tree Theorem, Kirchhoff 1847).''' Given a loopless graph G with vertex set v1, ..., vn, let ai,j be the number of edges with endpoints vi and vj. Let Q be the matrix in which entry (i,j) is −ai,j when i ≠ j and is d(vi) when i = j. If Q* is a matrix obtained by deleting row s and column t of Q, then:

:τ(G) = (−1)s+t det(Q*)

The proof proceeds in two steps:
# If D is an orientation of G and M is the incidence matrix, then Q = MMT.
# Every (n−1)-by-(n−1) submatrix B of M corresponding to n − 1 edges forms a spanning tree if and only if det(B) = ±1; otherwise det(B) = 0.

The Matrix Tree Theorem provides a computationally efficient method (O(n3)) for counting spanning trees, since determinants of n-by-n matrices can be computed in polynomial time.

===Graceful Labelings (optional)===

A '''graceful labeling''' of a graph G with m edges assigns distinct labels from {0, 1, ..., m} to the vertices so that the induced edge labels |f(u) − f(v)| are distinct (and hence are exactly {1, 2, ..., m}).

'''The Graceful Tree Conjecture (Ringel–Kotzig Conjecture):''' Every tree has a graceful labeling. This remains one of the major open problems in graph theory. It has been verified for many special classes of trees (paths, caterpillars, trees with at most 4 leaves, trees with at most 27 vertices) but the general case remains open.

A graceful labeling of Kn decomposes K2n+1 into 2n + 1 copies of the tree, providing a connection to decomposition problems.

==2.3 Optimization and Trees==

===Minimum Spanning Trees===

When edges of a graph carry weights (costs), a natural optimization problem is to find a spanning tree of minimum total weight.

'''Definition.''' Given a weighted connected graph G with edge weights w: E(G) → ℝ, the '''minimum spanning tree (MST)''' is a spanning tree T that minimizes the total weight sum of w(e) over all e in E(T).

Two classical greedy algorithms solve this problem:

'''Kruskal's Algorithm (1956):'''
# Sort the edges by weight in nondecreasing order.
# Consider edges one at a time; add the current edge to the tree if it does not create a cycle with previously selected edges.
# Stop when n − 1 edges have been selected.

'''Prim's Algorithm (1957):'''
# Start from any vertex s.
# At each step, add the minimum-weight edge connecting the current tree to a vertex not yet in the tree.
# Continue until all vertices are included.

Both algorithms produce a minimum spanning tree and run efficiently: Kruskal's in O(m log n) and Prim's in O(m + n log n) with appropriate data structures.

'''Theorem.''' An edge e belongs to some minimum spanning tree if and only if e is not the unique heaviest edge in some cycle of G.

'''Theorem.''' If all edge weights are distinct, the minimum spanning tree is unique.

===Shortest Paths===

'''Definition.''' The '''weighted distance''' from u to v in a weighted graph is the minimum total weight of a u,v-path.

'''Dijkstra's Algorithm (1959):''' Finds shortest paths from a single source vertex s to all other vertices in a graph with nonnegative edge weights.

# Initialize d(s) = 0 and d(v) = ∞ for all other vertices.
# Maintain a set S of vertices whose shortest distance is known.
# At each step, add to S the vertex u not in S with smallest d(u).
# Update distances: for each neighbor v of u, set d(v) = min(d(v), d(u) + w(u,v)).

Dijkstra's algorithm runs in O(n2) with a simple implementation or O(m + n log n) with a Fibonacci heap.

'''Chinese Postman Problem:''' Find a closed walk of minimum total weight that traverses every edge at least once. For Eulerian graphs, the answer is the total weight of all edges. For non-Eulerian graphs, one must duplicate some edges; the optimal solution involves finding a minimum-weight perfect matching on the vertices of odd degree.

===Network Flows and Trees===

The relationship between trees and network optimization extends to problems involving flows, cuts, and connectivity. Trees provide the structural foundation for many network algorithms, and spanning tree structures appear in the simplex method for network flow problems.

==Summary of Key Results==

{| class="table wikitable"
|-
! Result !! Significance
|-
| Theorem 2.1.4 (Tree characterization) || Four equivalent definitions of trees; any two of {connected, acyclic, n−1 edges} imply the third
|-
| Theorem 2.1.13 (Jordan) || Center of a tree is a vertex or an edge
|-
| Theorem 2.1.14 (Wiener index extremes) || Star minimizes and path maximizes the sum of distances
|-
| Theorem 2.2.3 (Cayley's Formula) || nn−2 labeled trees on n vertices, proved via Prüfer code bijection
|-
| Theorem 2.2.12 (Matrix Tree Theorem) || Number of spanning trees equals any cofactor of the Laplacian matrix
|-
| Proposition 2.2.8 (Deletion-contraction) || τ(G) = τ(G−e) + τ(G·e), a recursive counting method
|-
| Kruskal's and Prim's Algorithms || Greedy algorithms correctly find minimum spanning trees
|-
| Dijkstra's Algorithm || Efficient single-source shortest path algorithm for nonnegative weights
|}

=Flags=

{{ReadingFlag}}

Introduction to Graph Theory/Trees and Distance - Revision history

Admin: Create page from Chapter 2 notes on Trees and Distance (via create-page on MediaWiki MCP Server)