Graph Theory
Reference · Always free
Study graphs, paths, trees, and algorithms - the mathematics of networks and connections.
Concepts in this topic
- Graph Basics - Learn the fundamental terminology and types of graphs
- Paths & Connectivity - Explore paths, circuits, Euler paths, and Hamilton paths
- Trees - Learn about trees, spanning trees, and their properties
- Graph Algorithms - Learn BFS, DFS, shortest paths, and minimum spanning trees
Key formulas & identities
| Name | Formula | Meaning |
|---|---|---|
| Handshaking Theorem | ∑ deg(v) = 2|E| | The sum of all vertex degrees equals twice the number of edges |
| Edges in Complete Graph | |E(Kₙ)| = n(n-1)/2 | A complete graph on n vertices has n(n-1)/2 edges |
| Tree Edge Count | |E| = |V| - 1 (for any tree) | A tree with n vertices always has exactly n - 1 edges |
| Euler Circuit Condition | Euler circuit exists ⟺ connected ∧ every vertex has even degree | A connected graph has an Euler circuit if and only if all vertices have even degree |
| Euler Path Condition | Euler path exists ⟺ connected ∧ exactly 0 or 2 vertices have odd degree | A connected graph has an Euler path if it has exactly 0 or 2 vertices with odd degree |
| Cayley's Formula | Number of labeled trees on n vertices = nⁿ⁻² | The number of distinct labeled spanning trees of the complete graph Kₙ |
| Complete Bipartite Edges | |E(Kₘ,ₙ)| = m × n | A complete bipartite graph Kₘ,ₙ has m × n edges |
Sample practice problem
From the free practice sample - 76 guided problems cover this topic in interactive practice.
How many edges does the complete graph K₅ have?
- 5
- 10
- 15
- 20
Show answer
Answer: 10
K₅ has 5(5-1)/2 = 5(4)/2 = 10 edges. Every pair of the 5 vertices is connected.