This seemingly simple problem is doing my head in. I have tried doing a proof by induction over the edges of the graph but I just cannot seem to get it to work.


I am trying to prove that in a finite directed graph $G = (V, E)$ that obeys the following rules, any mode number of outgoing edges cannot exceed 2.


The rules:


* The graph has $|V| = n$ vertices - I've called them $0, 1, ..., n-2, n-1$.
* The graph has $|E| ≤ n$.
* Every vertex has 0 or 1 incoming edges.
* No vertex has an edge from itself to itself.
* The graphs are constructed by a process of adding edges between pairs of vertices according to the following rules:
	+ An edge can be added from any vertex $u$, but only to $v ≠ u$ when $v$ has no incoming edges already.
	+ Adding an edge from $u$ to $v$ when $u$ has no incoming edges means an edge must also be added from $v$ to $u$


An example of a graph that follows the rules, with $n = 2$:


* $V = \{0, 1\}$
* $E = \{ (0, 1), (1, 0) \}$
* Mode = 1
	+ there are 2 vertices with 1 outgoing edge
	+ therefore the modal number of outgoing edges is 1.


Another example of a graph that follows the rules, with $n = 4$:


* $V = \{0, 1, 2, 3\}$
* $E = \{ (0, 1), (1, 0), (0, 2), (1, 3) \}$
* Set of all modes = $\{0, 2\}$ (multimodal - see below)
	+ there are 2 vertices with 0 outgoing edges
	+ there are 2 vertices with 2 outgoing edges
	+ therefore there are two modal numbers of outgoing edges: 0, and 2.


The way I tried to formulate the inductive step was to let $T\_r$ denote the set of nodes that have $r$ outbound edges, and then to say:


For some $i$ in $\{0, 1, 2\}$, for all $j$ in $\{3, 4, ..., n-2, n-1\}$, $|T\_i| > |T\_j|$.


But I tie myself in knots trying to cover all the cases in making the inductive step.


Any help appreciated.


I feel like I'm going down a blind alley on this one. I haven't been able to come up with a counterexample either...



How to prove that the modal number(s) of outgoing edges cannot exceed 2?
The sum of outdegrees is at most $n$. Thus if certain value $d\geqslant 3$ appears, say, $k>0$ times, the value 0 must appear at least $(d-1)k>k$ times, and do $d$ is not modal.


