The Gateway to Computer Science Excellence
+2 votes
Which of the following is $\textbf{not}$ TRUE?

(a) In a complete graph $K_n$ ($n$ $\geq$ $3$), Euler circuit exists $\Leftrightarrow$ $n$ is odd.
(b) In a complete bipartite graph $K_{m,n}$ (m $\geq$ 2 and  n $\geq$2), Euler circuit exists $\Leftrightarrow$ m and n are even.
(C) In a cycle graph $C_n$($n \geq$3), Euler circuit exits for all $n$

(d) In a wheel graph $W_n$ ($n \geq 4$), Euler circuit exits $\Leftrightarrow$ $n$ is even.
in Graph Theory by Boss | 130 views

3 Answers

+2 votes
Best answer

Option d

If degree of all vertex is even then euler ckt is exist.

  • In complete graph (kn) . If n is odd then degree of vertex  become even . So it is always eular ckt for odd number of n.

by Boss
selected by
0 votes
I think (d) is correct as if n is even then the degree of the universal vertex will be (n-1) which implies no euler's circuit.
0 votes
Answer: D because whether 'n' be even or odd the degree of all vertices except the central vertex(connected to all vertices) will be 3 which is odd and for euler circuit to exist degree of all vertices should be even and for even to exist eulerian trail we need to have only 2 odd degree vertices. So there can' be possibility for Eulerian circuit.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,218 questions
59,856 answers
118,103 users