26-09 — Graph Theory Basics

Phase: Combinatorics | Subject: 26-09 Prerequisites: 26-03-combinations.md, 26-05-pigeonhole-principle.md Next subject: 26-10-combinatorial-proofs.md

Learning Objectives

By the end of this subject, you will be able to:

1. Define graphs: vertices, edges, adjacency, incidence, degree
2. State and prove the Handshaking Lemma
3. Classify graphs: simple, complete, bipartite, trees, planar
4. Compute paths, cycles, and connectivity
5. Apply Euler's formula for planar graphs

Core Content

Basic Definitions

A graph $G = (V, E)$ is a set of vertices $V$ and edges $E$ (unordered pairs of vertices).

• Order: $|V|$ (number of vertices)
• Size: $|E|$ (number of edges)
• Degree $\deg(v)$: number of edges incident to vertex $v$
• Adjacent vertices share an edge
• Simple graph: no loops, no multiple edges
• Complete graph $K_n$: every pair of vertices is connected ($\binom{n}{2}$ edges)
• Bipartite graph: vertices can be split into two sets, all edges cross between sets

The Handshaking Lemma

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

Corollary: In any graph, the number of vertices of odd degree is even.

Paths and Cycles

• Path of length $k$: sequence of $k+1$ distinct vertices $v_0, v_1, \ldots, v_k$ where consecutive vertices are adjacent
• Cycle: a path where $v_0 = v_k$ and all other vertices are distinct
• Connected: a graph is connected if there is a path between every pair of vertices
• Distance $d(u, v)$: length of shortest path between $u$ and $v$

Trees

A tree is a connected acyclic graph.

Properties (all equivalent for an $n$-vertex graph): - Connected and acyclic - $n-1$ edges - Connected, and removing any edge disconnects it - Any two vertices connected by exactly one path

Example: A tree with $n$ vertices has exactly $n-1$ edges.

Eulerian and Hamiltonian

• Eulerian trail: uses every edge exactly once. Exists iff at most 2 vertices have odd degree (exactly 0 for Eulerian circuit).
• Hamiltonian cycle: visits every vertex exactly once. No simple characterization — NP-complete.

Planar Graphs and Euler's Formula

A graph is planar if it can be drawn in the plane without edge crossings.

Euler's Formula: For a connected planar graph with $v$ vertices, $e$ edges, and $f$ faces (including the outer face):

$$v - e + f = 2$$

Corollary: For a simple planar graph with $v \geq 3$: $e \leq 3v - 6$. This proves $K_5$ is nonplanar: $v=5, e=10$, but $3(5)-6=9 < 10$.

Key Terms

• Graph, Vertex, Edge
• Degree, Handshaking Lemma
• Path, Cycle, Connected
• Tree
• Planar Graph, Euler's Formula

Worked Examples

Example 1: Degree Sequence

Is there a graph with degree sequence (3, 3, 3, 3, 2)?

Solution: Sum of degrees = $3+3+3+3+2 = 14$ (even — OK by Handshaking). By Havel-Hakimi, sort descending: 3, 3, 3, 3, 2. Remove the first (3) and subtract 1 from the next 3: 2, 2, 2, 2. Next: remove 2, subtract 1 from next 2: 1, 1, 2. Sort: 2, 1, 1. Remove 2, subtract 1 from next 2: 0, 0 — valid! So yes, such a graph exists.

Example 2: Tree Edges

How many edges does a forest of 3 trees with 15 total vertices have?

Solution: A tree with $n_i$ vertices has $n_i - 1$ edges. For 3 trees with $n_1 + n_2 + n_3 = 15$: Total edges = $(n_1 - 1) + (n_2 - 1) + (n_3 - 1) = 15 - 3 = 12$.

Example 3: Planarity

Use Euler's formula to show $K_{3,3}$ is nonplanar.

Solution: $K_{3,3}$ has $v=6$ vertices, $e=9$ edges. In a planar bipartite graph with no triangles, $e \leq 2v - 4$. Check: $2(6)-4 = 8 < 9$. So $K_{3,3}$ cannot be planar.

Quiz

Q1: What does the concept of Degree primarily refer to in this subject?

A) The definition and application of Degree B) A computational error related to Degree C) A visual representation of Degree D) A historical anecdote about Degree

