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 |