Chapter 1 · Graphs and Models
A Zoo of Graphs
The named families you should recognise on sight — and the edge counts each one gives you for free.
Competitions rarely ask you to invent a graph; they hand you a shape and expect you to know its invariants. Learn these ten, and half of all "how many edges / what is the degree of…" questions become reflexes.
#The named families
| family | notation | |E| | notes |
|---|---|---|---|
| path | Pn | n-1 | connected, exactly two vertices of degree 1 |
| cycle | Cn | n | 2-regular; exists only for n ≥ 3 (simple graphs) |
| complete | Kn | C(n, 2) | every pair adjacent; Δ = n-1 |
| star | Sn | n-1 | one vertex of degree n-1; a tree with diameter 2 |
| wheel | Wn | 2(n-1) | Cn-1 plus a universal hub |
| complete bipartite | Ka,b | ab | max edges with no triangle |
| hypercube | Qn | n 2n-1 | vertices = bitmasks of length n; n-regular, bipartite |
| grid / lattice | Ga,b | 2ab - a - b | planar, max degree 4 |
| complete multipartite | Kn1,…,nk | (1)/(2)(n2 - ∑ ni2) | complement of a disjoint union of cliques |
| empty / null | Kn̄ | 0 | n isolated vertices |
Every number in that column comes from the same move: count the same thing twice. Qn has 2n vertices each of degree n, so m = n 2n-1. If you can compute degrees in two ways, you never have to "see" the pattern.
#Vocabulary that decides algorithm choice
- simple: no self-loops, at most one edge per pair. Most of this book assumes simple unless stated.
- multigraph: parallel edges allowed — the model for "two flights between the same cities".
- directed: edges are ordered pairs (u,v); see Orientations, In/Out-Degree, Strong vs Weak.
- weighted: each edge carries a number; only the weights matter for shortest paths, the topology is the same.
- self-loop (v,v): contributes 2 to deg(v) in the undirected case, 1 to both in- and out-degree when directed.
A k-regular graph has every degree equal to k; the handshaking lemma then forces kn even, which is the standard proof that a 3-regular graph on 9 vertices cannot exist.
Density is (2m)/(n(n-1)) ∈ [0,1]. A graph with m > C(n-1, 2) must be connected: the maximum number of edges in a disconnected graph is a Kn-1 plus an isolated vertex.
- "Graph with n vertices and n edges is a cycle" — false; it only has exactly one cycle, somewhere, possibly with trees hanging off it (a unicyclic graph).
- "Bipartite means the parts have equal size" — no; it means V = A ⊔ B with all edges crossing. K1,7 is bipartite.
#Recognition is an algorithm
Given an adjacency matrix, O(n2) checks settle most of the above: regular (all row sums equal), complete (all off-diagonal ones), tree (connected and m=n-1), bipartite (no odd cycle — BFS colouring, see Bipartite Graphs and 2-Colouring).
int n; cin >> n;
vector<string> a(n);
for (auto& s : a) cin >> s;
long long m = 0; bool simple = true;
vector<int> deg(n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) if (a[i][j] == '1') {
if (i == j) simple = false; // self-loop
m += (j > i); deg[i]++;
}
int d0 = deg[0];
bool regular = all_of(deg.begin(), deg.end(), [&](int d) { return d == d0; });
bool complete = m == 1LL * n * (n - 1) / 2;
bool tree = m == n - 1 && connected(a); // connectivity is the other half