9.1 Graph Formalisms, Degree Sequences & the Handshaking Lemma

Back to Discrete Mathematics Notes

📚Module 09: Graph Theory Foundations, Paths & ConnectivityTopic 9.1: Graph Formalisms & Degrees⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Cocktail Party & Highway Bridges

Think of graphs as mathematical blueprints of relationships between entities:

1. The Handshaking Principle: Imagine entering a room with $n$ guests. When two guests shake hands, one single handshake adds 2 to the total count of handshakes given (1 to Person A's tally, and 1 to Person B's tally).
   • If 10 handshakes take place in the room, the sum of all individual handshakes recorded is exactly $2 \times 10 = 20$.
   • Because every handshake contributes 2 to the global tally, the sum of all degrees across the universe is always an even number!
   • Consequently, the number of guests who shook an odd number of hands must be an even number!
2. Simple Graphs vs Multigraphs:
   • Simple Graph: At most one direct flight between any two cities, and no flight that takes off and immediately lands at the exact same airport (no self-loops).
   • Multigraph: Multiple competing airlines flying between the same pair of cities (parallel edges).
3. The Havel-Hakimi Test: A group of people claim: "I have 3 friends, she has 3, he has 3, they have 1." Is that network physically possible, or are they lying? Havel-Hakimi recursively strips the highest degree to test whether a degree sequence can actually form a simple graph!

💻 Bridging to Computer Science: Networks, Social Graphs & Compilers

In computer systems:

• Computer Networks: Routers are vertices; fiber-optic cables are edges. Degree represents port bandwidth and network resilience.
• Social Networks (LinkedIn / Facebook): Users are vertices; bidirectional friendships form undirected edges; unidirectional follow relationships form directed edges.
• Compiler Register Allocation: Program variables are vertices; interference (overlapping live ranges) forms edges. The graph is colored to assign variables to physical CPU registers.

📑Table of Contents

• 🕸️ Formal Graph Taxonomy & Combinatorial Counting
  • 🔢 Combinatorial Counting of Labeled Simple Graphs
• 🔢 Vertex Degrees & The Handshaking Lemma
• 🏛️ Standard Graph Families
  • Regular Graphs
• 🌓 Bipartite Graphs & Turán's Bound
• 🔄 Graph Complement & Self-Complementary Graphs
  • Fundamental Properties of Graph Complements:
• 🔍 The Havel-Hakimi Theorem: Is a Sequence Graphical?
• 📝 Step-by-Step Worked Examples
  • Example 1: Applying the Havel-Hakimi Algorithm
  • Example 2: Handshaking Lemma & Bipartite Turán Limits
• 🎯 Exam & Interview Pitfall Check

---

🕸️ Formal Graph Taxonomy & Combinatorial Counting

📖Definition 9.1: Formal Graph Definitiondefinition

A Graph $G = (V, E)$ consists of:

1. A non-empty set $V = V(G)$ whose elements are called vertices (or nodes).
2. A set $E = E(G)$ whose elements are called edges (or links), where each edge $e \in E$ is associated with an unordered pair $\{u, v\}$ (for undirected graphs) or an ordered pair $(u, v)$ (for directed graphs) of vertices from $V$.

• Order of $G$: The number of vertices: $n = |V|$.
• Size of $G$: The number of edges: $m = |E|$.
• Null Graph ($N_n$): A graph containing $n$ vertices and $0$ edges ($|E| = 0$).
• Trivial Graph ($K_1$): A graph with exactly $1$ vertex and $0$ edges.

The Spectrum of Graph Topologies

Classifying graphs based on directionality, edge duplication, and self-loops

🌐

Simple Graph

Standard Model

• Undirected edges.
• NO self-loops (no edge connecting a vertex to itself).
• NO multiple / parallel edges (at most one edge between any pair).
• Maximum possible edges: C(n, 2) = n(n - 1) / 2.

🔀

Multigraph

Parallel Channels

• Allows multiple edges connecting the exact same pair of vertices.
• Models redundant network links or multi-lane highways.
• Zero self-loops allowed.

🔄

Pseudograph

Loops Allowed

• Allows both parallel edges AND self-loops (edges from v to v).
• A self-loop contributes 2 to the degree of its incident vertex!

➡️

Directed Graph (Digraph)

