# Maximum outdegree of internal vertex in a multi-source single sink directed acyclic graph

I'm looking to try and get a bound on the maximum outdegree of an internal vertex in a DAG w/ multiple-source vertexes and a single sink vertex given the following constraints:

1. $\text{deg}^-(\text{sink}) = 2$
2. For any internal vertex, $1 \le \text{deg}^-(v) \le 2$
3. Source vertexes can have any outdegree.

Using the degree sum formula, my gut instinct says that the maximum outdegree of an internal vertex is 2 but I'm having difficulty formally proving it. However, I'm new to graph theory so I'm not sure if I'm even on the right track or if my intuition is leading me astray. Any help would is much appreciated!

• what is an interval vertex? Jun 15, 2017 at 18:23
• Sorry typo, edited now
– jaip
Jun 15, 2017 at 19:37

Consider the following graph

            -> v_1 ->
-> v_2 -> v_5 ->
-> v_3 ->
Source -> v -> v_4 -> v_6 -> sink


i.e. the graph $G=(V,E)$, with $V=\{source,v,v_1,v_2,...,v_6,sink\}$ and $E=\{(source,v),(v,v_1),(v,v_2),(v,v_3),(v,v_4),(v_1,v_5),(v_2,v_5),(v_3,v_6),(v_4,v_6),(v_5,sink),(v_6,sink)\}$. Source and sink here are two vertices and thus sink has in-degree exactly 2.

You can easily add more "layers" in the graph and thus increase $\deg^+(v)$. If you do not bound the total number of vertices in your graph, vertex $v$ can have arbitrarily high out-degree (something around $\deg^+(v)=\frac{n-1}{2}$, where $n=|V|$). So the answer would be that there can only be an upper bound that is depending on the number of vertices. Note however, that this upper bound might even be higher than the one in my example.

(Excuse me for that ugly scetch but I only have my phone with me and I am not allowed to upload pictures.)

• Sorry, I think I'm not entirely clear on the notation you're using because the way I'm understanding your graph, it violates one of the constraints. The sink must have an indegree of 2 and only one sink can exist (therefore all paths from any input must terminate at that sink). The way I'm reading your diagram, there are either >1 sinks or the sink has an in degree >2.
– jaip
Jun 16, 2017 at 20:51
• Sorry, if my Diagramm is misleading. I meant a graph $G=(V,E)$, with $V=\{source,v,v_1,v_2,...,v_6,sink\}$ and $E=\{(source,v),(v,v_1),(v,v_2),(v,v_3),(v,v_4),(v_1,v_5),(v_2,v_5),(v_3,v_6),(v_4,v_6),(v_5,sink),(v_6,sink)\}$. Source and sink here are two vertices and thus sink has in-degree exactly 2. Does that help? Jun 16, 2017 at 23:42
• Ok yes, now I see what you're saying. Definitely helps, thanks for the clarification!
– jaip
Jun 18, 2017 at 0:47
• I edited my answer so that it includes the clarification. If it answers your question please mark it as the correct answer. Jun 18, 2017 at 13:53
• Sorry that took a bit, thanks for the help!
– jaip
Jun 21, 2017 at 17:44