3
$\begingroup$

From the paper https://web.math.princeton.edu/~pds/papers/girth6/paper.pdf, a cubic (every vertex is degree 3), planar graph has girth (smallest length face) strictly less than 6. It is also true that a cubic, bipartite (all faces even length) graph contains a square (or a 2-gon).

I am interested in planar graphs with exactly one degree 2 vertex, the rest degree 3. Is it true that such a graph must contain a face of length 1,2, 3 or 5? (In other words, a face of length less than or equal to 5 that is not a square.)

$\endgroup$
3
$\begingroup$

You can prove half of that. One way to conclude something about the girth of a planar graph is via an inequality like this one: if the graph has $p$ vertices, $q$ edges, and girth $g$, then $q \le \frac{g(p−2)}{g−2}$.

For a cubic planar graph, we have $q = \frac32 p$, and we get an upper bound on $g$ that way. The upper bound is always less than $6$ (but approaches $6$ as $p \to \infty$).

If you have a single vertex of degree $2$, then $q = \frac32p - \frac12$, and the same argument still works. Solving for $g$, we get $g \le \frac{6p-2}{p+3} < \frac{6p}{p} = 6$. So there is always a face of length $1$, $2$, $3$, $4$, or $5$.

However, it's possible for all such faces to be squares. For example, take the skeleton graph of the truncated octahedron (which is $3$-regular) and then, to create a vertex of degree $2$, subdivide an edge that separates two hexagonal faces. You'll get a graph with $24$ degree-$3$ vertices and one degree-$2$ vertex, in which $6$ faces are squares, $6$ are hexagons, and $2$ are heptagons.

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