1
$\begingroup$

Let $G$ be a planar graph in which every vertex has degree 4 and there are 10 regions (faces). How many graphs up to isomorphism are there?

We can easily infer from the vertex sum and Euler's formula, that the number of vertices is 8.

I drew one but every other graph that I draw is isomorphic to it, so I suspect there is just one. Proving it is another matter. I tried using the fact that it must have an Eulerian cycle, defining the map from vertex to vertex by the edges in the path, but couldn't see an argument that the map must be well-defined and bijective. I tried using the fact that it must have a Hamiltonian path, and now the map is bijective but I could not see a way to prove that it satisfied the homomorphism property. I also thought about trying to construct an isomorphism by tracing out the graph, but there seemed to be too many choices that one could possibly make.

$\endgroup$
  • $\begingroup$ Next you need two quadrilateral and six triangle faces or one pentagon and nine triangles. For the two quadrilaterals they can share an edge or not. $\endgroup$ – Ross Millikan Feb 5 '18 at 5:42
1
$\begingroup$

You are correct; up to isomorphism there is just one 4-regular planar graph with 8 vertices, the square antiprism graph, this guy:

To just see how many there are, we can check e.g. Markus Meringer's list of regular planar graphs and see that there's just one 4-regular planar graph on 8 vertices.

To really demonstrate it, we can follow up on the hint by Ross Millikan in the comments. Each face of the planar embedding has at least three edges on its boundary. On the other hand there are 16 edges, and each edge is in two faces (because there cannot be a cut-edge; this is left as an exercise for the reader 😉.) So the sum of all the face lengths is 32. If all ten faces have length 3, that accounts for 30 already, so there are two "extra" edges to add to faces.

Hence we either have a pentagon and nine triangles, or two quadrilaterals and eight triangles. So you just need to show that the pentagon case, or two quadrilaterals that share an edge, or two quadrilaterals that share a vertex but no edge, can't possibly work.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.