Is this degree sequence planar?

Question

For the degree sequence [6,6,4,4,4,4,2,2,2,2]. Then this graph has $f = 10$ by euler's formula. Let $T$ be the number of triangles. Then the inequalities $2e = 36 \geq 3T + 4(10 - T)$ shows that $T \geq 4$. Notice that $T \neq 10$. And $T = 9$ is also not possible since there will be a 9-side polygon. For $T = 4$, the graph will be consists of 4 triangles and 6 rectangles. But I don't know does that case exists or not. How should I proceed? Or someone could provide two graph with this degree sequence that one is not planar but the other is planar. Also there there exists an euler path but I don't know does it help or not.

Answer 1

Hi here are two graphs with the right degree sequence. One is non-planar ($K_3$ $_3$ is embedded) while the other is planar.

Answer 2

Initially you don't have to care about all degree 2 vertices. You can always create a degree 2 vertex either by subdividing an edge (which leaves the degrees of other vertices intact) or by replacing one edge with a triangle, by which I mean: introduce a new degree 1 vertex and connect it to two vertices of the same edge. Obviously, this operation increases the degree of two vertices by 1.

For a planar graph, start with a vertex of degree 6 and construct another degree 6 vertex from the remaining vertices. From there you'll have five degree 2 vertices some of which you will have to connect by an edge (while maintaining planarity) and eventually turn into deg 4 vertices.

To get a non-planar graph, start with a $K_5$. Your degree sequence is [4,4,4,4,4]. Replace one edge with a triangle (as described in 1st paragraph). You now have [5,5,4,4,4,2]. You can turn the same edge into a triangle again to get [6,6,4,4,4,2,2]. Now to one edge of degree 2 attach a triangle. You now should get [6,6,4,4,4,4,2,2,2]. We need one more vertex of deg 2 so simply subdivide any edge.