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

Question

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 !

Answer 1

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.

Answer 2

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.