Asymmetric Flow

• Edges are ordered pairs e = (u, v) with a designated direction.
• u is the initial vertex (source); v is the terminal vertex (target).

🔢 Combinatorial Counting of Labeled Simple Graphs

📐Theorem 9.1: Counting Labeled Graphstheorem

Let $V$ be a set of $n$ labeled vertices:

1. Total Number of Potential Edges: $$N = \binom{n}{2} = \frac{n(n - 1)}{2}$$
2. Total Number of Labeled Simple Graphs: Every potential edge $\{u, v\}$ can either be present or absent (2 independent binary choices): $$\text{Total Graphs} = 2^N = 2^{\binom{n}{2}}$$
3. Number of Labeled Simple Graphs with exactly $e$ edges: Choosing $e$ edges out of the $\binom{n}{2}$ available slots: $$\text{Count}(n, e) = \binom{\binom{n}{2}}{e}$$

---

🔢 Vertex Degrees & The Handshaking Lemma

📖Definition 9.2: Degree of a Vertexdefinition

Let $G = (V, E)$ be an undirected graph, and let $v \in V$:

1. The degree of vertex $v$ (denoted $\deg(v)$ or $d(v)$) is the number of edges incident with $v$. Each self-loop counts as two incident edges.
2. Isolated Vertex: A vertex with degree $0$ ($\deg(v) = 0$).
3. Pendant (Leaf) Vertex: A vertex with degree $1$ ($\deg(v) = 1$).
4. Minimum and Maximum Degrees: $$\delta(G) = \min_{v \in V} \deg(v), \qquad \Delta(G) = \max_{v \in V} \deg(v)$$
5. For a directed graph:
   • In-Degree ($\deg^-(v)$): Number of edges terminating at $v$.
   • Out-Degree ($\deg^+(v)$): Number of edges originating from $v$.

