Extremal graph problems for beginners: the bound and the example

An extremal graph problem looks like one question and is really two. "What is the largest number of friendships among $n$ people if no three are all friends?" asks you to prove that nobody can do better than some number, and to show a group that actually reaches it. Beginners almost always do one half and stop. They find a nice example and call it the answer, or they prove a bound that nobody can reach and call it the maximum.

Neither earns full marks, because neither is an answer. So before any technique, this is the habit to build: every extremal answer is a bound plus a construction, and they must meet.

How to recognise one

The graph is rarely announced. You get people, friendships, handshakes, roads, matches. Translate first: people are vertices, the relationship is edges. Then look for one of three shapes.

• "At most how many …" or "what is the largest …" with a forbidden pattern. Most edges with no triangle, most roads with no closed loop, most matches with nobody playing three times. A maximum under a ban is the classic extremal question.
• "What is the smallest number such that every … must contain …" The same question turned inside out. Instead of the most edges that avoid a pattern, you want the size at which avoiding it becomes impossible.
• "Prove that if there are more than so many edges, then …" This is a maximum problem in disguise. It is the contrapositive of "the most edges you can have without the pattern is exactly that many", and you should usually prove it in that form.

Do the construction first

It sounds backwards, but find the example before the proof. The example tells you the number you are trying to prove, and a proof aimed at the right number is a far easier thing to find than a proof aimed at nothing.

Small cases are how you find it. For the triangle question: with 4 people, the best you can do is 4 friendships (a square). With 5, it is 6. With 6, it is 9. Draw them and a pattern appears: split the people into two camps and make everyone friends with everyone in the other camp, and nobody inside their own. Any three people include two from the same camp, who are not friends, so there is no triangle. With camps of size $\lfloor n/2 \rfloor$ and $\lceil n/2 \rceil$ that gives $\lfloor n^2/4 \rfloor$ friendships, which matches 4, 6 and 9.

Now you know the target. The proof has to show $\lfloor n^2/4 \rfloor$ cannot be beaten.

Then the bound: take the extreme vertex

This is where the extremal principle in graphs earns its name. Pick the vertex $v$ with the most friends, say $d$ of them.

Those $d$ friends of $v$ cannot be friends with each other, because any two of them plus $v$ would be a triangle. So every edge in the graph has at least one end outside that group of $d$. There are $n - d$ vertices outside it (including $v$ itself), and none of them has more than $d$ friends, because $d$ was the maximum. Every edge is counted at least once by those outside vertices, so

$$e \le d(n - d) \le \frac{n^2}{4}.$$

The last step is AM–GM, or just the fact that a product with a fixed sum $n$ is largest when the two parts are equal. Since $e$ is a whole number, $e \le \lfloor n^2/4 \rfloor$, and the bound meets the construction. That is Mantel's theorem, and it is the model for the whole subject.

Look at why the extreme vertex was the right choice. Choosing maximum degree gave two facts for the price of one: a large independent set (its friends) and a cap on everyone else's degree. Any vertex gives the first fact. Only the extreme one gives the second.

The other two shapes

The "smallest $n$" shape works the same way, with the halves renamed. Among any six people, three are mutual friends or three are mutual strangers is the bound: six is enough. The construction is five people sitting in a circle, each friends only with their two neighbours. No three are mutual friends, no three are mutual strangers, so five is not enough. Six is the answer only because both halves are there.

Counting problems hide an extremal step inside them. To show every 2-colouring of the edges of $K_6$ has at least two monochromatic triangles, you count the pairs of differently coloured edges at each vertex. A vertex with $r$ red edges and $5 - r$ blue ones has $r(5-r)$ such pairs, and that is at most 6. The maximising is the whole proof: at most 36 mixed pairs, each non-monochromatic triangle uses exactly two, so at most 18 of the 20 triangles are mixed. And the bound is exact, because some colouring has exactly two.

Underneath almost all of these sits one equation you should write without thinking: the degrees add up to twice the number of edges. It is the handshake lemma, and it is how a statement about vertices becomes a statement about edges. In Mantel's proof it is hiding in the line "every edge is counted at least once".

The other extreme: the longest path

Maximum degree is one extreme. The other one beginners should own is the longest path. If every vertex has at least $\delta$ neighbours, there is a path with at least $\delta$ edges. Take the longest path and look at its last vertex. All of its neighbours must already be on the path, or you could extend it. It has at least $\delta$ of them, so the path has at least $\delta + 1$ vertices.

The pattern is the same as before. You do not build the path. You assume the longest one and ask what being longest forces.

What to do with this

When you meet one of these, write three lines before anything else: the graph (what are the vertices, what are the edges), the extreme you will take (most edges at a vertex, longest path), and the construction you think is optimal. If you cannot write the third line, do small cases until you can.

The extremal principle in graphs page has the statement and where it sits in the ladder, and the pigeonhole principle page covers the counting that most of these bounds lean on. The problem archive has the problems above in full with difficulty and expected time, and the daily problem posts a new one every day in three tiers, no account needed.