A connected graph G has 12 vertices and 64 edges. Is G Hamiltonian? Is G Eulerian?

Question

A connected graph G has 12 vertices and 64 edges. Is G Hamiltonian? Is G Eulerian? Do we have enough information to be able to tell?

Not sure where to start with this one! Can anyone help me out?

Answer 1

There are some nice ocnditions for a graph to be Eulerian or Hamiltonian. Here is the condition for a graph to be Eulerian:

A graph $G=(V,E)$ is Eulerian if and only if each vertex has an even degree.

Conditions for a graph to be Hamiltonian are very vast, from easy ones to hard and abstract ones. I will limit myself to this one, which will help us solve the problem:

A graph $G(V,E)$ is Hamiltonian if $\forall v\in V(G)$, $deg(v)\geq\frac{|V(G)|}{2}$ (Dirac's theorem)

Now, using these, you can see that $G$ doesn't have to be Eulerian, but it must be Hamiltonian.

One last hint: $K_{12}$ has $66$ edges