[Math] Is it correct to prove the Dirac’s theorem in the way I tried

graph theoryhamiltonian-pathproof-verification

Here is a proof from Wiki:
enter image description here

and another proof I found here:
http://faculty.wwu.edu/sarkara/dirac.pdf
enter image description here
enter image description here

I read them and tried it on my own, I haven't assumed that P is the longest path, and then I proved that P is a cycle and contains all the vertices, it seems more convinent, but I'm not sure, wether it is correct to prove in that way. Could someone help me? Thanks a lot.:)

Let G=(V, E), suppose P is a path in G, which consists of vertices from $\{v_1, v_2,…,v_k\}$ $\in$ V. Since degree of every vertex in V is at least $\frac{n}{2}$, and from $v_1$ to $v_{ \lceil \frac{k}{2} \rceil}$ or from $v_{ \lceil \frac{k}{2} \rceil}$to v_k there are less than $\frac{n}{2}$ vertices, and $v_1$ is connected to at least $\frac{n}{2}$ vertices from $v_2$ to $v_k$, and $v_k$ is connected to at least $\frac{n}{2}$ vertices from $v_1$ to $v_{k-1}$. Therefore there exists i, $1 \le i \le k$, that $\{v_1, v_{i+1}\}$, $\{v_i, v_k\}$ $\in$ E,therefore P is a cycle with tour below: $$(v_1, v_{i+1}, v_{i+2},…,v_{k-1}, v_k, v_i, v_{i-1},…,v_1,v_1)$$ and the length of which is k. Since $k \lt n$, suppose k=n-1, $v_x$ is a vertex which is not on the path P, and $v_x$ is connected to at least $\frac{n}{2}$ vertices as well. And since P is a cycle with less then n vertices, $v_x$ is connected to at least two adjacent vertices, therefore the length of P is extended to n, which is a contradiction to $k \lt n$. Therefore G contains a Hamiltonian cycle.

Best Answer

If you do not assume that $P$ is the longest path, then you're not guaranteed to be able to find an $i \in \{1,2,\dots,k-1\}$ such that $v_1 v_{i+1}$ and $v_i v_k$ are edges in the graph. In fact, if $P$ is sufficiently short (if it contains fewer than $\frac n2$ vertices) then it's possible that all of $v_1$'s neighbors except for $v_2$ are outside $P$, and all of $v_k$'s neighbors except for $v_{k-1}$ are outside $P$. In that case, your method of turning $P$ into a $k$-vertex cycle doesn't work.

Additionally, your logic for extending the cycle into a Hamiltonian cycle doesn't work. "Since $k<n$, suppose $k=n-1$" is not valid logic. And when $k < n-1$, vertices outside $P$ are not required to have $\frac n2$ neighbors in $P$. In that case, there might be no vertex $v_x$ with two neighbors in $P$ which are consecutive along the cycle.

(In fact, if $G$ is the complete bipartite graph $K_{n/2,n/2}$, then you can never extend a cycle in this way. If $C$ is any cycle in $K_{n/2,n/2}$, then no vertex $v$ outside $C$ can be adjacent to two consecutive vertices of $C$, because any two consecutive vertices are on different sides of the bipartition.)