An introduction to more advanced topics in graph theory.

Preface

Since I have already encountered the basics of graph theory many times in courses such as discrete mathematics, circuit theory, and algorithms, I will not repeat the basic concepts here and treat them as prerequisites. Only the extended material is covered.

Review of Basic Concepts

• In general, 𝛿(𝐺) denotes the minimum degree of graph 𝐺, and Δ(𝐺) denotes the maximum degree
• Induced subgraph: if 𝑉(𝐺) ⊆ 𝑉(𝐺′) and 𝐸(𝐺) ⊆ 𝐸(𝐺′), and moreover 𝐸(𝐺) = 𝐸 (𝐺′) ∩ , then 𝐺 is an induced subgraph of 𝐺′
• If in addition 𝑉(𝐺) = 𝑉(𝐺′), then 𝐺 is a spanning subgraph of 𝐺′
• If every vertex in the graph has the same constant degree 𝑟, the graph is called 𝑟-regular (r-regular graph)
• Simple graph: an undirected graph with no self-loops and no multiple edges is called a simple graph.
• Handshaking theorem (Leonhard Euler 1736): given an undirected graph 𝐺 = (𝑉, 𝐸),
  • Corollary: in an undirected graph, the number of vertices of odd degree is always even

Graph: Isomorphism and Score

Graph isomorphism: if for a graph 𝐺= 𝑉, 𝐸 and a graph G’=(V’, E’) there exists a bijection such that for any 𝑥, 𝑦∈𝑉 we have if and only if 𝑓(𝑥), 𝑓(𝑦) ∈𝐸′, then we say that graphs 𝐺 and 𝐺′ are isomorphic.

Counting Graphs

• The number of graphs on 𝑛 vertices is — each edge of the complete graph is either present or absent

• Any graph G=(V, E) is isomorphic to at most n! distinct graphs on V. From this we obtain the inequality
  $\frac{2^{\binom{n}{2}}}{n!} \leq x \leq 2^{\binom{n}{2}}$ .

Graph Score

