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? 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. Graph Theory tifr2010 graph-theory degree-of-graph + – makhdoom ghaya asked Oct 10, 2015 retagged Jun 23, 2017 by Arjun makhdoom ghaya 5.7k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Bhagirathi commented Aug 30, 2014 reply Follow Share 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 1 votes 1 votes Marv Patel commented Aug 31, 2014 reply Follow Share yeap c is correct...check the below answer 0 votes 0 votes srestha commented Sep 25, 2018 reply Follow Share 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 1 votes 1 votes samir757 commented Jan 23, 2022 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.
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 rish1602 answered May 10, 2021 rish1602 comment Share Follow See all 0 reply Please log in or register to add a comment.
–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. a trip answered Sep 12, 2017 a trip comment Share Follow See all 0 reply Please log in or register to add a comment.