5 votes 5 votes Let $\text{G = (V, E)}$ be a finite directed acyclic graph with $|\text{E}| > 0.$ Which of the following is not necessarily true? $\text{G}$ has a vertex with no incoming edge. $\text{G}$ has a vertex with no outgoing edge. $\text{G}$ has an isolated vertex, that is, one with neither an incoming edge nor an outgoing edge. None Graph Theory goclasses2024-dm-5-weekly-quiz goclasses graph-theory graph-connectivity 1-mark + – GO Classes asked May 11, 2022 • edited May 27, 2023 by Lakshman Bhaiya GO Classes 612 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes Since graph is finite directed acyclic graph so there must be some vertex with no incoming edge and there must be some vertex with no outgoing edge. C is not necessarily true. GO Classes answered May 11, 2022 GO Classes comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments sk91 commented Nov 25, 2022 i edited by sk91 Nov 26, 2022 reply Follow Share @BHOJARAMA and B are always true for any connected DAG. Also, DAG can have an isolated vertex with no edges and can be still connectedGiven in the question that no. of edges is greater than 0 and so we have minimum 1 edge. So, there must be atleast two vertices in the graph connected by this edgeNow, if we have a third vertex which is isolated , it will disconnect the graph. So, no. of edges plays a vital role in deciding option C 1 votes 1 votes BHOJARAM commented Nov 25, 2022 reply Follow Share thanx for correction@sk91… Yes,as given that |E|>0, so statements A and B are necessarily true... 0 votes 0 votes Pranavpurkar commented Jan 17, 2023 reply Follow Share its not necessary to have an isolated vertex. 0 votes 0 votes Please log in or register to add a comment.