Foundations of Graph Theory, Degree Sequences & Handshaking Theorems

1. The Mathematical Definition of a Graph

Graph theory is the mathematical framework dedicated to modeling pairwise relations between objects. Historically founded by Leonhard Euler in 1736 with his resolution of the Königsberg bridge problem, a graph abstracts away physical geometries to focus purely on topological connectivity.

Definition 1.1 (Graph): A graph $G$ is an ordered triple $G = (V(G), E(G), \psi_G)$ (or simply an ordered pair $G = (V, E)$ when unambiguous) consisting of:

1. A non-empty set $V(G) = \{v_1, v_2, \dots, v_n\}$ whose elements are called vertices (or nodes). The cardinality $|V(G)| = n$ is the order of $G$.

2. A set $E(G) = \{e_1, e_2, \dots, e_m\}$ whose elements are called edges (or lines). The cardinality $|E(G)| = m$ is the size of $G$.

3. An incidence function $\psi_G: E(G) \to \mathcal{P}_2(V(G)) \cup V(G)$ that associates each edge $e \in E(G)$ with an unordered pair of vertices $\{u, v\} \subseteq V(G)$.

If $\psi_G(e) = \{u, v\}$, we say that edge $e$ joins vertices $u$ and $v$. Vertices $u$ and $v$ are called the endpoints of $e$. Furthermore:

• Vertices $u$ and $v$ are said to be adjacent (or neighbors), denoted $u \sim v$.

• The edge $e$ and each of its endpoint vertices $u, v$ are said to be incident with each other.

2. Edge Typologies and Graph Classifications

Definition 1.2 (Self-Loops and Multiple Edges):

1. A self-loop (or loop) is an edge whose endpoints are identical: $\psi_G(e) = \{u, u\} = \{u\}$.

2. Multiple edges (or parallel edges) are two or more distinct edges $e_1, e_2 \in E(G)$ ($e_1 \ne e_2$) having identical endpoints: $\psi_G(e_1) = \psi_G(e_2) = \{u, v\}$.

Based on the permissible edge configurations, we classify graphs into distinct categories:

• Simple Graph: A graph having neither loops nor parallel edges. In a simple graph, every edge can be identified directly with a 2-element subset $\{u, v\} \in \binom{V}{2}$, and $E \subseteq \binom{V}{2}$.

• Multigraph: A graph that permits multiple edges between pairs of vertices, but contains no loops.

• Pseudograph: A general graph that permits both multiple edges and self-loops.

• Finite vs. Infinite Graph: A graph is finite if both $V(G)$ and $E(G)$ are finite sets. Throughout this textbook, all graphs are assumed to be finite unless explicitly stated otherwise.

• Null Graph (Empty Graph): A graph with an edge set $E = \emptyset$, denoted $N_n$ for $n$ isolated vertices.

• Trivial Graph: A graph containing exactly one vertex and no edges: $V = \{v\}$, $E = \emptyset$ ($K_1$).

1. Degree of a Vertex and Neighborhoods

Definition 1.3 (Open and Closed Neighborhoods): Let $G = (V, E)$ be a simple graph and $v \in V$.

1. The open neighborhood of $v$, denoted $N(v)$ or $N_G(v)$, is the set of all vertices adjacent to $v$:

2. The closed neighborhood of $v$, denoted $N[v]$, includes $v$ itself:

Definition 1.4 (Degree of a Vertex): The degree (or valency) of a vertex $v \in V(G)$, denoted $\deg(v)$, $\deg_G(v)$, or $d(v)$, is the number of edges incident with $v$. In pseudographs, a self-loop contributes 2 to the degree of its incident vertex (since both endpoints meet at $v$).

Extreme Degrees:

• The minimum degree of $G$ is $\delta(G) = \min \{ \deg(v) : v \in V \}$.

• The maximum degree of $G$ is $\Delta(G) = \max \{ \deg(v) : v \in V \}$.

• A vertex $v$ with $\deg(v) = 0$ is called an isolated vertex.

• A vertex $v$ with $\deg(v) = 1$ is called a pendant vertex (or leaf).

2. Euler's Handshaking Lemma

The very first theorem of graph theory, established by Leonhard Euler in 1736:

