Prove short reachability from an extremal vertex

Try

Three teams compare results: a defeats b, b defeats c, and c defeats a. Draw an arrow from winner to loser. No team defeats every other team directly. Nevertheless each team can reach either opponent by following at most two arrows. For instance a reaches c through b. We are studying this directed reachability, not assuming that winning is transitive.

A tournament here means a finite directed graph with exactly one arrow between each pair of distinct vertices. This mathematical model rules out ties and missing comparisons. It need not represent a sporting competition; the same graph can describe any complete collection of pairwise directions. A vertex is a king if it can reach every vertex in at most two directed edges. It reaches itself using zero edges.

Predict

The outdegree of a vertex counts arrows leaving it. Predict whether a vertex with maximum outdegree must be a king. Could another king have smaller outdegree? Keep these as two different statements: a sufficient condition need not be necessary.

In the three-cycle every outdegree is one. A tie for the maximum does not prevent us from choosing a maximizer. Predict whether the theorem should apply to all tied maximizers or just to one special choice. Also consider a graph with one vertex: the zero-step convention matters there.

Experiment

Use the explorer to inspect outgoing edges and short routes. Before checking a chosen vertex, list its direct neighbors and then the vertices reachable through each of those neighbors. A missing direct edge is not yet evidence against the king property. Keep the finite checks separate from the general proof below.

Predict a route, then inspect its witness

Each pair has exactly one directed edge: no ties, self-edges or missing pairs. Choose a start and predict which targets need two edges. Flip one orientation and explain which degrees and paths change. All results update immediately; the ten buttons below also provide a complete textual edge list.

Start vertexABCDEReset cyclic fiveUse transitive preset

The cyclic preset has i → j when j−i modulo 5 is 1 or 2 (A=0,…,E=4). The transitive preset directs every edge from an earlier letter to a later letter. Presets also reset the selected start to A.

A → B — flipA → C — flipD → A — flipE → A — flipB → C — flipB → D — flipE → B — flipC → D — flipC → E — flipD → E — flip

Outdegree is the number of arrows leaving a vertex. The five degrees sum to 10, one contribution per edge. Maximum degree: 2. All vertices attaining it: A, B, C, D, E. A maximum is a comparison with the other four degrees, not merely a vertex with some outgoing edge.

Exact witnesses from A; direct edges are preferred, then the first alphabetical intermediate vertex

Target	Outdegree	Maximum?	Route from A	Edges used
A	2	Yes	A	0
B	2	Yes	A → B	1
C	2	Yes	A → C	1
D	2	Yes	A → B → D	2
E	2	Yes	A → C → E	2

A is a king in this tournament: every target has a route using at most two edges. The start reaches itself with zero edges.

A missing short witness does not assert that the target is unreachable by a longer route. This bounded computation checks the direct edge and all five possible intermediate vertices for each target. It verifies the selected finite graph exactly, but is not a proof that every finite tournament has a king. The lesson proves why every maximum-outdegree vertex is one; a king need not have maximum degree.

Try the transitive preset with start E, then A. Return to the cyclic preset and check every start. Before flipping an edge, predict the two degrees that will change and one route that might be lost or replaced. State your evidence in the lesson response; this temporary explorer saves nothing and awards no completion.

For an independent paper example, keep a→b→c→a and add a fourth vertex d, with a→d, b→d and d→c. This specifies every pair exactly once. Compute all four degrees before reading the table.

Vertex	Outgoing neighbors	Outdegree	Route from c
a	b, d	2	c→a
b	c, d	2	c→a→b
c	a	1	Zero edges
d	c	1	c→a→d

Vertex c is a king even though its degree is not maximum. This refutes the converse of our prediction, not the prediction itself. To challenge the forward implication, we would need a maximum-degree vertex that fails to reach some target within two edges.

Understand

Here is a proof for every finite nonempty tournament. Choose any vertex v of maximum outdegree; it exists because the nonempty finite set of degrees has a maximum. Write S for the set of outneighbors of v, so the number of members of S equals its outdegree.

Suppose, seeking a contradiction, that a vertex w is not reachable from v in at most two steps. Then w is not v, because zero steps reach v. It is not in S, because one step reaches every member of S. Since exactly one orientation connects v and w, the edge must be w→v.

Now take any u in S. If u→w, then v→u→w would reach w in two steps. That is forbidden by the supposition. The unique orientation between u and w must therefore be w→u. This argument applies to every member of S.

Consequently w has outgoing edges to all members of S and also to v. These are distinct destinations, since v is not its own outneighbor. Thus w has at least |S|+1 outgoing edges, strictly more than v. This contradicts the maximal choice of v. No such unreachable w exists, so v is a king.

The strict extra one is the heart of the proof. We did not assume a unique maximum, so every tied maximizer satisfies the conclusion. We also did not assume transitivity. The directed three-cycle is fully compatible with the argument. In a singleton tournament the sole vertex is a king by the zero-step convention. The empty tournament is excluded because it has no vertex whose existence could satisfy the conclusion.

Completeness is essential. In a graph containing only p→q and an isolated r, p is the unique maximum-degree vertex, yet cannot reach r. The failed step is precise: absence of p→r no longer forces r→p. The graph is finite and nonempty, but it is not a tournament.

Apply

Construct a five-vertex tournament on residues 0 through 4. Direct i→j when j−i modulo 5 is either 1 or 2. Check why exactly one direction is chosen for each distinct pair: the opposite difference is 5 minus the original difference. Each vertex has two outgoing edges, so the theorem already proves that all five are kings.

Supply a second certificate without invoking the theorem. Targets at differences 1 and 2 are direct. A difference of 3 can be made by steps 1 then 2; a difference of 4 by steps 2 then 2. This covers every possible target from every starting vertex. A symmetric drawing may suggest the construction, but the residue argument verifies all orientations and routes.

Finally distinguish short reachability from simple cycles. A walk may revisit vertices; a simple cycle repeats only its start at the end. Two directed cycles sharing just one vertex can make vertices in different branches mutually reachable without putting them on one common simple cycle. The written task asks for both routes and a proof of that obstruction, so neither a suggestive picture nor a search failure is the whole certificate.

Continue

When applying an extremal proof, name the quantity being maximized, explain why a maximizer exists, and derive a strictly better competitor from a supposed failure. Check each hypothesis at the step where it is used. The practice separates direct constructions, general proofs, false converses and changed graph models. The explorer can verify a finite example; the outneighbor comparison explains why the theorem holds for every finite nonempty tournament.