1
$\begingroup$

I'm stuck with this question.

1. Let G be a simple graph on 21 vertices with at least 200 edges. Show that G is Hamiltonian.

I tried to use Dirac's theorem to prove it but it is inconclusive because δ(G) = 10 < 21/2. And I don't think we have seen Ore's theorem in class.

Is there another way to prove it ?

Thank you very much !

$\endgroup$
3
$\begingroup$

The prove is pretty easy.

1- If $11\leq \delta (G)$, then G is Hamiltonian (by Dirac's theorem)

2- If $\delta (G)=10$, let $u\in G$ such that $d(u)$=10. Let $N(u)=\{u_1,u_2,\ldots,u_{10} \}$

Let $H$ be induced subgraph in $G$ such that $V(H)=V(G)-\{u\}$.

Since $E(G)=200$, then $E(H)=190$. Since in complete graph with 20 vertices there are 190 edge, then $H$ is complete graph.

In complete graph $H$ there exists hamiltonian cycles with successive vertices $u_1, u_2$ (property of complete graphs; i.e. if $x,y\in K_l$ "complete on $l$ vertices", then $\exists$ hamiltonian cycle with successive vertices $x$ and $y$).

Note that $u$ is connected to both $u_1$ and $u_2$ , then we have the result.

$\endgroup$
1
$\begingroup$

This is similar to your other question and you are on the right track with Diracs theorem: A simple graph with n vertices (n ≥ 3) is Hamiltonian if every vertex has degree n / 2 or greater.

Consider the complete graph on 21 vertices we know that has 210 edges, so consider maximum degree reduction of a given vertex and prove that it cannot go below n/2.

$\endgroup$
  • $\begingroup$ Yes but 21/2=10.5, for the theorem to hold every vertex must have a degree >= 11. If we remove 10 edges from the vertex then this vertex will have degree 10 ? $\endgroup$ – John Graig Dec 3 '15 at 20:03
  • $\begingroup$ Sorry! You are right in this case, luckily we have another bound we can use math.stackexchange.com/questions/30833/… $\endgroup$ – user2879934 Dec 3 '15 at 20:23
  • $\begingroup$ Does that make sense? That gives like 192 or something $\endgroup$ – user2879934 Dec 3 '15 at 20:40
  • $\begingroup$ Thank you, it does make sense, but i'm not sure that i'm allowed to use that formulae as it is for an assignment and we haven't seen it in class... I could prove the formula but again, I think it comes from Ore's theorem that we haven't seen in class either. $\endgroup$ – John Graig Dec 3 '15 at 21:06
  • $\begingroup$ I'll keep thinking about a better proof. $\endgroup$ – user2879934 Dec 3 '15 at 21:09

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.