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.


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.