# Las Vergnas theorem

I am supposed to prove that the graph satisfies the Las Vergnas theorem. Here is the graph: Las Vergnas theorem is the following:

$$G$$ is a graph and $$V(G)=(v_1,...,v_n)$$. There is no such $$i,j$$ such that $$i. Then $$G$$ is hamiltonian

But if I label the vertices like this: I found such $$i$$, $$j$$: $$i=2$$ and $$j=4$$, so the graph does not satisfy Las Vergnas theorem.

Is there something, which I misunderstood or where is the mistake.

Thanks

• @PrasunBiswas but then that is counterexample or? Because the theorem says that such numbers do not exist, but we found them Nov 10, 2020 at 17:00
• The theorem does not say that such numbers do not exist. The theorem says that if such numbers do not exist, then the graph is hamiltonian. Precision matters! Nov 10, 2020 at 18:06

Let $$G=(X,E)$$ be a simple graph of order $$n \ge 3$$. Let the vertices $$x_i$$ of $$G$$ be indexed arbitrarily, and let $$q$$ be an integer, where $$0 \le q \le n-1$$. If $$\left.\begin{array}{l}1 \le i < j \le n \\ i+j \ge n-q \\ d_G(x_i) \le i+q \\ d_G(x_j) \le j+q-1 \\ [x_i,x_j] \notin E\end{array}\right\} \implies d_G(x_i) + d_G(x_j) \ge n+q$$ then, for each $$F \subset E$$ with $$|F|=q$$ such that the connected components of $$(X,F)$$ are elementary chains, there exists a hamiltonian cycle that contains $$F$$.
Here, we want $$q=0$$, so the conditions are the same as in the question; the point that I am making is that the hypotheses in the question are satisfied if there is any ordering of the vertices that works.
In the case of your graph, if we swap the order of vertices $$v_1$$ and $$v_2$$ in your labeling, there will no longer be any pair $$(i,j)$$ violating the conditions, because the only two vertices in the right positions with the right degrees will be adjacent. So the graph does satisfy the hypotheses of the theorem.