Question on degree sequence of eulerian, hamiltonian bipartite graph

566 Views Asked by At

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

1

There are 1 best solutions below

0
On

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.