Theorem 1.1 (Euler's Handshaking Lemma): Let $G = (V, E)$ be any graph with vertex set $V$ and edge set $E$. The sum of the degrees of all vertices in $G$ is equal to twice the number of edges:

Complete Formal Proof (Double Counting):

Consider the set of all incidence pairs:

We count the cardinality $|\mathcal{I}|$ in two distinct ways:

1. Summing by vertices:

For each fixed vertex $v \in V$, the number of incident edges is by definition $\deg(v)$ (with loops counted twice). Summing over all vertices:

2. Summing by edges:

For each fixed edge $e \in E$, $e$ has exactly two endpoints (either two distinct vertices $u \ne v$, or one vertex counted twice if $e$ is a loop). Therefore, each edge contributes exactly 2 incidence pairs to $\mathcal{I}$. Summing over all edges:

Equating the two counts yields:

3. The Odd Degree Corollary

Corollary 1.1 (The Handshaking Corollary): In every graph $G$, the number of vertices having odd degree is even.

Complete Formal Proof:

Partition the vertex set $V$ into two disjoint subsets:

By the Handshaking Lemma:

Rearranging:

Notice that $2 |E|$ is an even integer. Furthermore, each term $\deg(v)$ in $\sum_{v \in V_{\text{even}}} \deg(v)$ is even, so the sum of even integers is even. The difference of two even integers is even:

The left side is a sum of odd integers. A sum of odd integers is even if and only if the number of terms in the sum is even. Therefore, $|V_{\text{odd}}|$ must be an even integer. $\blacksquare$

1. Complete Graphs $K_n$

Definition 1.5 (Complete Graph): A complete graph on $n$ vertices, denoted $K_n$, is a simple graph in which every pair of distinct vertices is connected by an edge.

• Number of vertices: $|V(K_n)| = n$.

• Number of edges: $|E(K_n)| = \binom{n}{2} = \frac{n(n - 1)}{2}$.

• Degree of each vertex: $\deg(v) = n - 1$ for all $v \in V(K_n)$.

2. Regular Graphs

Definition 1.6 ($k$-Regular Graph): A graph $G$ is called $k$-regular if every vertex has the same degree $k$:

By the Handshaking Lemma, for any $k$-regular graph on $n$ vertices:

A necessary condition for the existence of a $k$-regular graph on $n$ vertices is that $n \cdot k$ must be an even integer (i.e., if $k$ is odd, $n$ must be even).

3. Bipartite Graphs and Complete Bipartite Graphs $K_{m,n}$

Definition 1.7 (Bipartite Graph): A graph $G = (V, E)$ is bipartite if its vertex set $V$ can be partitioned into two disjoint non-empty sets $V_1$ and $V_2$ ($V = V_1 \cup V_2$, $V_1 \cap V_2 = \emptyset$) such that every edge in $E$ joins a vertex in $V_1$ to a vertex in $V_2$. No edge connects two vertices within the same part $V_1$ or $V_2$.

Definition 1.8 (Complete Bipartite Graph $K_{m, n}$): A complete bipartite graph, denoted $K_{m, n}$, is a bipartite graph with partition sets of sizes $|V_1| = m$ and $|V_2| = n$ such that every vertex in $V_1$ is connected to every vertex in $V_2$.

• Number of vertices: $|V(K_{m,n})| = m + n$.

• Number of edges: $|E(K_{m,n})| = m \cdot n$.

• Star Graph: $K_{1, n}$ consists of one central vertex connected to $n$ leaves.

4. Hypercube Graphs $Q_k$

Definition 1.9 ($k$-Dimensional Hypercube $Q_k$): The $k$-cube $Q_k$ is the simple graph whose vertices are all binary strings of length $k$:

Two vertices are adjacent if and only if their binary strings differ in exactly one coordinate (Hamming distance 1).

• Number of vertices: $|V(Q_k)| = 2^k$.

• Degree of each vertex: $\deg(v) = k$ (every $Q_k$ is $k$-regular).

• Total edges: $|E(Q_k)| = \frac{2^k \cdot k}{2} = k \cdot 2^{k-1}$.

• $Q_k$ is bipartite (partitioned by strings of even vs. odd Hamming weight).

1. Degree Sequences and the Realizability Problem

Definition 1.10 (Degree Sequence): Let $G$ be a simple graph of order $n$. The degree sequence of $G$ is a monotonic non-increasing sequence of non-negative integers:

where each $d_i = \deg(v_i)$ for some labeling of vertices $V(G) = \{v_1, \dots, v_n\}$.

The Graphical Realizability Question:

Given an arbitrary sequence of non-negative integers $S = (s_1, s_2, \dots, s_n)$, does there exist a simple graph $G$ whose degree sequence is precisely $S$? If such a simple graph exists, the sequence $S$ is called graphic (or graphical).

Elementary Necessary Conditions for a Graphic Sequence:

1. $\sum_{i=1}^n s_i$ must be an even integer (Handshaking Lemma).

2. $s_1 \le n - 1$ (no vertex in a simple graph of order $n$ can have degree $\ge n$).

2. The Havel-Hakimi Theorem

Published independently by Václav Havel (1955) and S. Louis Hakimi (1962), this theorem provides a recursive algorithmic characterization that decides whether a sequence is graphic in polynomial time.

Theorem 1.2 (Havel-Hakimi Theorem): Let $S = (d_1, d_2, \dots, d_n)$ be a non-increasing sequence of non-negative integers with $n \ge 2$ and $d_1 \ge 1$. Define the reduced sequence $S'$ by deleting the first element $d_1$ and subtracting $1$ from each of the next $d_1$ elements:

Then $S$ is graphic if and only if the rearranged non-increasing sequence $S'$ is graphic.

Complete Proof of the Havel-Hakimi Theorem:

• $(\impliedby)$ Direction (Sufficiency):

Suppose $S'$ is graphic. Then there exists a simple graph $G'$ with vertex set $V' = \{v_2, v_3, \dots, v_n\}$ having degree sequence $S'$:

Construct a new graph $G$ by adding a new vertex $v_1$ and connecting $v_1$ to the $d_1$ vertices $\{v_2, v_3, \dots, v_{d_1 + 1}\}$. Then:

• $\deg_G(v_1) = d_1$.

• For $2 \le i \le d_1 + 1$: $\deg_G(v_i) = \deg_{G'}(v_i) + 1 = (d_i - 1) + 1 = d_i$.

• For $d_1 + 2 \le i \le n$: $\deg_G(v_i) = \deg_{G'}(v_i) = d_i$.

Thus $G$ is a simple graph whose degree sequence is $S$. Hence $S$ is graphic.

• $(\implies)$ Direction (Necessity):

Suppose $S$ is graphic. Among all simple graphs having degree sequence $S$, choose a graph $G = (V, E)$ with $V = \{v_1, v_2, \dots, v_n\}$ and $\deg(v_i) = d_i$ such that the neighborhood $N(v_1)$ contains the maximum possible number of vertices from the target set $T = \{v_2, v_3, \dots, v_{d_1 + 1}\}$.

• If $N(v_1) = T$, we are done: deleting $v_1$ yields a graph $G' = G - v_1$ whose degree sequence is precisely $S'$.

• Suppose $N(v_1) \ne T$. Since $|N(v_1)| = d_1 = |T|$, there must exist vertices $v_j \in T$ and $v_k \notin T$ such that:

Because $v_j \in T$ and $v_k \notin T$, the indices satisfy $j < k$, which implies:

Since $v_1 \sim v_k$ but $v_1 \not\sim v_j$, vertex $v_j$ has degree $\ge d_k$, so $v_j$ must have neighbors outside of $N(v_k) \cup \{v_1\}$. Specifically, there must exist some vertex $v_r \in V \setminus \{v_1, v_j, v_k\}$ such that:

Now perform a 2-switch (edge interchange): Delete the edges $\{v_1, v_k\}$ and $\{v_j, v_r\}$, and add the edges $\{v_1, v_j\}$ and $\{v_k, v_r\}$:

Notice that the degree of every vertex remains completely unchanged! However, the new graph $G_{\text{new}}$ has $v_1 \sim v_j$, so $|N(v_1) \cap T|$ has strictly increased by 1! This directly contradicts the maximality of our initial choice of $G$. Therefore, it must be that $N(v_1) = T$, which proves that $S'$ is graphic. $\blacksquare$

1. Graph Isomorphism

Two graphs may appear drastically different when drawn in the plane, yet possess identical structural connectivity.

Definition 1.11 (Graph Isomorphism): Let $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ be simple graphs. An isomorphism between $G_1$ and $G_2$ is a bijection $f: V_1 \to V_2$ such that:

If such a bijection exists, we say $G_1$ and $G_2$ are isomorphic, written $G_1 \cong G_2$.

Isomorphism is an equivalence relation on the class of all graphs.

2. Graph Invariants

A graph invariant is any mathematical property of a graph that is preserved under isomorphism. If $G_1 \cong G_2$, then every invariant must match identically:

1. $|V(G_1)| = |V(G_2)|$ (same number of vertices).

2. $|E(G_1)| = |E(G_2)|$ (same number of edges).

3. The degree sequences of $G_1$ and $G_2$ must be identical.

4. The number of cycles of length $k$ ($C_k$) must be identical for every $k \ge 3$.

5. The chromatic number, diameter, and clique number must match.

Note: Having matching invariants is a necessary condition for isomorphism, but not sufficient. Two non-isomorphic graphs can share the identical degree sequence (e.g., $C_6$ and two disjoint triangles $2 K_3$ both have degree sequence $(2, 2, 2, 2, 2, 2)$).

3. Fundamental Graph Operations

Definition 1.12 (Complement of a Graph): The complement $\overline{G}$ of a simple graph $G = (V, E)$ is the simple graph with the same vertex set $V$, where two distinct vertices are adjacent in $\overline{G}$ if and only if they are not adjacent in $G$:

Notice: $|E(G)| + |E(\overline{G})| = \binom{n}{2} = \frac{n(n - 1)}{2}$. A graph $G$ is called self-complementary if $G \cong \overline{G}$.

Definition 1.13 (Union and Join):

1. Disjoint Union ($G_1 \cup G_2$): $V(G_1 \cup G_2) = V_1 \cup V_2$ and $E(G_1 \cup G_2) = E_1 \cup E_2$.

2. Join ($G_1 * G_2$): Obtained from $G_1 \cup G_2$ by connecting every vertex in $V_1$ to every vertex in $V_2$.