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$
    – LSpice
    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$
    – Fedor Petrov
    Commented Feb 2, 2022 at 1:28
  • $\begingroup$ @LSpice Hi I have corrected the title and also fixed the "rules" of the graph. $\endgroup$
    – R u c k s a c k
    Commented Feb 2, 2022 at 10:35
  • $\begingroup$ @FedorPetrov that is what I mean here yes. $\endgroup$
    – R u c k s a c k
    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$
    – R u c k s a c k
    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$
    – Fedor Petrov
    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$
    – Fedor Petrov
    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$
    – R u c k s a c k
    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$
    – Fedor Petrov
    Commented Feb 2, 2022 at 12:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .