Practice Material Question

Question

If G is a connected graph with 6 vertices and maximum number of edges, then which of the following is true ?

 

(a) Euler path exists, but Euler circuit does not exist in G.

(b) Only Euler path exists in G.

(c) Euler circuit does not exists in G

(d) G is not traversable.

Answer 1

Correct answer - Option C.

In the mentioned graph, 

n=6,

e = 15 (Maximum edges = 6C2)

and also, it is connected, 

Therefore, we can infer that given Graph is K6 (Complete graph of 6 vertices).

 Every complete graph is K-1 regular.

Thus, it is a 5- regular graph i.e degree of every vertex is 5.

For an Euler circuit to be present, every vertex should have a even degree, which is false in this case .

Therefore, option C is True.