retagged by
5,728 views
37 votes
37 votes

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?

  1. Exactly seven edges leave every vertex.
  2. Exactly seven edges leave some vertex.
  3. Some vertex has at least seven edges leaving it.
  4. The number of edges coming out of vertex is odd.
  5. None of the above.
retagged by

6 Answers

Best answer
40 votes
40 votes
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$.
edited by
26 votes
26 votes
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.
1 votes
1 votes

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!

 

0 votes
0 votes

 

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)

Answer:

Related questions

5 votes
5 votes
1 answer
2