+2 votes

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 in Discrete Maths by gbeditor (15,310 points)
reshown Jul 13 by gbeditor

1 Answer

0 votes
V1 ----------------- V2




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 by tssoumambanerjee-nit (1,040 points)
if in S2 degree(x)+degree(y)>=20 then it is hamiltonian