Graph Theory Reference
Graph Theory
A graph models objects and the connections between them; vertices represent objects and edges represent relationships or routes.
Solved Examples
Jump directly to a worked example by type.
Fact Table
| Idea | Meaning | Use or Check |
|---|---|---|
| Graph | A set of vertices together with a set of edges joining pairs of vertices. | For a simple graph, edges have no direction and no loops. |
| Degree | The number of edges incident to a vertex. | A loop, when allowed, contributes 2 to degree. |
| Path and cycle | A path follows edges from vertex to vertex; a cycle returns to its start. | A simple path does not repeat vertices. |
| Connected | Every pair of vertices is joined by some path. | A disconnected graph has separate components. |
| Euler trail | Uses every edge exactly once. | A connected graph has an Euler circuit when all degrees are even, and an open Euler trail when exactly two are odd. |
A Four-Vertex Network
The degrees are 2, 2, 3, and 1. Their sum is 8, twice the four edges.
Content Formulas
Handshaking Lemma
$$\sum_{v\in V}\deg(v)=2|E|$$
Complete Graph
$$|E(K_n)|=\binom n2=\frac{n(n-1)}2$$
Euler Circuit Test
$$\text{Connected and all vertex degrees even}$$
The handshaking lemma counts every edge twice, once at each endpoint. It follows that every graph has an even number of odd-degree vertices.
Classic Examples
Check the Handshaking Lemma
A graph has vertex degrees 2, 2, 3, and 1. How many edges does it have?
Solution Steps
- Add all vertex degrees.
- Divide by 2 because every edge has two endpoints.
$$2+2+3+1=8$$
$$|E|=\frac82=4$$
Decide Whether an Euler Route Exists
A connected graph has vertex degrees 2, 2, 3, and 1. Does it have an Euler circuit or an open Euler trail?
Solution Steps
- Count the odd-degree vertices.
- Use the connected-graph Euler criteria.
$$\deg(v)=3\text{ and }1\text{ are odd: there are exactly two odd vertices.}$$
The graph has an open Euler trail, but not an Euler circuit.
Count Edges in a Complete Graph
How many edges does the complete graph $K_5$ have?
Solution Steps
- Every pair of distinct vertices determines one edge.
- Choose 2 of the 5 vertices.
$$|E(K_5)|=\binom52=\frac{5\cdot4}{2}$$
$$|E(K_5)|=10$$