Finding a planar graph satisfying these properties

Question

I need to construct a 3-regular connected planar graph with a planar embedding where each face has degree 4 and 6. In addition, each vertex must be incident with exactly one face of degree 4.

seems to fit the description well if extended infinitely but unfortunately infinite graphs are not allowed. I spent so much time trying to construct such a graph! The hard part is that there is that annoying unbounded face outside everything...

Answer 1

The colours show the order in which I constructed the graph. Every vertex must be part of one face of order 4, so I start with a square (black, centre).

Now, each vertex is of order 3, and the four vertices have order 2, so extend one edge out from each. They're next to their face of order 4, so these edges must be parts of hexagons (blue).

We now have four vertices which are already of order 3 and missing their face of order 4, and eight vertices which are of order 2 and missing their face of order 4. Create the suitable faces (red).

Now each "edge" of the square formed by the red edges is really three edges, and they must each form part of a hexagon. The 4 corners of the red square are order 2, so they need one more edge each, and that brings us to 5 of the 6 edges of each hexagon, so just join them up in the green square.

Check: the outside face is also of order 4, so this works.

Answer 2

Put a hexagon ABCDEF down. Extend side AB to a square A'B', side CD to C'D', and side EF to E'F', so that now we have the hexagon with four squares sticking out of it. Along the line B'C' place two points U,V, along line D'E' place W,X, and along line F'A' place two points Y'Z'. Note that with these insertions the parts between the squares sticking out of the original hexagon are now also hexagons. Finally extend each of the last pairs UV outward to U'V', WX outward to W'X', and YZ outward to Y'Z' (creating three more squares) and throw in the edges connecting V'W', X'Y', and Z'U' so that the "outside" is another hexagon.

Answer 3

Let $f_4, f_6$ be the number of quadrangles and hexagons. Then we get the restrictions (count vertex-edge incidences, count face-edge incidences, Eulre's polyhedra formula, vertex-quadrangle incidences) $$\tag13v=2e$$ $$\tag24f_4+6f_6=2e$$ $$\tag3v+f_4+f_6=e+2$$ $$\tag4 v=4f_4$$ By combining these ($6\cdot(3)-2\cdot(1)-(2)$), one quickly finds $f_4=6$ and then also $v=24$, $e=36$, $f_6=8$. The $f_4=6$ reminds of a cube. Indeed, by cutting off the eight vertices of a cube we get a suitable polyhedron (which can be embedded into the plane)