TIFR CSE 2010 | Part B | Question: 36

Question

In a directed graph, every vertex has exactly seven edges coming in. What can one always say about the number of edges going out of its vertices?

• A. Exactly seven edges leave every vertex.
• B. Exactly seven edges leave some vertex.
• C. Some vertex has at least seven edges leaving it.
• D. The number of edges coming out of vertex is odd.
• E. None of the above.

Comments

I feel option c is correct because there must be some vertex from which 7 edges are coming out else our given condition cantbe satisfied

---

yeap c is correct...check the below answer

---

is there any theorem like this, that outdegree is multiple of indegree?

I just got this, 

A directed graph G contains a closed Euler-trail if and only ifG is strongly connected and the indegree and outdegree are equal at each vertex

 http://math.mit.edu/~csikvari/introduction_graph_theory.pdf

---

total number of incoming edges = total number of out going edges.

7n = total number of outgoing edges. ( if we have n vertices.)

Now analyze the options.

You will find C to be the most suitable one.

Answer 1

Since $7$ edges come to every vertex, total no. of edges leaving $n$ vertices must be $7n$. So, option (A) is a possibility but it needn't be always true. We can have $8$ edges leave one vertex and $6$ edges leave another (and similarly any other combination of outgoing edges ensuring total no. of outgoing edges remain constant). But option (C) must always be true as if none of the $n$ vertices have at least $7$ edges leaving, sum of outgoing edges can never be $7n$.

Comments

Can i say total In-degree == Total out-degree == 7n and then 

" it is guaranteed that some vertex will have at least 7 vertices leaving it."...............via Pegionhole principle?

---

what if it is disconnected directed graph as it is not mentioned in the question

 

---

This question makes us realise that we must satisfy at least case first

Answer 2

Let $n$ be the number of vertices.

Total number of incoming edges $= 7 \times n$.

This should be equal to the total number of outgoing edges. So, either all vertices must have 7 edges leaving or some should have more than 7 leaving while others could have less than 7 leaving. But, it is guaranteed that some vertex will have at least 7 vertices leaving it.

So, (c) is the correct answer.

Only if we restrict $n$ to 8, exactly seven edges need to leave every vertex.

Comments

How this is true?

Only if we restrict nn to 8, exactly seven edges need to leave every vertex

---

"Only if we restrict $n$ to 8" means, if we assume $n=8$

So, if $n=8$ i.e. no. of vertices is $8$,

Total no. of incoming edges  $=7 \times n = 7 \times 8 = 56$

this should equal to,

Total no. of outgoing edges $ = \text{No. of vertices} \times \text{outgoing edges per vertex}  = n \times \text{outgoing edges per vertex}$

$\implies 56 = 8 \times x$

So, outgoing edges per vertex will be $7$.

---

@Arjun Sir, if we consider simple graph with no parallel edges then option A will also be true always?? pls correct me if wrong

Answer 3

C) Some vertex has at least seven edges leaving it 
I took 8 vertex and there is one vertex can be leaved without out edge and at least one will be there with 7 out edge!
 

Answer 4

 

In a directed graph, total no. of incoming edges = total no. of outgoing edges.

Let, no. of vertices in the graph be $n$.
Since, each of the $n$ vertices has $7$ edges coming in (given), therefore, no. of incoming edges = $7 \times n$ 

$\Rightarrow$  no. of outgoing edges = $7 \times n$

$\Rightarrow$ Total no. of edges leaving all the vertices must always be $7 \times n$ (multiple of $7$) even though individual vertices may have any no. of edges them, maybe less or more or even equal to $7$ edges.

$\Rightarrow$ There must always be some vertex must have at least $7$ edges leaving it so that the total no. of vertices is $7 \times n$.

$\Rightarrow$ Correct option: (c)