retagged by
276 views
0 votes
0 votes

Let G be a simple undirected graph such that G contains only vertex 'u' of maximum degree and let D be a DFS tree of G such that D contains only vertex 'v' of maximum degree. Which of the following is True?

unchecked

[ A ]

'u' is same as 'v' always

unchecked Correct Answer

[ B ]

'u' is same as 'v' sometimes, but not always.

unchecked

[ C ]

Degree of 'u' in G is same as degree of 'v' in G

unchecked

[ D ]

None of the above

I don't understand this. Isn't 'u' is same as 'v' supposed to mean that both the graph and the dfs tree have the same vertex set. And I imagine the graph to be a single vertex with multiple self loops, hence having a degree of 2n. But the dfs tree should have just one vertex with a single self loop in this case, right?

retagged by

1 Answer

Best answer
1 votes
1 votes

First of all there will be no loops in a simple graph 

https://gateoverflow.in/115177/find-the-essential-prime-implicants

second we can eliminate A and D options by just assuming the Graph G as a disconnected Graph and the maximum degree vertex 'u' of G is not reachable from the source vertex then the 'u' vertex will no be present in the DFS tree itself ..so you can go with option B

selected by

Related questions

5 votes
5 votes
1 answer
1
manvi_agarwal asked Sep 15, 2018
2,451 views
Also let me know the approach to find back edges, cross edges, forward edges,How to solve these questions
1 votes
1 votes
1 answer
2
1 votes
1 votes
1 answer
4
Kuldeep Pal asked Jul 16, 2017
352 views