# Finding a planar graph satisfying these properties

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...

• Degree 6 or degree 8? Your diagram doesn't seem to fit your description. – Peter Taylor Jul 18 '13 at 21:34
• Oh, degree 6, not 8. My bad. The pattern can easily be extended to hexagons though. – ithisa Jul 18 '13 at 21:35
• Extend it to hexagons and it doesn't go infinite. – Peter Taylor Jul 18 '13 at 21:57

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.

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)

• Cutting off the eight vertices of a cube generates faces with degree 3. This is impossible; all faces need degree 4 or 6. – ithisa Jul 19 '13 at 15:31
• It's a truncated octahedron, not a truncated cube. – Peter Taylor Jul 19 '13 at 20:23

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.