1
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ What is a modal number of an edge? And is it of an edge, or, as you have it in the title, of a vertex? $\endgroup$ Commented Feb 2, 2022 at 1:00
  • 2
    $\begingroup$ @LSpice I think, it is a standard statistical terminology applied to the multiset of $n$ outdegrees of the graph. $\endgroup$ Commented Feb 2, 2022 at 1:28
  • $\begingroup$ @LSpice Hi I have corrected the title and also fixed the "rules" of the graph. $\endgroup$ Commented Feb 2, 2022 at 10:35
  • $\begingroup$ @FedorPetrov that is what I mean here yes. $\endgroup$ Commented Feb 2, 2022 at 10:36

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Can you go into more detail about why the value 0 must appear at least $(d-1)k$ times? I guess this refers to the vertices at the ends of the $d$ outgoing edges, but they could have non-zero outdegrees of their own, couldn't they? I don't see the connection between the sum of outdegrees being $n$ and your following statements. $\endgroup$ Commented Feb 2, 2022 at 10:42
  • $\begingroup$ If 0 appears at most $(d-1)k-1$ times, then the total sum is at least $dk+n-dk+1>n$ $\endgroup$ Commented Feb 2, 2022 at 10:58
  • $\begingroup$ After we observed that the sum of outdegrees is at most $n$, we may forget about the graph at all $\endgroup$ Commented Feb 2, 2022 at 10:59
  • $\begingroup$ Thanks Fedor, I need to look at this in more detail as I am not understanding it just by reading it through. Any more detailed step-by-step instructions are welcome. However in the meantime I will try to understand it and come back with more specific questions. Thanks $\endgroup$ Commented Feb 2, 2022 at 11:59
  • 1
    $\begingroup$ You have $n$ non-negative integers with sum at most $n$. There are $k$ integers equal to $d$. Thus the sum of rest $n-k$ integers is at most $n-kd$. Therefore at most $n-kd$ of them are positive, and others (at least $k(d-1)$ integers) are equal to 0. $\endgroup$ Commented Feb 2, 2022 at 12:49

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.