+3 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, 2019 in Discrete Maths by gbeditor (44,560 points) 2 flags
reshown Jul 13, 2019 by gbeditor

3 Answers

+1 vote
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, 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.
0 votes
I got the solution for S1. Can someone please define solution for S2 as well?
answered Dec 14, 2019 by neerajpro20 (1,240 points)
here in the question it is mentioned about every pair of vertices(even the adjacent ones), but in ore's theorem it's only non-adjacent, so I guess here it will not be hamiltonian
0 votes
see ORE's theorem
answered Dec 29, 2019 by (300 points)