Graph Theory Basics: Definitions, Paths, Trees, and Isomorphism

Core Definitions and Terminology

Graph Basics

A graph $G$ is a pair $(V,E)$, where:

• $V$ = finite set of vertices (nodes).
• $E$ = set of edges connecting pairs of vertices.
  • Undirected edge: $\{u,v\}$ (no direction).
  • Directed edge (arc): $(u,v)$ (from $u$ to $v$).
  • Weighted graph: Edges have numerical values (e.g., distances).

Degree of a vertex:

• Undirected: $\mathrm{deg}(v)=$ number of edges incident to $v$.
• Directed: ${\mathrm{deg}}^{+}(v)$ (out-degree), ${\mathrm{deg}}^{-}(v)$ (in-degree).

Key Theorems:

1. Handshaking Lemma: Sum of all vertex degrees = $2|E|$ (undirected). Proof: Each edge contributes 2 to the total degree sum.
2. Isolated vertex: $\mathrm{deg}(v)=0$.
3. Path: Sequence of vertices $v_1,v_2,...,v_k$ where each $\{v_i,v_{i+1}\}\in E$.
4. Cycle: Path where $v_1=v_k$ and no repeated vertices/edges (except start/end).

---

Eulerian and Hamiltonian Graphs

Eulerian Graphs

• Eulerian Path: Traverses every edge exactly once (no repeats).
• Eulerian Circuit: Eulerian Path that starts/ends at the same vertex. Conditions:

  Graph Type	Necessary & Sufficient Conditions	Example
  Eulerian Circuit	All vertices have even degree, and graph is connected.	Cycle graph $C_n$.
  Eulerian Path	Exactly 0 or 2 vertices have odd degree, rest even.	"A" shape (2 odd-degree vertices).

Algorithm to Find Eulerian Circuit (Fleury’s):

1. Start at any vertex with $\mathrm{deg}(v)>0$.
2. Traverse edges, removing them as you go.
3. At each step, avoid bridges (edges whose removal disconnects the graph) unless no choice.
4. Stop when all edges are traversed.

Hamiltonian Graphs

• Hamiltonian Cycle: Path that visits every vertex exactly once and returns to the start.
• No simple degree-based conditions exist (NP-Hard to verify). Examples:
• Complete graph $K_n$: Always Hamiltonian.
• Cycle graph $C_n$: Hamiltonian if $n\ge 3$.
• Bipartite graphs: Only Hamiltonian if parts have equal size (e.g., $K_{2,2}$ is not).

---

Trees and Spanning Trees

Tree Definitions

• Tree: Connected acyclic graph.
  • Properties:
    • $n$ vertices → $n-1$ edges.
    • Any two vertices have exactly one path between them.
    • Adding any edge creates a cycle.
• Forest: Disjoint union of trees.
• Rooted Tree: Tree with a designated root vertex (used in hierarchies).

Spanning Trees

• Spanning Tree: Subgraph of $G$ that is a tree and includes all vertices of $G$.
• Minimum Spanning Tree (MST): Spanning tree with the minimum total edge weight. Algorithms:
  1. Kruskal’s:
     • Sort edges by weight (ascending).
     • Add edges one by one, skipping those that form cycles (use Union-Find).
  2. Prim’s:
     • Start from any vertex, grow the tree by adding the cheapest edge to the current tree.

Example (Kruskal’s): Given graph $G$ with edges $\{A-B:4,A-C:2,B-C:1,B-D:3,C-D:5\}$:

1. Sort: $B-C(1)$, $A-C(2)$, $B-D(3)$, $A-B(4)$, $C-D(5)$.
2. Add $B-C$, $A-C$, $B-D$. MST edges: $\{B-C,A-C,B-D\}$, total weight = 6.

---

Graph Isomorphism

Two graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ are isomorphic if there exists a bijection $f:V_1\to V_2$ such that:

• $\{u,v\}\in E_1⟺\{f(u),f(v)\}\in E_2$ (undirected).
• $(u,v)\in E_1⟺(f(u),f(f(v)))\in E_2$ (directed).

Conditions to Check:

1. Same number of vertices/edges.
2. Same degree sequence (multiset of degrees).
3. Same connectivity (e.g., both connected/disconnected).
4. Same number of cycles of each length.

Example:

• $G_1$: Vertices $\{A,B,C\}$, edges $\{A-B,B-C\}$.
• $G_2$: Vertices $\{1,2,3\}$, edges $\{1-2,2-3\}$. Isomorphic via $f(A)=1,f(B)=2,f(C)=3$.

Non-Isomorphic Example:

• $K_3$ (complete graph on 3 vertices) vs. $C_3$ (cycle on 3 vertices).
  • Both have 3 vertices/edges, but $K_3$ has all pairs connected; $C_3$ is a single cycle.

---

Graph Representations

Advantages/Disadvantages:

---

Applications of Graph Theory

1. Network Routing: MST for efficient data transmission (e.g., internet topology).
2. Scheduling: Project management (e.g., PERT charts use directed acyclic graphs).
3. Social Networks: Friend recommendations (bipartite graphs: users vs. interests).
4. Biology: Protein interaction networks (vertices = proteins, edges = interactions).
5. Transportation: Shortest path algorithms (Dijkstra’s) for GPS navigation.
6. Bipartite Matching: Assigning tasks to workers (e.g., stable marriage problem).

