Two isomorphic 9 vertex graphs Given the ordered degree sequence of a hamiltonian circuit in a maximal planar graph. Can we have different maximal planar graphs with the same ordered degree sequence?
The hamilton circuit in both graphs have the same ordered degree sequence, but are isomorphic. Both have a 5-3 and a 5-6 edge
On
Here is the graphical result after I understood Misha's answer. The three 9vertex graphs have the same ordered degree sequences in the hamilton circuit. The two left are isomorphic, the two right are not.3MPG's on 9 vertices
If trying small examples doesn't work (and it doesn't, because very small examples don't exist), your next step should be trying out slightly larger examples with software.
Go to Brendan McKay's graphs page and you'll be able to download a
.g6file of all the connected $9$-vertex planar graphs. (With $8$ or fewer, this won't work.)From here, pick out the ones with $21$ edges, and from there the Hamiltonian ones. Finding the degree sequence along each Hamiltonian cycle of each graph that's left results in some overlap; for example, there are two graphs with the ordered degree sequence $5, 5, 5, 3, 6, 3, 6, 3, 6$.
Here are these two planar graphs, with the corresponding Hamiltonian cycles $(a,b,c,d,e,f,g,h,i,a)$ highlighted. One quick way to see that these are not isomorphic is that in the first graph, any two vertices of degree $3$ have a common neighbor; in the second graph, $d$ has neighbors $\{b,c,e\}$ but $h$ has neighbors $\{a,g,i\}$.