retagged by
5,712 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

0 votes
0 votes

By drawing the graphs, I observed that option B is also correct and option C is also correct. As in one of the example, the graph with 3 vertices had 7 edges leaving it, 6 edges leaving it and 8 edges leaving it.  Hence option B and C

–1 votes
–1 votes

If we denote Indegree and Outdegree of a vertex (v) by d+(v) and d-(v) respectively; then by using Degree-sum formula for directed graph,we knew  

{ summation of d+(v) } = { summation of d-(v)}= no. of edges   [verify formula from Kenneth Rosen Page no. 654, theorem 3]

Therefore; as given in ques,every vertex has exactly seven edges coming in( suppose there are n number of vertices). so, {summation of d+(v)}=7*n. and ALSO there should be exactly {summation of d-(v)}=7*n ; It 7*n outdegree edges can come from any no. of vertices,only thing is that their summation should be equal to indregee summation.

According to above description, i think Answer would be (e) none of the above. 

Answer:

Related questions

5 votes
5 votes
1 answer
2