0
$\begingroup$

Consider the following part of proof for Dirac's theorem:

Theorem (Dirac’s Theorem 1952) If G is a simple graph with n vertices where n>=3 and d(v)>=n/2 for every vertex v of G, then G is Hamiltonian.

Proof:We suppose that the result is not true. So, the graph G is Non-Hamiltonian. Then for some value of n>=3; there is a non-Hamitonian graph in which every vertex has degree at least n/2: Any proper spanning supergraph also has every vertex with degree at least n/2 because any proper spanning supergraph can be obtained by introducing more edges in G. Thus, there will be a Maximal Non- Hamiltonian graph of G with n vertices and d(v)=n/2 for every vertex v in G. But the graph G cannot be complete, since if G is complete graph Kn then it would be a Hamiltonian graph (for n>=3). Therefore, there are two nonadjacent vertices u and v in G. Let G + uv be the supergraph of G obtained by introducing an edge uv: Then, since G is Maximal Non-Hamiltonian graph, G + uv must be a Hamiltonian graph .... ....

Book : "Graph Theory with Algorithms and its Application" by Shantanu Saha Ray

I don't get it how all in a sudden author says "since G is Maximal Non-Hamiltonian graph". In any case author is missing something please explain or point a link to the proof of dirac's theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.