📐Theorem 9.2: The Handshaking Lemma (Euler's First Theorem)theorem

In any undirected graph $G = (V, E)$:

$$\sum_{v \in V} \deg(v) = 2 |E|$$

Proof: Every edge $e = \{u, v\}$ has two distinct endpoints ($u$ and $v$). When summing the degrees of all vertices across the graph, each edge is counted exactly twice: once at vertex $u$ and once at vertex $v$. (A self-loop at $u$ contributes 2 to $\deg(u)$, again contributing 2 to the sum). Therefore, the sum of all vertex degrees must equal exactly twice the number of edges.

Directed Graph Analogue:

$$\sum_{v \in V} \deg^-(v) = \sum_{v \in V} \deg^+(v) = |E|$$

Average Degree Inequality: The average vertex degree is $d_{\text{avg}} = \frac{2|E|}{n}$. Consequently:

$$\delta(G) \le \frac{2|E|}{n} \le \Delta(G)$$

📐Theorem 9.3: The Odd-Degree Vertex Parity Theoremtheorem

In any undirected graph, the number of vertices of odd degree is ALWAYS EVEN!

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

• $V_{\text{even}}$: The set of vertices with even degree.
• $V_{\text{odd}}$: The set of vertices with odd degree. By the Handshaking Lemma:

$$\sum_{v \in V} \deg(v) = \sum_{v \in V_{\text{even}}} \deg(v) + \sum_{v \in V_{\text{odd}}} \deg(v) = 2 |E|$$

Notice that:

• $2 |E|$ is strictly an even integer.
• $\sum_{v \in V_{\text{even}}} \deg(v)$ is a sum of even numbers, which is strictly even. Rearranging:

$$\sum_{v \in V_{\text{odd}}} \deg(v) = 2 |E| - \sum_{v \in V_{\text{even}}} \deg(v) = \text{Even} - \text{Even} = \text{Even}$$

The sum of an odd number of odd terms is odd! Therefore, for the sum of odd degrees to be even, there must be an even number of terms in $V_{\text{odd}}$.

---

🏛️ Standard Graph Families

Fundamental Families of Simple Graphs

Classical symmetric topologies forming the building blocks of network theory

⭐

Complete Graph (Kₙ)

All-to-All Mesh

• Every pair of distinct vertices is connected by an edge.
• Degree of every vertex: n - 1.
• Total edges: |E| = n(n - 1) / 2 = C(n, 2).
• Hamiltonian cycles: (n - 1)! / 2.
• Spanning trees (Cayley's Formula): n^(n - 2).

🔄

Cycle Graph (Cₙ)

Closed Ring (n ≥ 3)

• A single closed loop with vertices v₁, v₂, ..., vₙ.
• Every vertex has degree exactly 2 (2-regular).
• Total edges: |E| = n.
• Bipartite if and only if n is EVEN.

📏

Path Graph (Pₙ)

Linear Chain

• A single non-branching chain with n vertices.
• Two leaf endpoints of degree 1; n - 2 internal vertices of degree 2.
• Total edges: |E| = n - 1.
• Always bipartite for all n ≥ 1.

☸️

Wheel Graph (Wₙ)

Hub & Spokes (n ≥ 3)

• Formed by adding a central hub vertex to a cycle Cₙ.
• Total vertices: n + 1. Total edges: 2n.
• Central hub has degree n; rim vertices have degree 3.

Regular Graphs

📖Definition 9.3: Regular Graphdefinition

A graph is $k$-regular if every vertex has the exact same degree $k$:

$$\forall v \in V, \quad \deg(v) = k$$

By the Handshaking Lemma, the number of edges in a $k$-regular graph with $n$ vertices is:

$$n \cdot k = 2 |E| \implies |E| = \frac{n \cdot k}{2}$$

Immediate Invariant: For a $k$-regular graph to exist, the product $n \cdot k$ must be an even integer! At least one of $n$ or $k$ must be even (e.g., a 3-regular graph cannot have 7 vertices because $7 \times 3 = 21$, which is odd).

---

🌓 Bipartite Graphs & Turán's Bound

📖Definition 9.4: Bipartite Graph & Complete Bipartite (K_{m, n})definition

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

1. Complete Bipartite Graph ($K_{m, n}$): Every vertex in $V_1$ ($|V_1| = m$) is connected to every vertex in $V_2$ ($|V_2| = n$).
   • Total vertices: $|V| = m + n$.
   • Total edges: $|E| = m \cdot n$.
   • Degrees: Vertices in $V_1$ have degree $n$; vertices in $V_2$ have degree $m$.
   • Total spanning trees: $\tau(K_{m, n}) = m^{n - 1} n^{m - 1}$.
2. Turán's Maximum Edge Bound for Bipartite Graphs: In any bipartite graph with $n$ vertices, the maximum possible number of edges occurs when the partitions are balanced as equally as possible ($m = \lfloor n/2 \rfloor, n - m = \lceil n/2 \rceil$): $$\max |E| = \left\lfloor \frac{n^2}{4} \right\rfloor$$

★ 2-Colorable Bipartite Graph (K₂,₃)

Bipartition: V₁ = {u₁, u₂} and V₂ = {v₁, v₂, v₃}. Every edge connects a blue vertex to an emerald vertex; zero intra-set edges exist.

📐Theorem 9.4: Kőnig's Characterization of Bipartite Graphstheorem

A graph $G$ is bipartite if and only if $G$ contains NO ODD CYCLES!

Intuition: To traverse a cycle in a bipartite graph, you must alternately step from $V_1 \to V_2 \to V_1 \to V_2 \dots$. To return to your starting partition, you must take an even number of steps. Thus, every cycle in a bipartite graph must have even length!

• $C_4, C_6, C_8$: Bipartite (even cycles).
• $C_3, C_5, C_7$: NOT Bipartite (contain odd cycles).
• Trees and Forests: Always bipartite (contain zero cycles).

---

🔄 Graph Complement & Self-Complementary Graphs

📖Definition 9.5: Complement of a Graphdefinition

Let $G = (V, E)$ be a simple graph. The complement of $G$, denoted $\bar{G}$, has the identical vertex set $V$, and two distinct vertices are adjacent in $\bar{G}$ if and only if they are NOT adjacent in $G$:

$$e = \{u, v\} \in E(\bar{G}) \iff e = \{u, v\} \notin E(G)$$

Fundamental Properties of Graph Complements:

1. Edge Sum Conservation: $$|E(G)| + |E(\bar{G})| = \binom{n}{2} = \frac{n(n - 1)}{2}$$
2. Complement Degree Formula: For every vertex $v \in V$: $$\deg_{\bar{G}}(v) = (n - 1) - \deg_G(v)$$
3. Self-Complementary Graphs: A simple graph is self-complementary if it is isomorphic to its own complement: $$G \cong \bar{G}$$ If $G$ is self-complementary, then $|E(G)| = |E(\bar{G})|$. Substituting into the conservation formula: $$2 |E(G)| = \frac{n(n - 1)}{2} \implies |E(G)| = \frac{n(n - 1)}{4}$$ Because $|E(G)|$ must be a non-negative integer: $$4 \mid n(n - 1) \iff n \equiv 0 \pmod 4 \quad \text{or} \quad n \equiv 1 \pmod 4$$ (e.g., $n = 4$ for $P_4$, and $n = 5$ for $C_5$ are self-complementary).

---

🔍 The Havel-Hakimi Theorem: Is a Sequence Graphical?

A non-increasing sequence of non-negative integers $d = (d_1, d_2, \dots, d_n)$ is called graphical if there exists a simple graph whose vertex degree sequence is precisely $d$.

The Havel-Hakimi Algorithm for Graphical Sequences

Recursive greedy stripping algorithm to determine if a degree sequence is physically realizable

1

Parity & Range Pre-Flight Check

Pre-Flight Checks

Check: (1) Max degree d₁ ≤ n - 1. (2) Sum of all degrees is EVEN. (3) Number of odd-degree elements is EVEN. If any check fails, IMMEDIATELY NOT GRAPHICAL!

2

Sort in Descending Order

Sort

Arrange the sequence so d₁ ≥ d₂ ≥ ... ≥ dₙ.

3

Extract the Leading Degree d₁

Greedy Strip

Remove the first element d₁. Subtract 1 from each of the next d₁ elements in the sequence.

4

Repeat Until Termination Base Case

Base Case

Re-sort and repeat. If all elements reduce to zeros (0, 0, ..., 0) ⟹ GRAPHICAL! If any element becomes negative (-1) ⟹ NOT GRAPHICAL!

---

📝 Step-by-Step Worked Examples

Example 1: Applying the Havel-Hakimi Algorithm

Problem Statement: Determine whether the following degree sequence is graphical (can form a simple graph):

$$d = (5, 4, 3, 3, 2, 2, 2, 1)$$

Step-by-Step Solution:

1. Step 1: Pre-Flight Parity Check

   • Number of vertices: $n = 8$.
   • Max degree is $5 \le n - 1 = 7$ (valid).
   • Sum of degrees: $5 + 4 + 3 + 3 + 2 + 2 + 2 + 1 = 22$ (Even! Passes the Handshaking Lemma).
   • Odd-degree vertices: $\{5, 3, 3, 1\}$ (4 odd vertices $\implies$ Even count! Passes).

2. Step 2: Iteration 1 of Havel-Hakimi

   • Current sequence (sorted): $(5, 4, 3, 3, 2, 2, 2, 1)$.
   • Remove the leading element $d_1 = 5$.
   • Subtract $1$ from the next $5$ elements:
     • $4 - 1 = 3$
     • $3 - 1 = 2$
     • $3 - 1 = 2$
     • $2 - 1 = 1$
     • $2 - 1 = 1$
   • Unaltered remaining elements: $(2, 1)$.
   • Resulting sequence: $(3, 2, 2, 1, 1, 2, 1)$.
   • Re-sort in descending order: $$d^{(1)} = (3, 2, 2, 2, 1, 1, 1)$$

3. Step 3: Iteration 2 of Havel-Hakimi

   • Remove leading element $d_1 = 3$.
   • Subtract $1$ from the next $3$ elements:
     • $2 - 1 = 1$
     • $2 - 1 = 1$
     • $2 - 1 = 1$
   • Unaltered elements: $(1, 1, 1)$.
   • Resulting sequence: $(1, 1, 1, 1, 1, 1)$.
   • Re-sort: $$d^{(2)} = (1, 1, 1, 1, 1, 1)$$

4. Step 4: Iteration 3 of Havel-Hakimi

   • Remove leading element $1$. Subtract $1$ from next $1$ element: $(0, 1, 1, 1, 1)$.
   • Re-sort: $(1, 1, 1, 1, 0)$.
   • Continuing the greedy strip terminates in all zeros $(0, 0, 0, 0, 0, 0)$.
   • Conclusion: The sequence IS GRAPHICAL! A simple graph with this degree sequence exists.

Key Takeaway: Always re-sort the remaining elements in non-increasing order after every subtraction step in Havel-Hakimi!

---

Example 2: Handshaking Lemma & Bipartite Turán Limits

Problem Statement:

1. A bipartite graph $G$ has 12 vertices. What is the maximum number of edges $G$ can have?
2. If a simple graph has 10 vertices and is 3-regular, how many edges does it contain? What if it is 3-regular with 11 vertices?

Step-by-Step Solution:

1. Part 1: Maximum Edges in Bipartite Graph ($n = 12$)

   • By Turán's theorem for bipartite graphs: $$\max |E| = \left\lfloor \frac{n^2}{4} \right\rfloor = \left\lfloor \frac{12^2}{4} \right\rfloor = \frac{144}{4} = 36 \text{ edges}$$
   • This occurs in the complete bipartite graph $K_{6, 6}$ with $|V_1| = 6$ and $|V_2| = 6$.

2. Part 2: 3-Regular Graph with 10 Vertices

   • By the Handshaking Lemma: $$n \cdot k = 2 |E| \implies 10 \times 3 = 30 = 2 |E| \implies |E| = 15 \text{ edges}$$
   • Since $k = 3 \le n - 1 = 9$ and $n \cdot k = 30$ is even, a 3-regular graph with 10 vertices exists.

3. Part 3: 3-Regular Graph with 11 Vertices

   • Sum of degrees: $11 \times 3 = 33$.
   • $33$ is an ODD integer, which violates the Handshaking Lemma ($\sum \deg(v) = 2|E|$ must be even).
   • Alternatively, it would require 11 vertices of odd degree, violating the Odd-Degree Parity Theorem!
   • Conclusion: NO such graph can exist.

Key Takeaway: For a $k$-regular graph to exist, the product $n \cdot k$ must be strictly even, and $k \le n - 1$.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: Can a simple graph with 7 vertices have degree sequence $(6, 6, 6, 2, 2, 1, 1)$? Key Focus Points: No! Let us analyze the structural constraints:

• There are 7 vertices in total ($n = 7$). A vertex of degree 6 connects to every single other vertex in the graph (it is a universal neighbor).
• Here, there are three distinct vertices of degree 6 ($v_1, v_2, v_3$). Each of these three vertices must connect to every other vertex in the graph.
• Therefore, every remaining vertex in the graph must connect to at least $v_1, v_2,$ and $v_3$, meaning every vertex must have degree at least 3!
• The sequence contains vertices of degree 1 and 2, which contradicts the existence of three degree-6 vertices. Thus, it cannot form a simple graph!

Question 2: If a self-complementary graph has $n$ vertices, why is $n = 8$ possible but $n = 7$ or $n = 6$ impossible? Key Focus Points: For a graph to be self-complementary ($G \cong \bar{G}$):

$$|E(G)| = \frac{n(n - 1)}{4}$$

• For $n = 8$: $|E| = \frac{8 \times 7}{4} = 14$ (integer, valid since $8 \equiv 0 \pmod 4$).
• For $n = 7$: $|E| = \frac{7 \times 6}{4} = 10.5$ (impossible).
• For $n = 6$: $|E| = \frac{6 \times 5}{4} = 7.5$ (impossible). Self-complementary graphs can only exist when $n \equiv 0$ or $1 \pmod 4$.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Forgetting to re-sort after each step in Havel-Hakimi Why it fails: In Havel-Hakimi, after subtracting 1 from the adjacent elements, the resulting numbers may no longer be in descending order. Subtracting from a non-sorted list invalidates the greedy invariant and produces false negatives!

Trap 2: Counting a self-loop as degree 1 Why it fails: A self-loop connects vertex $v$ back to itself. Both endpoints of the edge attach to $v$, contributing +2 to the degree of $v$! Counting it as 1 violates the Handshaking Lemma ($\sum \deg(v) = 2|E|$).

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic8.3 Ordinary Generating Functions & Closed-Form Combinatorial SequencesNext Topic →9.2 Graph Representations, Subgraphs & Graph Isomorphism Invariants