Conditions are given for a finite set of natural numbers to be realizable as the vertex degree set of a graph with a given number of vertices and property P.

NEW

Problem: Reconstructed statement: For a graphical degree sequence $d$, let $R_P(d)$ be the graph whose vertices are the labeled simple realizations of $d$ having property $P$, with two vertices adjacent when the corresponding graphs differ by one 2-switch. A property $P$ is complete if $R_P(d)$ is connected for every $d$ for which it is nonempty. The question asks whether “planar” and “Hamiltonian” are complete. I resolve the question negatively: planarity is not complete.

Result: Let the vertex set be $\{0,1,\dots,7\}$ and fix the degree sequence

Consider the following two graphs.

Both have degree sequence $d$, and both are planar.

I claim they lie in different components of the planar realization graph.

Let $L=\{2,3\}$ be the two leaves, $A=\{6,7\}$ the two degree-$5$ vertices, and $B=\{0,1,4,5\}$ the four degree-$4$ vertices. For any planar realization $X$ of $d$, the leaves are not adjacent: otherwise the induced graph on the other six vertices would have $13$ edges, impossible for a planar graph on six vertices. Hence deleting the two leaves leaves a planar graph $C$ on six vertices with $12=3\cdot 6-6$ edges.

Thus $C$ is a maximal planar graph on six vertices. Equivalently, its complement in $K_6$ has three edges. A planar six-vertex graph with twelve edges has complement either a perfect matching or a path $P_4$ plus two isolated vertices; the other three-edge complements give either a vertex of degree $2$ in a maximal planar graph or contain a $K_{3,3}$.

If the complement is a perfect matching, then both leaves are attached to the two degree-$5$ vertices. If the complement is $P_4$ plus two isolates, then both leaves are attached to degree-$4$ vertices. Therefore in every planar realization of $d$, the number

is either $0$ or $2$, never $1$.

A single 2-switch can change the neighbor of at most one leaf, unless it uses both leaf edges, in which case it only swaps their neighbors or creates a leaf-leaf edge, the latter being nonplanar here. Hence along any planar-preserving switch, $t$ cannot change from $0$ to $2$.

But $t(G)=2$, while $t(H)=0$. Therefore $G$ and $H$ are planar realizations of the same degree sequence in different connected components of $R_{\mathrm{planar}}(d)$. Thus the property of being planar is not complete. Consequently the answer to the problem “Are the properties of being Hamiltonian and planar complete?” is negative.

Citation: No external citation used; the counterexample and proof are given above.