Study guide: Graph Theory
Overview
A graph is a set of vertices joined by edges. That simple structure models road maps, social networks, task dependencies, circuits and molecules. Graph theory asks about degrees, paths, cycles, connectivity and colourings.
Several of its best results are checkable conditions: you can decide whether a route that uses every edge exists just by counting degrees, without searching.
Key ideas explained
Basic vocabulary and the handshaking lemma
A simple graph has no loops or repeated edges. The degree of a vertex is the number of edges at it. Each edge contributes to two degrees, so Σ deg(v) = 2|E|. Consequently the number of odd-degree vertices is always even.
Euler and Hamiltonian routes
An Euler circuit uses every edge exactly once and returns to the start; it exists in a connected graph exactly when every vertex has even degree. An Euler path exists exactly when there are 0 or 2 odd vertices. A Hamiltonian cycle visits every vertex once; there is no simple test for it, although Dirac's theorem gives a sufficient condition (n ≥ 3 and every degree at least n/2).
Bipartite graphs and colouring
A graph is bipartite exactly when it has no odd cycle, which is the same as being 2-colourable. The chromatic number is the fewest colours needed so that adjacent vertices differ. For a connected planar graph, Euler's formula says v − e + f = 2.
Standard families
The complete graph Kₙ has n(n − 1)/2 edges. The complete bipartite graph K_{m,n} has m·n edges. A cycle Cₙ has n edges, and a path on n vertices has n − 1.
Worked examples
The Königsberg bridges
Problem. Four land masses are joined by seven bridges, with degrees 3, 3, 3 and 5. Can you cross every bridge exactly once?
- Degree sum: 3 + 3 + 3 + 5 = 14 = 2 × 7, which matches the seven bridges.
- All four vertices have odd degree, but an Euler path allows at most two.
Answer. No such walk exists. This is the problem that started graph theory.
Reading properties from a small graph
Problem. Vertices A, B, C, D with edges AB, BC, CD, DA, AC.
- Degrees: A = 3, B = 2, C = 3, D = 2, summing to 10 = 2 × 5.
- Exactly two odd vertices (A and C), so an Euler path exists but an Euler circuit does not. One such path is A–B–C–D–A–C.
- A, B, C form a triangle, which is an odd cycle, so the graph is not bipartite.
Answer. It has an Euler path from A to C, no Euler circuit, and is not bipartite.
Enter these same values in the calculator above and compare each step with the working shown here.
Common mistakes to avoid
- Confusing Euler (every edge once) with Hamiltonian (every vertex once).
- Forgetting that a loop adds 2 to a vertex's degree, or forgetting to halve the degree sum when counting edges.
- Thinking “connected” means every vertex is adjacent to every other. That is a complete graph.
- Calling a graph bipartite because it looks two-sided, without checking for odd cycles.
Where this shows up in computer science
- Routing, GPS and social-network analysis all treat their data as graphs.
- Graph colouring schedules exams without clashes and allocates registers in compilers.
- Dependency graphs order tasks in build systems; molecular graphs model chemistry.
Test yourself
Try each question before opening the answer.
How many edges does K₇ have?
7·6/2 = 21.
Can a graph have exactly three vertices of odd degree?
No. By the handshaking lemma the number of odd-degree vertices is even.
Does K₅ have an Euler circuit? Does K₄?
K₅ does, because every degree is 4. K₄ does not, because every degree is 3.