• Definition: the degree sequence of a graph G is called the score of G.
• Relation to graph isomorphism: isomorphic graphs necessarily have the same score. However, graphs with the same score are not necessarily isomorphic
• Existence: not every finite sequence can be the score of a graph. Whether a sequence is the score of some graph can be decided using the Score Theorem: let $D = (d_1, d_2, \ldots, d_n)$ be a sequence of natural numbers with n>1 and $d_1 \leq d_2 \leq \cdots \leq d_n$ , and let D’ be the sequence $(d_1', d_2', \ldots, d_{n - 1}')$ where $d_{i}'=\begin{cases}d_{i}&\text{if }i < n - d_{n}\\d_{i}-1&\text{if }i \geq n - d_{n}\end{cases}$. Then D is a graph score if and only if D’ is a graph score.
• Proof:
  • if: add a vertex to D’ to construct D
  • only if: D can be transformed into an isomorphic graph such that the last vertices are connected to ; deleting these edges yields D’

Applications of Handshake lemma

• Sperner’s lemma (Sperner, 1928): subdivide any n-dimensional simplex (𝑛-simplex) and color it with 𝑛+ 1 colors; then under any proper coloring scheme of the subdivided simplex, there must be a cell that contains all the distinct colors.

• Planar Brouwer’s fixed point theorem: Every continuous function has a fixed point.

• Theorem (Smith): in a 3-regular graph, the number of Hamiltonian cycles containing any given edge 𝑒 is even.

Tree

Characterizations of Trees

• Tree-growing lemma: for a graph 𝐺 and a leaf 𝑣 of 𝐺, the following statements are equivalent
  • G is a tree
  • G - v is a tree
• Equivalent characterizations of a tree:
  • II. Unique paths: for any two vertices u , , there exists a unique path from u to v.
  • III. Minimal connected graph: G is connected, and removing any single edge makes it disconnected.
  • • IV. Maximal acyclic graph: G contains no cycle, but adding any single edge yields a graph G+e (where ) that contains a cycle.
  • V. Euler’s formula: G is connected and |V|=|E|+1

Counting Trees

Two trees 𝑇, 𝑇′ are “equal” if and only if the edge set of tree 𝑇 equals the edge set of tree 𝑇′.

Cayley’s Theorem

(Cayley’s formula): there are distinct trees on 𝑛 vertices.

1. Core proposition: let be positive integers whose sum is . Then in the graph (the complete graph, in which every pair of the vertices is joined by an edge), the number of spanning trees in which vertex has degree exactly () equals $$\frac{(n - 2)!}{(d_1 - 1)!(d_2 - 1)!\cdots(d_n - 1)!}$$
2. Proof
   • Base case: for n = 1, 2 the proposition clearly holds. When n = 1 the graph has only one vertex, which can be regarded as a degenerate tree; when n = 2 there is a single edge joining the two vertices, so there is only one tree shape, which agrees with the formula above.
   • Inductive step (n > 2): since $d_1 + d_2 + \cdots + d_n = 2n - 2$ , by the handshaking theorem there must exist some i with $d_i = 1$; without loss of generality let $d_n = 1$. For $1\leq i\leq n - 1$ , define $T_i$ to be the set of spanning trees of $K_n$ that contain the edge $\{i, n\}$. From each tree in $T_i$, delete the vertex $v_n$ to obtain $T_i'$ ; $T_i'$ is a spanning tree of $K_{n - 1}$ whose vertex degrees are $d_1, d_2, \cdots, d_{i - 1}, d_i - 1, d_{i + 1}, \cdots, d_{n - 1}$
     • By the induction hypothesis, we obtain $|T_i| = |T_i'| = \frac{(n - 3)!}{(d_1 - 1)!\cdots(d_{i - 1}-1)!(d_i - 2)!(d_{i + 1}-1)!\cdots(d_{n - 1}-1)!}$, which can be rewritten as $|T_i| = \frac{(n - 3)!(d_i - 1)}{(d_1 - 1)!(d_2 - 1)!\cdots(d_{n - 1}-1)!}$
     • Since $|T|=\sum_{i = 1}^{n}|T_i|=\sum_{i = 1}^{n - 1}\frac{(n - 3)!(d_i - 1)}{(d_1 - 1)!(d_2 - 1)!\cdots(d_{n - 1}-1)!}$, after a series of algebraic manipulations, we sum over all tuples satisfying $d_1 + d_2 + \cdots + d_n = 2n - 2$ and $d_i\geq1$, i.e. over all such $d_1, d_2, \cdots, d_n$ , giving $\left|T\left(K_{n}\right)\right|=\sum_{\substack{d_{1}, d_{2}, \cdots, d_{n} \geq 1 \\ d_{1}+d_{2}+\cdots+d_{n}=2 n - 2}} \frac{(n - 2)!}{(d_{1}-1)!(d_{2}-1)!\cdots(d_{n}-1)!}$ Let $k_i = d_i - 1$; then $k_1 + k_2 + \cdots + k_n = n - 2$ and $k_i\geq0$, and the expression becomes $\sum_{\substack{k_{1}+k_{2}+\cdots+k_{n}=n - 2 \\ k_{1}, \cdots, k_{n} \geq 0}} \frac{(n - 2)!}{k_{1}!k_{2}!\cdots k_{n}!}$, which by the multinomial theorem equals $\underbrace{(1 + 1+\cdots+1)^{n - 2}}_{n - 2}=n^{n - 2}$. This proves that the number of distinct trees on n vertices is $n^{n - 2}$ .

Tree Isomorphism

Rooted Tree Isomorphism

Definition: 𝑇, 𝑟 ≅′ (𝑇′, 𝑟′):

• 𝑓: 𝑉(𝑇) → 𝑉(𝑇′) is an isomorphism 𝑇 ≅ 𝑇′,
• 𝑓(𝑟) = 𝑟′
• The relation ≅′ is strictly stronger than the relation ≅.

Using an encoding, one proves that $(T, r) \cong'(T', r')$ if and only if they have the same encoding.

Proof:
– Sufficiency: follows from the definition of rooted tree isomorphism and the encoding.
– Necessity: decode, i.e., recover the original tree structure from the encoding.
The encoding of any rooted tree necessarily has the general form 0𝑆1, where

$$𝑆 = 𝑆1𝑆2 … 𝑆𝑡$$

𝑆1 is the shortest prefix of 𝑆 with equal numbers of 0s and 1s, 𝑆2 is the second shortest 0/1-balanced prefix, and so on.
The rooted tree can be recovered from this, and clearly such rooted trees must be isomorphic.

Unrooted Tree Isomorphism

Problem reduction: general tree isomorphism ⊑ rooted tree isomorphism

• Distance: for two vertices u ,v in a graph G, disc(1,1) denotes the length of the shortest path between 𝑢, 𝑣.
• Eccentricity: for a graph 𝐺 and a vertex 𝑣 in it, the eccentricity is defined as:

$$ex_{G}(v)=max _{u \in G} dis_{G}(u, v)$$

• Center: the set of vertices of graph 𝐺 with the minimum eccentricity is called the center, denoted by 𝐶(𝐺).

Property: for a tree 𝑇 = (𝑉, 𝐸), 𝐶(𝑇) contains at most 2 vertices. Moreover, if 𝐶(𝑇) = 𝑥, 𝑦 , then 𝑥, 𝑦 ∈ 𝐸

If 𝐶(𝑇) contains only a single vertex 𝑣: output the encoding #(𝑻, 𝒗) of the rooted tree (𝑇, 𝑣).
• 𝐶(T) = {𝑥1, 𝑥2}: let 𝑒 = {𝑥1, 𝑥2}
𝑇 − 𝑒: has exactly two connected components 𝑇1, 𝑇2. Without loss of generality let 𝑥1 ∈ 𝑉(𝑇1), 𝑥2 ∈ 𝑉(𝑇2).

• Compute #(𝑇1, 𝑥1) and #(𝑇2, 𝑥2)
• If #(𝑇1, 𝑥1) ≤ #(𝑇2, 𝑥2), output #(𝑻, 𝒙𝟏)
• Otherwise, output # (𝑻, 𝒙𝟐)

The proof then proceeds as for the rooted tree encoding.

---

Translated from the Chinese original.