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

We can have 8 vertex leave one vertex and 6 vertex leave another what does it mean??

---

sorry. It is edge.

---

sir can u explain with example

---

Take $n= 10$. Now, make 7 outgoing edges from all of the 10 vertices such that there are 7 incoming edges to  each of the 10 vertices.

---

Sir can we have multi-edges from one vertex to another vertex , or we have to consider only one edge only between each pair of vertices.

---

Sir Option (A) will be correct if the graph is simple since every vertex should have 7 incoming edges...Am I right?

Since it is not given graph is simple/multi, we go with option (C)...Am I thinking correct?

---

Option (A) will be correct only if the graph is Complete directed graph with 8 vertices where each vertex has exactly 7 indegrees and 7 outdegrees .

---

for simple graph only A is correct rt ?

---

have u considered simple graph?

---

Hello warrior

I don't think there is something like that.Why do you think there can't be multiple edges between same source and destination vertex ? Let $n=2$ (name vertex $V_{1}$ and $V_{2}$) from $V_{1}$ there are 7 edges going to $V_{2}$ and from $V_{2}$ there are 7 edges going to $V_{1}$.

https://en.wikipedia.org/wiki/Multigraph

---

@ Rupendra Choudhary Yes,its possible.But i think when in Qn not mention simple or multigraph so we should go with simple.what do u think?what is by default graph when not mention in Qn?

---

No , when graph would be simple , questioner would explicitly mention it. otherwise consider graph without any restriction.

---

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)