# Prove that $G$ with 21 vertices with at least 200 edges is Hamiltonian

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 !

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.

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.

• 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 ? – John Graig Dec 3 '15 at 20:03
• Sorry! You are right in this case, luckily we have another bound we can use math.stackexchange.com/questions/30833/… – user2879934 Dec 3 '15 at 20:23
• Does that make sense? That gives like 192 or something – user2879934 Dec 3 '15 at 20:40
• 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. – John Graig Dec 3 '15 at 21:06
• I'll keep thinking about a better proof. – user2879934 Dec 3 '15 at 21:09