graph theory
Definitions of both:
Hamiltonian Circuit: Visits each vertex exactly once and consists of a cycle. Starts and ends on same vertex.
Eulerian Circuit: Visits each edge exactly once. Starts and ends on same vertex.
Is it possible a graph has a hamiltonian circuit but not an eulerian circuit?
Here is my attempt based on proof by contradiction:
Suppose there is a graph G that has a hamiltonian circuit. That means every vertex has at least one neighboring edge. <– stuck
Here is a $2$-regular graph that is not connected:
o---o o---o
| | | |
o---o o---o
Your reasoning about (b) and (c) is correct; (c) is the only one that must have an Euler circuit.
For (a), we're essentially after a sequence of the edges such that consecutive edges share an endpoint (and the first and last edges in the sequence also share an endpoint).
We start off with the sequence of edges defined by the Hamiltonian circuit: $$(1,2),(2,3),\ldots,(n-1,n),(n,1)$$ after relabeling the vertices such that $(1,2,\ldots,n)$ is the Hamiltonian circuit. Then we add edges outside of the Hamiltonian circuit to the sequence. Here's an illustration as to how we would do it:
The line graph of
has the Hamiltonian circuit: $$(1,2),\color{orange}{(2,4)},\color{orange}{(2,5)},(2,3),(3,4),\color{blue}{(4,6)},(4,5),(5,6),(6,1).$$ For (b), there's some 4-vertex example. Graphs with cut vertices don't have Hamiltonian circuits.
Best Answer
Take a graph which is just a cycle on at least 4 vertices, then add an edge between one pair of vertices. Where you added the edge, you will have an odd degree, so the graph cannot have an Eulerian cycle. But the original cycle gives a Hamiltonian cycle.
Another example: the complete graph on $n$ vertices, when $n$ is even.