2
$\begingroup$

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

enter image description here

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<j, i+j \geq n, v_iv_j \notin E(G), deg(v_i) \leq i, deg(v_j) \leq j-1, deg(v_i) + deg(v_j) \leq n-1$. Then $G$ is hamiltonian

But if I label the vertices like this:

enter image description here

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

$\endgroup$
2
  • $\begingroup$ @PrasunBiswas but then that is counterexample or? Because the theorem says that such numbers do not exist, but we found them $\endgroup$
    – Peter F.
    Nov 10 '20 at 17:00
  • $\begingroup$ 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! $\endgroup$ Nov 10 '20 at 18:06
2
$\begingroup$

Let me quote the actual theorem (as stated in Berge's Graphs and Hypergraphs, on p. 208 of the 1973 edition):

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.

As a side note: it is incorrect to say "the graph satisfies the theorem" or "the graph does not satisfy the theorem". All graphs satisfy the theorem: it's a theorem! Some graphs don't satisfy the hypotheses of the theorem, but that's okay. The only counterexample would be a graph that did satisfy the hypotheses of the theorem, but wasn't hamiltonian: such a graph would not satisfy the theorem. Such graphs do not exist.

$\endgroup$
1
  • $\begingroup$ Thank you so much $\endgroup$
    – Peter F.
    Nov 10 '20 at 18:07

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.