Dark Mode

4,286 views

35 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?

- Exactly seven edges leave every vertex.
- Exactly seven edges leave some vertex.
- Some vertex has at least seven edges leaving it.
- The number of edges coming out of vertex is odd.
- None of the above.

39 votes

Best answer

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$.

1

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.

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.

"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$.

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$.

1

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)**