---

Worked Examples

Example 1: Eulerian Path/Circuit

Question: Does the following graph have an Eulerian circuit or path?

A -- B -- C
|    |    |
D -- E -- F

Solution:

• Degrees: $A(2),B(3),C(2),D(2),E(4),F(2)$.
• Odd-degree vertices: $B$ (only one).
• Conclusion: No Eulerian circuit (needs 0 odd vertices) or path (needs 0 or 2 odd vertices). Correction: If we add edge $A-F$, degrees become $A(3),B(3),C(2),D(2),E(4),F(3)$. Now 2 odd vertices ($A,B,F$) → Eulerian path exists.

Example 2: Spanning Tree (Prim’s Algorithm)

Graph:

A -- B (weight 1)
|    |
3    2
|    |
D -- C (weight 4)

Steps:

1. Start at $A$. Add $A-B$ (weight 1).
2. From $\{A,B\}$, cheapest edge is $B-C$ (weight 2).
3. From $\{A,B,C\}$, cheapest is $A-D$ (weight 3). MST: $\{A-B,B-C,A-D\}$, total weight = 6.

Example 3: Graph Isomorphism

Graphs:

• $G_1$: Vertices $\{1,2,3\}$, edges $\{1-2,2-3\}$.
• $G_2$: Vertices $\{X,Y,Z\}$, edges $\{X-Y,Y-Z\}$. Solution: Isomorphic via $f(1)=X,f(2)=Y,f(3)=Z$. Both are paths of length 2.

---

Common Mistakes and Clarifications

1. Eulerian vs. Hamiltonian:

   • Eulerian focuses on edges; Hamiltonian on vertices.
   • Example: $K_4$ (complete graph on 4 vertices) is Hamiltonian but not Eulerian (unless all degrees are even, which they are, but it’s not a single cycle unless you repeat vertices).

2. Spanning Tree vs. Minimum Spanning Tree:

   • All spanning trees connect all vertices, but MST minimizes total edge weight.
   • Kruskal’s vs. Prim’s: Kruskal’s is edge-driven; Prim’s is vertex-driven.

3. Isomorphism:

   • Not just about degree sequences (e.g., two graphs can have the same degree sequence but different structures, like $K_{1,3}$ vs. $P_4$).
   • Always verify connectivity and cycle structure.

4. Adjacency Matrix for Directed Graphs:

   • For $(u,v)$, set $M[u][v]=1$, but $M[v][u]=0$ unless there’s a reverse edge.

---

Exam Tip

What to Focus On

1. Definitions:

   • Memorize Eulerian/Hamiltonian conditions and tree properties (e.g., $n$ vertices → $n-1$ edges).
   • Know isomorphism criteria (degree sequence is necessary but not sufficient).

2. Algorithms:

   • Kruskal’s/Prim’s: Practice on small graphs (3–5 vertices). Show steps clearly.
   • Eulerian Circuit: Use Fleury’s algorithm; highlight bridges.

3. Proofs:

   • Handshaking Lemma: Prove by counting edge contributions.
   • Tree properties: Use induction (e.g., "A tree with $n$ vertices has $n-1$ edges"). Base case: $n=1$ (0 edges). Inductive step: Adding a leaf increases edges by 1.

4. Applications:

   • Link graph theory to real-world problems (e.g., "Why use MST in network design?").
   • For bipartite graphs, recall König’s theorem (matching = vertex cover).

5. Common Exam Questions:

   • Given a graph, determine if it’s Eulerian/Hamiltonian.
   • Find MST using Kruskal’s/Prim’s (show all steps).
   • Prove isomorphism between two graphs (provide bijection).
   • Shortest path: Use Dijkstra’s (if weights are non-negative).

Avoid These Pitfalls

• Assuming all graphs are Eulerian/Hamiltonian: Always check conditions.
• Forgetting directed graphs: Conditions differ (e.g., Eulerian directed graphs need in-degree = out-degree for all vertices).
• Incorrect MST: Skipping Union-Find in Kruskal’s leads to cycles.
• Isomorphism without verification: Degree sequence match ≠ isomorphism.

Sample Short-Answer Tips

• Define Eulerian Path: "A path that traverses every edge exactly once."
• MST Definition: "A spanning tree with the minimum possible total edge weight."
• Isomorphism: "Two graphs are isomorphic if there’s a one-to-one correspondence between vertices that preserves adjacency."

Long-Answer Strategy

1. State definitions clearly.
2. Draw the graph (if given) and label key parts.
3. Apply theorems/algorithms step-by-step (e.g., Kruskal’s: sort → add → check cycles).
4. Justify conclusions (e.g., "Since there are 4 odd-degree vertices, no Eulerian path exists").

---

Practice Problems

1. Given a graph, find all Eulerian circuits (if any).
2. Prove that a graph with 10 vertices and 11 edges is not a tree.
3. Find MST for a given weighted graph using both Kruskal’s and Prim’s.
4. Determine isomorphism between two graphs and provide the mapping.
5. Apply graph coloring to a map to show 4 colors suffice (Four Color Theorem intuition).