1,111 views

1 Answer

Best answer
2 votes
2 votes
Form a new graph H by adding a new vertex w  to G that is adjacent to every vertex of G.
 Then in H, every two non-adjacent vertices x, y  in G satisfy,
deg x in H+ deg y in H= deg x in G +1 + deg y in G + 1≥ n − 1+ 2 = n + 1 = V(H ) , and so all the edges
between vertices of G belong to the closure of H. Thus, the closure of H is complete and it
follows that H must have a Hamiltonian cycle, call it C. So it follows that C - w is a
Hamiltonian path in G
selected by

Related questions

1 votes
1 votes
2 answers
1
Ayush Upadhyaya asked Jun 2, 2018
1,599 views
Is every regular graph of degree d(d$\geq$3) non-separable?If not, give a simple regular graph of degree 3 that is separable.
0 votes
0 votes
0 answers
2
Ayush Upadhyaya asked Jun 2, 2018
657 views
Prove that in a connected graph G a vertex v is a cut-vertex if and only if there exist two(or more) edges x and y incident on v such that no circuit in G includes both x...
1 votes
1 votes
2 answers
3
3 votes
3 votes
1 answer
4
Sarvottam Patel asked Aug 15, 2016
3,925 views
If the intersection of two path is a disconnected graph, Show that the union of the two path has at least one circuit.