1.

G is an undirected graph with n vertices and 26 edges such that each vertex of G has a degree at least 4. Then the maximum possible value of n is ___________(a) 7(b) 43(c) 13(d) 10This question was posed to me in final exam.This interesting question is from Graphs topic in portion Graphs of Discrete Mathematics

Answer»

Correct OPTION is (c) 13

To explain I would say: LET m be MIN degree and M be a max degree of a GRAPH, then m ≤ 2E/V ≤ M. Here, m=4, E=26, v=?

So, 4 ≤ (2*26)/V

V ≤ (52/4)

V ≤ 13 ⇒ V = 13.


Discussion

No Comment Found

Related InterviewSolutions