Correct: A)

• If you chose A: Degree is defined as: the definition and application of degree. The other options describe different aspects that are not the primary focus. Correct!
• If you chose B: This is incorrect. Degree is defined as: the definition and application of degree. The other options describe different aspects that are not the primary focus.
• If you chose C: This is incorrect. Degree is defined as: the definition and application of degree. The other options describe different aspects that are not the primary focus.
• If you chose D: This is incorrect. Degree is defined as: the definition and application of degree. The other options describe different aspects that are not the primary focus.

Q2: Which of the following is the key formula discussed in this subject?

A) A simplified version of G = (V, E)... B) G = (V, E) C) An unrelated formula from a different topic D) The inverse operation of the formula in question

Correct: B)

• If you chose A: This is incorrect. The formula G = (V, E) is central to this subject. The other options are either simplified versions or unrelated.
• If you chose B: The formula G = (V, E) is central to this subject. The other options are either simplified versions or unrelated. Correct!
• If you chose C: This is incorrect. The formula G = (V, E) is central to this subject. The other options are either simplified versions or unrelated.
• If you chose D: This is incorrect. The formula G = (V, E) is central to this subject. The other options are either simplified versions or unrelated.

Q3: What is the primary purpose of Adjacent?

A) It is primarily a historical notation system B) It is used only in advanced research contexts C) It replaces all other methods in this domain D) It is used to adjacent in mathematical analysis

Correct: D)

• If you chose A: This is incorrect. Adjacent serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose B: This is incorrect. Adjacent serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose C: This is incorrect. Adjacent serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose D: Adjacent serves the purpose described in the correct answer. The other options misrepresent its role. Correct!

Q4: Which statement about Complete graph is TRUE?

A) Complete graph is a fundamental concept covered in this subject B) Complete graph is not related to this subject C) Complete graph is mentioned only as a historical footnote D) Complete graph is an advanced topic beyond this subject's scope

Correct: A)

• If you chose A: Complete graph is a fundamental concept covered in this subject. This subject covers Complete graph as part of its core content. Correct!
• If you chose B: This is incorrect. Complete graph is a fundamental concept covered in this subject. This subject covers Complete graph as part of its core content.
• If you chose C: This is incorrect. Complete graph is a fundamental concept covered in this subject. This subject covers Complete graph as part of its core content.
• If you chose D: This is incorrect. Complete graph is a fundamental concept covered in this subject. This subject covers Complete graph as part of its core content.

Q5: Based on the worked examples in this subject, what is the correct result?

A) An unrelated numerical value B) A different result from a common mistake C) The inverse of the correct answer D) Tree Edges

Correct: D)

• If you chose A: This is incorrect. The worked examples show that the result is Tree Edges. The other options represent common errors.
• If you chose B: This is incorrect. The worked examples show that the result is Tree Edges. The other options represent common errors.
• If you chose C: This is incorrect. The worked examples show that the result is Tree Edges. The other options represent common errors.
• If you chose D: The worked examples show that the result is Tree Edges. The other options represent common errors. Correct!

Q6: How are Complete graph and Distance related?

A) Complete graph is a special case of Distance B) Complete graph and Distance are completely unrelated topics C) Complete graph and Distance are closely related concepts D) Complete graph is the inverse of Distance

Correct: C)

• If you chose A: This is incorrect. Both Complete graph and Distance are covered in this subject as interconnected topics.
• If you chose B: This is incorrect. Both Complete graph and Distance are covered in this subject as interconnected topics.
• If you chose C: Both Complete graph and Distance are covered in this subject as interconnected topics. Correct!
• If you chose D: This is incorrect. Both Complete graph and Distance are covered in this subject as interconnected topics.

Q7: What is a common pitfall when working with Basic Definitions?

A) A common mistake is confusing Basic Definitions with a similar concept B) The main error with Basic Definitions is using it when it is not needed C) Basic Definitions is always computed the same way in all contexts D) Basic Definitions has no common misconceptions

Correct: A)

• If you chose A: Students often confuse Basic Definitions with similar-sounding or related concepts. Pay attention to the precise definitions. Correct!
• If you chose B: This is incorrect. Students often confuse Basic Definitions with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose C: This is incorrect. Students often confuse Basic Definitions with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose D: This is incorrect. Students often confuse Basic Definitions with similar-sounding or related concepts. Pay attention to the precise definitions.

