I found this degree sequencing problem interesting and tried to work it out but got stuck. I would like to find the graphs with the following degree sequence:
For $ N>4 $, the degree sequence of a set of graphs is defined as follows:
$ (N, N, N, N, 4, 4, 4, ... ) $,
where the number of $ 4's $ in the degree sequence is equal to $ (N-2)^2 $.
For each $ N $ prove that there are at least two graphs with the given degree sequence.
Prove that for each $ N $ there is only one planar graph that satisfies the degree sequence.
If there is only one planar graph that satisfies the degree sequence is that interesting or uninteresting?
For $N=5$ the degree sequence is $(\color{blue}{5^4}, \color{red}{4^9})$ (where multiplicities have been indicated by using exponents. The obvious planar graph with this degree is
BUT this is not the only planar graph with this degree sequence !