1
$\begingroup$

enter image description here

I've gathered that it requires a cycle with degree 10 to be considered hamiltonian and it is bipartite so there can not be any odd cycle, lastly it is eulerian hence every edge set can be partitioned into cycles. However, I am not sure how to continue with this information at hand

$\endgroup$
1
$\begingroup$

Since it's Hamiltonian it contains a $C_{10}$ subgraph, and it has minimum degree at least $2$. Consequently, it's bipartition (which exists, since it's bipartite) must have two parts of size $5$, so the graph has maximum degree at most $5$. Moreover, it's connected and Eulerian, so every vertex has even degree: necessarily $2$ or $4$ in this case.

It has 18 edges, so the degrees sum to 36, by the Handshaking Lemma. Thus the degree sequence must be $(4, 4, 4, 4, 4, 4, 4, 4, 2, 2)$. Two examples are below (and hopefully it's clear how I constructed them):

enter image description here

They're Hamiltonian, as identified by the green Hamilton cycles. They're Eulerian because they have all-even degrees. They're bipartite, since the vertices are $2$-colored. And they're non-isomorphic, since in the first example the two degree-$2$ vertices are adjacent, and in the second example they're non-adjacent.

$\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.