3
$\begingroup$

I have a graph with $11$ vertices and $53$ edges and I'm trying to prove it is Hamiltonian. I know that a graph is Hamiltonian if $n \geq 3$ and $d(v) \geq \frac{n}{2}$.

I'm just having trouble proving that the smallest possible degree of a vertex in a graph with $11$ vertices and $53$ edges is greater than $5.5$.

$\endgroup$
2
$\begingroup$

Note that $K_{11}$ has $\binom{11}{2} = 55$ edges. So you remove two edges from a single vertex. In this case, $\delta(G) = 8 > 5.5$, where $\delta(G)$ denotes the minimum degree of $G$. It follows that $\delta(G) \geq 8$ in the general case.

$\endgroup$
1
$\begingroup$

Hint: how many edges does $K_{11}$ have?

$\endgroup$

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.