A complete visual guide covering graphs, connectivity, paths, planarity and coloring — built for CSE beginners.
Graph theory studies pairwise relationships between objects. It powers GPS navigation, social networks, circuit design, scheduling — nearly all of computer science.
A graph G = (V, E) consists of a nonempty set V of vertices (nodes) and a set E of edges. Each edge connects one or two vertices, called its endpoints.
| Type | Edges | Multiple Edges? | Loops? |
|---|---|---|---|
| Simple Graph | Undirected | No | No |
| Multigraph | Undirected | Yes | No |
| Pseudograph | Undirected | Yes | Yes |
| Simple Digraph | Directed | No | No |
| Directed Multigraph | Directed | Yes | Yes |
| Mixed Graph | Both | Yes | Yes |
Vertices = people. Edges = friendships. Simple undirected graph. Degree = number of friends.
Vertices = webpages. Directed edges = hyperlinks. PageRank algorithm runs on this digraph.
Vertices = intersections. Edges = roads (weighted by distance). GPS uses shortest-path algorithms here.
Vertices = tasks. Directed edges = dependency (A→B means A must finish before B). Topological sort used.
The degree of vertex v, written deg(v), is the number of edges incident to v. A loop counts twice. In a digraph: in-degree = edges coming in; out-degree = edges going out.
For any undirected graph G = (V, E):
Consequence: Every graph has an even number of vertices with odd degree. This is a fundamental counting fact used everywhere.
Every pair of vertices connected by exactly one edge. Kₙ has n(n−1)/2 edges. Every vertex has degree n−1.
n vertices arranged in a ring. Each vertex has degree 2. Minimum n = 3.
Cₙ plus one central hub connected to all. Hub degree = n; rim vertices degree = 3.
Vertices split into two disjoint sets V₁, V₂. Every edge goes between V₁ and V₂ — never within same set. A graph is bipartite iff it has no odd-length cycle.
Every vertex in V₁ connected to every vertex in V₂. Has m·n edges.
Vertices = n-bit strings. Edge between strings differing in exactly 1 bit. Qₙ has 2ⁿ vertices and n·2ⁿ⁻¹ edges. Used in parallel computing.
For graph G with vertices v₁…vₙ, the adjacency matrix A is an n×n matrix where A[i][j] = 1 if {vᵢ,vⱼ} is an edge, else 0. For multigraphs, A[i][j] = number of edges between them.
Properties: symmetric for undirected, diagonal all-zeros for simple graph, row sum = degree of vᵢ.
n×m matrix M where M[i][j] = 1 if vertex vᵢ is incident with edge eⱼ, else 0. Column sum always = 2 (each edge has two endpoints).
More memory-efficient. For each vertex store list of its neighbors. Total space: O(V + E) vs O(V²) for matrix.
Graphs G₁=(V₁,E₁) and G₂=(V₂,E₂) are isomorphic if there exists a bijection f: V₁→V₂ such that {u,v}∈E₁ iff {f(u),f(v)}∈E₂. They are "same graph, different labeling."
These are necessary but not sufficient. If any differ → not isomorphic. If all match → might be isomorphic (need explicit bijection to confirm).
A path of length n from u to v is a sequence u=v₀, e₁, v₁, e₂, …, eₙ, vₙ=v of alternating vertices and edges. A simple path visits no vertex more than once.
A circuit (closed walk) starts and ends at same vertex. A cycle is a simple circuit — no repeated vertex except start=end.
An undirected graph is connected if there is a path between every pair of vertices. Otherwise it's disconnected, and each maximal connected subgraph is a connected component.
Strongly connected: path from u to v AND v to u for every pair. Weakly connected: underlying undirected graph is connected.
A cut vertex (articulation point): removing it increases connected components. A bridge: removing it disconnects the graph. Critical for network reliability analysis.
Min vertices to remove to disconnect G (or make trivial). κ(Kₙ) = n−1 (most robust). κ(G) ≤ λ(G) ≤ δ(G).
Min edges to remove to disconnect G. Menger's theorem links this to max disjoint paths.
A circuit that visits every edge exactly once (may revisit vertices). Named after Leonhard Euler who solved the Königsberg Bridge Problem in 1736 — birth of graph theory.
A path (not circuit) that uses every edge exactly once. Starts and ends at different vertices.
Euler Circuit exists iff G is connected AND every vertex has even degree.
Euler Path exists iff G is connected AND exactly two vertices have odd degree (those are the endpoints).
Seven bridges over the Pregel River connecting 4 land masses. Euler proved no walk crossing each bridge exactly once exists — all 4 vertices had odd degree. This proof founded graph theory.
A circuit that visits every vertex exactly once (may skip edges). Named after William Rowan Hamilton.
If G is simple, n ≥ 3, and every vertex has deg(v) ≥ n/2, then G has a Hamiltonian circuit.
If for every pair of non-adjacent vertices u,v: deg(u)+deg(v) ≥ n, then Hamiltonian circuit exists.
Key distinction: Euler = traverse all edges; Hamilton = visit all vertices. Euler conditions are easy to check; Hamilton is NP-complete in general.
| Euler | Hamiltonian | |
|---|---|---|
| What is traversed? | Every edge once | Every vertex once |
| Characterization | Degree conditions (easy) | No simple characterization (NP-hard) |
| Algorithm | Fleury's / Hierholzer's O(E) | No poly-time known |
| Application | Route planning, circuit boards | TSP, DNA sequencing |
Given a weighted graph, find the path from source to destination with minimum total weight. Real applications: GPS, network routing (OSPF), airline connections.
Finds shortest paths from a single source to all vertices in a weighted graph with non-negative weights. Greedy approach using priority queue.
Finds shortest paths between all pairs of vertices. Works with negative weights (not negative cycles). Dynamic programming approach.
A graph that can be drawn in the plane with no edge crossings. The drawing itself (without crossings) is called a planar embedding.
For a connected planar graph with V vertices, E edges, and F faces (regions, including unbounded outer face):
This is the planar graph version of Euler's characteristic. Works for any planar embedding!
Cube graph: V=8, E=12, F=6 → 8−12+6 = 2 ✓ Triangle: V=3, E=3, F=2 → 3−3+2 = 2 ✓
For simple connected planar graph with V ≥ 3:
Use to prove non-planarity: if E > 3V−6, graph is NOT planar.
A graph is planar iff it contains no subgraph that is a subdivision of K₅ or K₃,₃. (A subdivision replaces edges with paths.)
V=5, E=10. Check: E ≤ 3V−6 → 10 ≤ 9. FALSE → K₅ not planar.
V=6, E=9, bipartite so no triangles. Check: E ≤ 2V−4 → 9 ≤ 8. FALSE → K₃,₃ not planar.
Assignment of colors to vertices so that no two adjacent vertices share the same color. The minimum number of colors needed is the chromatic number χ(G).
Every planar graph can be colored with at most 4 colors. First major theorem proved with computer assistance (checking 1,936 reducible configurations).
| Graph | χ(G) | Reason |
|---|---|---|
| Bipartite (non-trivial) | 2 | 2-colorable (proven by BFS 2-coloring) |
| Odd Cycle C₂ₖ₊₁ | 3 | Need 3rd color for the "closing" vertex |
| Even Cycle C₂ₖ | 2 | Bipartite |
| Complete Kₙ | n | All pairs adjacent |
| Tree | 2 | Always bipartite |
| Planar Graph | ≤ 4 | Four Color Theorem |
| Petersen Graph | 3 | Not bipartite, not complete |
Assign colors in order: give each vertex the smallest color not used by its already-colored neighbors. Produces at most Δ(G)+1 colors where Δ is max degree. NOT always optimal.
χ(G) ≤ Δ(G) unless G is a complete graph or odd cycle, in which case χ(G) = Δ(G)+1.
Vertices = exams. Edge if same student takes both. Color = time slot. χ(G) = minimum slots needed.
In compilers, variables that are "live" at same time can't share a register. Coloring = register assignment.
Countries sharing border need different colors. Dual graph of map = planar graph → 4 colors always enough.
Sudoku is a graph coloring problem on a 81-vertex graph where edges connect cells in same row/col/box. χ = 9.