Q8: When should you apply The Handshaking Lemma?

A) The Handshaking Lemma is not practically useful B) Use The Handshaking Lemma only in pure mathematics contexts C) Apply The Handshaking Lemma to solve problems in this subject's domain D) Avoid The Handshaking Lemma unless explicitly instructed

Correct: C)

• If you chose A: This is incorrect. The Handshaking Lemma is a practical tool used throughout this subject to solve relevant problems.
• If you chose B: This is incorrect. The Handshaking Lemma is a practical tool used throughout this subject to solve relevant problems.
• If you chose C: The Handshaking Lemma is a practical tool used throughout this subject to solve relevant problems. Correct!
• If you chose D: This is incorrect. The Handshaking Lemma is a practical tool used throughout this subject to solve relevant problems.

Practice Problems

1. How many edges in $K_7$ (complete graph on 7 vertices)?
   

   Click for answer

   $\binom{7}{2} = 21$ edges.

2. A graph has 10 vertices each of degree 4. How many edges?
   

   Click for answer

   $\sum \deg = 40 = 2|E|$, so $|E| = 20$.

3. Can a tree have 7 vertices and 7 edges? Justify.
   

   Click for answer

   No. A tree on $n$ vertices has exactly $n-1$ edges. 7 vertices → 6 edges.

4. Is the complete bipartite graph $K_{2,3}$ planar?
   

   Click for answer

   Yes. $v=5, e=6$. $3v-6 = 9 \geq 6$. And $K_{2,3}$ can be drawn without crossings.

5. What is the maximum number of edges in a simple graph with 5 vertices?
   

   Click for answer

   $\binom{5}{2} = 10$ edges ($K_5$, the complete graph on 5 vertices).

Summary

Key takeaways:

• Graph = vertices + edges
• Handshaking Lemma: $\sum \deg(v) = 2|E|$
• Trees: connected, acyclic, $n-1$ edges
• Eulerian: uses every edge once (≤ 2 odd-degree vertices)
• Planar: can be drawn without crossings; $v - e + f = 2$
• $K_5$ and $K_{3,3}$ are the fundamental nonplanar graphs (Kuratowski's theorem)

Pitfalls

• Confusing the Handshaking Lemma with an "even number of vertices": The Handshaking Lemma says the sum of degrees is $2|E|$, which implies the number of vertices of odd degree is even — not that every vertex has even degree, and not that the total number of vertices is even. A graph with vertices of degrees 3, 3, 2 has an even number of odd-degree vertices (two) and is valid.
• Assuming every connected graph with $n-1$ edges is a tree: A tree requires both connectedness and acyclicity. A graph with $n$ vertices and $n-1$ edges could be disconnected (e.g., a cycle plus isolated vertices). Always verify both properties, or verify that the graph is connected and has $n-1$ edges — these conditions together imply a tree.
• Misapplying Euler's formula by counting the outer face incorrectly: Euler's formula $v - e + f = 2$ counts the unbounded outer region as a face. A common mistake is forgetting the outer face, giving $f$ that's one too small. For a triangle drawn in the plane, $v=3, e=3$, and $f=2$ (the interior triangle plus the exterior region), giving $3-3+2=2$. Forgetting the outer face would give $f=1$ and a mismatched formula.
• Using Euler's formula on disconnected planar graphs without adjusting: Euler's formula $v - e + f = 2$ applies only to connected planar graphs. For a disconnected planar graph with $c$ components, the correct formula is $v - e + f = 1 + c$. Applying the connected version to a forest with multiple trees will give wrong results.
• Checking for an Eulerian circuit by only counting odd-degree vertices without checking connectivity: A graph has an Eulerian circuit iff it is connected (ignoring isolated vertices) and every vertex has even degree. The classic mistake is declaring a graph Eulerian because all degrees are even, while the graph is actually disconnected. The graph of two disjoint even cycles has all even degrees but no single Eulerian circuit.

Next Steps

Next up: 26-10-combinatorial-proofs.md — the art of proving combinatorial identities by counting the same thing in two ways.