A few graphs come up so often that they have names. Knowing their edge counts and degrees saves time, and each count is a small exercise in the handshake lemma or in combinations.
Key idea
The complete graph $K_{n}$ joins every pair of its $n$ vertices: $\frac{n(n-1)}{2}$ edges, every degree $n - 1$. The complete bipartite graph $K_{m,n}$ has two sides of $m$ and $n$ vertices, with every vertex joined to every vertex on the other side and none on its own: $mn$ edges. The cycle $C_{n}$ ($n \ge 3$) is a ring of $n$ vertices with $n$ edges; the path $P_{n}$ is $n$ vertices in a row with $n - 1$ edges.
Why it works
An edge of $K_{n}$ is a choice of two endpoints, so there are $\binom{n}{2} = \frac{n(n-1)}{2}$ of them. The handshake lemma agrees: $n$ vertices of degree $n - 1$ give a degree sum of $n(n - 1)$, which is twice the number of edges. In $K_{m,n}$ an edge is one choice from each side, so the product rule gives $mn$.
| Graph | vertices | edges | degrees |
|---|---|---|---|
| $K_{n}$ | $n$ | $\frac{n(n-1)}{2}$ | all $n - 1$ |
| $K_{m,n}$ | $m + n$ | $mn$ | $n$ on one side, $m$ on the other |
| $C_{n}$ | $n$ | $n$ | all $2$ |
| $P_{n}$ | $n$ | $n - 1$ | $1$ at the two ends, $2$ inside |
Each row passes the handshake test. For $K_{m,n}$: $m$ vertices of degree $n$ and $n$ vertices of degree $m$ give a degree sum of $2mn$, twice the edge count. For $P_{n}$: $1 + 1 + 2(n - 2) = 2(n - 1)$.
Worked examples
Worked example: Edges of a complete graph
How many edges does $K_{10}$ have?
- Choose the two endpoints: $\binom{10}{2} = \frac{10 \cdot 9}{2} = 45$.
Answer: $45$
Worked example: Working backward
A complete graph has $66$ edges. How many vertices does it have?
- $\frac{n(n - 1)}{2} = 66$, so $n(n - 1) = 132$.
- Two consecutive integers with product $132$: $12 \cdot 11$. So $n = 12$.
Answer: $12$
Worked example: Which are bipartite?
A graph is bipartite when its vertices split into two sides with every edge going between the sides. Are $C_{6}$, $C_{5}$ and $K_{2,4}$ bipartite?
- $C_{6}$: color the vertices alternately around the ring; six is even, so the last vertex differs from the first. Bipartite.
- $C_{5}$: alternating around a ring of five ends with two neighbors on the same side. Not bipartite.
- $K_{2,4}$: bipartite by definition, with its two sides.
Answer: $C_{6}$ and $K_{2,4}$ yes; $C_{5}$ no
Common mistake
Counting the edges of $K_{n}$ as $n(n - 1)$. Adding up "each vertex is joined to $n - 1$ others" counts every edge twice, once from each end. Check: for $K_{3}$, a triangle, the formula must give $3$, not $6$.