Prove that connected graph G, with 11 vertices and and 52 edges, is Hamiltonian Is this graph always, sometimes, or never Eulerian? Give a proof or a pair of examples to justify your answer
Could G contain an Euler trail? Must G contain an Euler trail? Fully justify your answer
 A: Let $h_{11}$ be the number of edge-disjoint Hamiltonian cycles in $K_{11}$.  Now if you remove $e$ edges from $K_{11}$, the maximum number of Hamiltonian cycles you could have destroyed is $e$.  If $e < h_{11}$ then there will be remaining Hamiltonian cycles.
If you show that $3 < h_{11}$, then there will be at least one Hamiltonian cycle left in your graph with 11 vertices and 52 edges.  There is a well known result regarding the number of of edge-disjoint Hamiltonian cycles in $K_n$ that you may have covered in class.  Otherwise you can just show that there are at least 4 of them in $K_{11}$ (say by explicitly writing down the cycles).
Regarding whether the graph is Eulerian and whether it has an Eulerian trail, you might want to recall some theorems about the conditions required on the degrees of the vertices in the graph.  Then it's easy to exhibit graphs with 11 vertices and 52 edges that meet / don't meet these conditions.
A: $G$ is obtained from $K_{11}$ by removing three edges $e_1,e_2,e_3$. We label now the vertices of $G$ the following way:
$$e_1=(1,3)$$
Label the unlabeled vertices of $e_2$ by the smallest unused odd numbers, and label the unlabeled vertices of $e_3$ by the smallest unused odd numbers. Note that by our choices $e_3 \neq (1,11)$, since if $e_3$ uses the vertex $1$, the remaining vertex is labeled by a number $\leq 9$.
Label the remaining vertices some random way.
Then $1-2-3-4-5-6-7-8-9-10-11-1$ is an Hamiltonian cycle in $G$. 
A: Below are the $5$ non-isomorphic $11$-vertex $52$-edge graphs.  The three non-edges are in blue, and a Hamilton cycle is highlighted in orange in each case.  The vertices are ascribed their degrees.  This is sufficient to determine the existence of an Eulerian trail and Eulerian circuit in each case using the properties:


*

*An undirected graph has an Eulerian trail if and only if at most two vertices have odd degree, and if all of its vertices with nonzero degree belong to a single connected component.


*An undirected graph has an Eulerian cycle if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single connected component.
(Source: Wikipedia.)


