This seemingly simple problem is doing my head in. I have tried doing a proof by induction over the vertices 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.
• If the graph has $|E| > 0$, there must be (at least) one pair of vertices $u$ and $v$ such that both edges $(u, v)$ and $(v, u)$ are in $E$.

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...

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...