Graph Theory – Proving Modal Number of Outgoing Edges Cannot Exceed 2

graph theory

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…

Best Answer

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.

Related Question