---
title: A Zoo of Graphs
summary: The named families you should recognise on sight — and the edge counts each one gives you for free.
difficulty: easy
tags: [definitions, counting]
see: [foundations/intro, foundations/walks, structures/trie]
---

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 | $P_n$ | $n-1$ | connected, exactly two vertices of degree 1 |
| cycle | $C_n$ | $n$ | 2-regular; exists only for $n \ge 3$ (simple graphs) |
| complete | $K_n$ | $\binom{n}{2}$ | every pair adjacent; $\Delta = n-1$ |
| star | $S_n$ | $n-1$ | one vertex of degree $n-1$; a tree with diameter 2 |
| wheel | $W_n$ | $2(n-1)$ | $C_{n-1}$ plus a universal hub |
| complete bipartite | $K_{a,b}$ | $ab$ | max edges with no triangle |
| hypercube | $Q_n$ | $n 2^{n-1}$ | vertices = bitmasks of length $n$; $n$-regular, bipartite |
| grid / lattice | $G_{a,b}$ | $2ab - a - b$ | planar, max degree 4 |
| complete multipartite | $K_{n_1,\dots,n_k}$ | $\frac{1}{2}\big(n^2 - \sum n_i^2\big)$ | complement of a disjoint union of cliques |
| empty / null | $\overline{K_n}$ | $0$ | $n$ isolated vertices |

:::idea title="Count edges by double counting"
Every number in that column comes from the same move: count the same thing twice. $Q_n$ has $2^n$ vertices each of degree $n$, so $m = n 2^{n-1}$. If you can compute degrees in two ways, you never have to "see" the pattern.
:::

:::figure src="Konigsberg_Graph.svg" caption="The graph that started the field: seven bridges of Königsberg, drawn as four land masses and seven edges. Multi-edges are exactly what makes Euler's degree condition the right one."
:::

## Vocabulary that decides algorithm choice

:::definition label="Simple, directed, weighted, looped"
- **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 @directed/definitions.
- **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.

:::definition label="Density and the extremal threshold"
Density is $\frac{2m}{n(n-1)} \in [0,1]$. A graph with $m > \binom{n-1}{2}$ must be connected: the maximum number of edges in a *disconnected* graph is a $K_{n-1}$ plus an isolated vertex.
:::

:::warning title="Two traps"
1. "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).
2. "Bipartite means the parts have equal size" — no; it means $V = A \sqcup B$ with all edges crossing. $K_{1,7}$ is bipartite.
:::

## Recognition is an algorithm
:::check
Given an adjacency matrix, $O(n^2)$ 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 @foundations/bipartite).
:::

```cpp recognise.cpp
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
```

:::problems
- [[CSES 1666]] Building Roads | https://cses.fi/problemset/task/1666 | easy | components
- [[CF 977E]] Cyclic Components | https://codeforces.com/problemset/problem/977/E | core | cycles
- [[SPOJ PT07Y]] Is it a tree? | https://www.spoj.com/problems/PT07Y/ | easy | trees
:::