Olympiad MethodsDifficulty 45-10055 tagged problems

Graph Theory Counting

Graph Theory Counting is the habit of modeling relationships as vertices and edges to count incidences, paths, and constraints. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$\sum_{v \in V} \deg(v) = 2\,|E|.$$

In any finite (undirected) graph, the sum of all vertex degrees equals twice the number of edges, because each edge is counted once at each of its two endpoints — the Handshake Lemma.

Why It Works

1
Form the set of incidences: pairs $(v, e)$ where vertex $v$ is an endpoint of edge $e$. Count this set two ways (double counting).
2
Counting by vertices: each vertex $v$ contributes exactly $\deg(v)$ incidences, so the total is $\sum_{v\in V}\deg(v)$.
3
Counting by edges: each edge has exactly two endpoints, so it contributes $2$ incidences, giving a total of $2|E|$.
4
The two counts of the same set are equal: $\sum_{v}\deg(v) = 2|E|$. An immediate corollary is that the number of odd-degree vertices is even.

Worked Examples

Example 1

At a party of $9$ people, can everyone shake hands with exactly $3$ others?

1
Model people as vertices and handshakes as edges; "shakes with $3$ others" means every vertex has degree $3$.
2
By the Handshake Lemma, $\sum_v \deg(v) = 2|E|$, so the degree sum must be even.
3
Here the degree sum is $9 \times 3 = 27$, which is odd.
4
An odd degree sum is impossible, so no such configuration exists (equivalently, the count of odd-degree vertices, $9$, must be even — contradiction).

Answer:

No — the required degree sum $27$ is odd, which the Handshake Lemma forbids.

Contest level

A graph has $10$ vertices and $25$ edges. Show that some vertex has degree at least $5$.

1
By the Handshake Lemma the degree sum is $\sum_v \deg(v) = 2|E| = 2\cdot 25 = 50$.
2
If every vertex had degree at most $4$, the sum would be at most $10\cdot 4 = 40 < 50$ — a contradiction.
3
So at least one vertex has degree $\ge 5$. (Equivalently, the average degree is $50/10 = 5$, and some value meets or beats the average.)

Answer:

Yes — average degree is $5$, so some vertex has degree $\ge 5$.

Olympiad / Challenge

Mantel's theorem: prove that a triangle-free graph on $n$ vertices has at most $\left\lfloor n^2/4 \right\rfloor$ edges, and exhibit a graph attaining the bound.

1
Let $G$ be triangle-free with vertex set $V$, $|V| = n$, and $m = |E|$ edges. Key local fact: for any edge $uv$, the endpoints $u$ and $v$ have no common neighbor (a common neighbor $w$ would make triangle $uvw$), and every neighbor of $u$ or $v$ is one of the $n$ vertices, so $\deg(u) + \deg(v) \le n$.
2
Sum this over all edges and double count: $\sum_{uv \in E}\bigl(\deg(u) + \deg(v)\bigr) \le mn$. The left side counts, for each vertex $v$, the quantity $\deg(v)$ once per incident edge — that is $\deg(v)$ times — so it equals $\sum_{v \in V} \deg(v)^2$. Hence $\sum_{v} \deg(v)^2 \le mn$.
3
By Cauchy–Schwarz, $\sum_{v} \deg(v)^2 \ge \dfrac{\left(\sum_v \deg(v)\right)^2}{n} = \dfrac{(2m)^2}{n} = \dfrac{4m^2}{n}$, using the Handshake Lemma $\sum_v \deg(v) = 2m$. Chaining, $\dfrac{4m^2}{n} \le mn$, so $m \le \dfrac{n^2}{4}$; as $m$ is an integer, $m \le \left\lfloor n^2/4 \right\rfloor$.
4
The bound is sharp: the complete bipartite graph $K_{\lfloor n/2\rfloor,\,\lceil n/2\rceil}$ is triangle-free (any triangle would need two vertices on the same side, which are nonadjacent) and has exactly $\lfloor n/2\rfloor\cdot\lceil n/2\rceil = \left\lfloor n^2/4 \right\rfloor$ edges.

Answer:

A triangle-free graph on $n$ vertices has at most $\left\lfloor n^2/4 \right\rfloor$ edges, attained by $K_{\lfloor n/2\rfloor,\,\lceil n/2\rceil}$.

Going Deeper

The Handshake Lemma generalizes: $\sum_v \deg(v) = 2|E|$ is the degree-counting case of double counting incidences; in bipartite graphs the same idea gives $\sum_{u\in U}\deg(u) = \sum_{w\in W}\deg(w) = |E|$.
Parity of the degree sum is a recurring AIME/olympiad gadget: it instantly rules out 'everyone has odd degree $k$ with an odd number of people' configurations, and underlies Euler-circuit existence (all degrees even).
Pitfall: the lemma counts a loop (edge from a vertex to itself) as contributing $2$ to that vertex's degree. In simple graphs there are no loops, but if loops/multi-edges are allowed you must honor that convention or the count breaks.

Spot the Signal

Look for problems where the key step is modeling relationships as vertices and edges to count incidences, paths, and constraints.
You can describe the hard part as modeling relationships as vertices and edges to count incidences, paths, and constraints, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the olympiad structure that calls for graph theory counting, then rewrite the givens around it.
Name the relation that makes Graph Theory Counting legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Graph Theory Counting just because the surface looks familiar; verify the required condition first.
Applying Graph Theory Counting because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let graph theory counting reveal the structural theorem; then compute only what remains.

Try it on:

Practice a contest problem where the key step is modeling relationships as vertices and edges to count incidences, paths, and constraints.