retagged by
2,613 views
1 votes
1 votes

Which of the following is not true?

(a) Number of edge-disjoint Hamiltonian cycles in $K_7$ is $3$

(b) If $G$ is a simple graph with $6$ vertices and the degree of each vertex is at least $3$, then the Hamiltonian cycle exists in $G$

(c) Number of Hamiltonian cycles in $K_{4,4}$ = 72

(d) If $G$ is a simple graph with $5$ vertices and $7$ edges, then the Hamiltonian cycle exists in $G$

Please help me understand all the options.

retagged by

2 Answers

1 votes
1 votes
option-a)  In K7, we will have degree of each vertex will be 6 it means every edge is connected to remaining all 6-vertices. Hence we can form 3-edge disjoint graphs  by selecting 2 different  vertices each time for every vertex. And as all vertices will have degree 2 it means we can enter each vertex and leave the vertex hence making degree of each vertex-2. So, option-a is correct.

 

option-b) It is a direct theorem, It is dirac's theorem and according to it if we have n vertices and each vertex is having degree atleast n/2 then hamiltionian cycle will exist. (NOTE: converse of this statement is not true).

option-c): In K4,4 we will have the choices for selecting cycles as below.  'o' represents node.

                            (4)o     o(3)

                            (3)o     o(2)

                            (2)o     o(1)

                            (1)o     o(1)

the values in () includes possibilities for selecting any node in other set. The total possibilities are 144 but as they happens to be cycle it means end-vertices will be same "a-b-c-d-a" is same as "a-d-c-b-a" and hence we divide by 2 and it gives 72 exactly.

 

option-d) is false because we can draw graph with 5 vertices and 7 in edges in many ways and in one of the way if we take one of the vertex as pendant vertex the we can't have hamiltonian cycle in that case means we will be visiting one vertex more than once. Hence it is not true.
0 votes
0 votes
Option D Because 7>=8 which is false. M>=1/2 (n^2-3n+6) where M edges &N is vertices

Related questions

0 votes
0 votes
1 answer
4
Vegeta asked Sep 13, 2018
928 views
whats ans of this qn and please explain