1
$\begingroup$

Here is a question from a textbook I’m reading,

prove that a simple graph with n vertices has a hamiltonian path if the sum of degree number of each two none adjacent vertices is n-1.

I know A graph with n vertices (where n > 3) is Hamiltonian if the sum of the degrees of every pair of non-adjacent vertices is n or greater.

I know Dirac's theorem for Hamiltonian graphs tells us that if a graph of order n greater than or equal to 3 has a minimum degree greater than or equal to half of n, then the graph is Hamiltonian

How can we use them to achieve the proper answer ? A hint or an answer would be appreciated.

Thank you in advance.

$\endgroup$
3
  • $\begingroup$ Do you know Ore's theorem? $\endgroup$
    – saulspatz
    May 19, 2020 at 6:16
  • $\begingroup$ @saulspatz I know both ore and Dirac theorem $\endgroup$ May 19, 2020 at 6:17
  • $\begingroup$ It's a simple consequence of Ore's theorem. $\endgroup$
    – saulspatz
    May 19, 2020 at 6:17

1 Answer 1

1
$\begingroup$

HINT

Add a new vertex $\omega$ to the graph, where $\omega$ is adjacent to each vertex of the original graph.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .