# DM-Graphs-Q14

Consider the following Graphs:

S1: Graph with $n$ vertices and each vertex has degree $n/4$

S2: Graph with 20 vertices such that for every 2 vertices $x, y ,\text{ }degree(x) + degree(y) \geq19$

Which of the following represents hamilton graph?

(A). Only S1

(B). Only S2

(C). Both S1 and S2

(D). Neither S1 nor S2

asked Jul 12, 2019 2 flags
reshown Jul 13, 2019

+1 vote
V1 ----------------- V2

V3-------------------V4

the above graph has 4 vertices ie n=4 , and each has a degree of n/4  eq to 1

and its not a hamiltonian graph, Hence Statement 1 is FALSE
answered Jul 15, 2019 by (1,080 points)
if in S2 degree(x)+degree(y)>=20 then it is hamiltonian
@tsaakashdoulwani26, what you're saying is sufficient condition for the graph to be Hamiltonian. There can be graphs for which deg(x) + deg(y) < 20, but they can still be Hamiltonian.