Chapter 12: Planar Graphs, Multigraphs, Eulerian & Hamiltonian Graphs, Chromatic Numbers & Graph Coloring
(TB1 Ch.5, Articles 7–12)
1. Planar Graphs
Definition
A graph is planar if it can be drawn on a plane without any edges crossing.
- Such a drawing is called a plane graph
Euler’s Formula for Connected Planar Graphs
[ v - e + f = 2 ]
- (v) = number of vertices
- (e) = number of edges
- (f) = number of faces (including outer region)
Example
- Graph: Triangle (3 vertices, 3 edges)
- Faces: 2 (inside + outside) [ v - e + f = 3 - 3 + 2 = 2 ✅ ]
Application
- PCB layout
- Geographic maps (planarity for regions)
2. Multigraphs
Definition
A multigraph allows:
-
Multiple edges between same vertices
-
Loops may or may not be allowed (pseudograph if loops included)
-
Not necessarily simple
-
Useful for network modeling with multiple connections
Example
Vertices: {A,B}, edges: {AB, AB, loop at A} → multigraph
3. Eulerian Graphs
Definition
A graph is Eulerian if it contains a closed trail that visits every edge exactly once.
- Eulerian Circuit: starts and ends at same vertex
- Eulerian Path: visits every edge exactly once, may start ≠ end
Conditions (Undirected Graph)
- Eulerian Circuit: All vertices have even degree
- Eulerian Path: Exactly two vertices have odd degree, rest even
Example
Graph: Square with diagonals
- Degrees: 2,2,2,2 → Eulerian circuit exists
- Eulerian path? Yes, same as circuit in this case
4. Hamiltonian Graphs
Definition
A graph is Hamiltonian if there exists a cycle visiting every vertex exactly once.
- Hamiltonian Path: visits each vertex once, may start ≠ end
Conditions
- No simple degree rule (more complex than Eulerian)
- Dirac’s Theorem: For simple graph with n ≥ 3, if every vertex deg ≥ n/2 → Hamiltonian
Example
- Pentagon (5-cycle): Hamiltonian cycle exists (1→2→3→4→5→1)
5. Chromatic Number & Graph Coloring
Definition
- Graph coloring: Assign colors to vertices so no two adjacent vertices share the same color
- Chromatic number (\chi(G)): Minimum number of colors needed
Example
- Triangle (3 vertices, 3 edges) → (\chi(G) = 3)
- Bipartite graph → (\chi(G) = 2)
Applications
- Register allocation in compilers
- Map coloring (regions on a map)
- Scheduling problems
Graph Coloring Rules
- Adjacent vertices must have different colors
- Start with highest-degree vertex (heuristic for exams)
- Count minimum colors → chromatic number
6. Summary Table
| Concept | Definition | Key Property | Example |
|---|---|---|---|
| Planar Graph | Can be drawn without crossing edges | Euler formula: v-e+f=2 | Triangle, square |
| Multigraph | Multiple edges allowed | May contain loops | Network with redundant links |
| Eulerian Graph | Closed trail covering all edges | All vertices even deg (circuit) | Square graph |
| Hamiltonian Graph | Cycle covering all vertices | Dirac’s theorem (sufficient) | Pentagon |
| Chromatic Number | Min colors for proper vertex coloring | (\chi(G)) | Triangle → 3, Bipartite → 2 |