Suppose I have a planar graph (without loops or multiple edges) with $3n$ edges such that it has $n$ faces and each face (including external) has six edges. Is it true that either: there exists two adjacent vertices with degree two, or there are no vertices of degree greater than three?

Additional requirement:

There is a connected route that passes every edge once and when you enter the face you should leave by the "opposite" edge, as in example below:



1 Answer 1


Without additional requirement, this should be a counter example: enter image description here

To solve the additional requirement, we will need the following gadget (which incidentally is another counter example without the additional requirement) :enter image description here Let $G$ be a planar graph with only hexagonal faces. For each edge of your $G$, follow the path made by taking the opposite edge of the face. You end up with a collection of cycles.

Take a face where there is distinct cycles passing through. Replace this face by the gadget, by matching the outer face of the gadget. Lets $u-v-w$ be two consecutive edges crossed by different cycles. Match $u-v-w$ with $13-15-8$. It is relatively easy to see that the two corresponding cycles will be one in the resulting graph. (We need to check the cases where two or three different cycles pass through the face). Moreover, this gadget will not add any new cycle, so the number of cycles obtained in the resulting graph will be strictly lower. Repeat the addition of gadgets until there is only one cycle left.

  • $\begingroup$ Thank you for the interesting example. I edited the questions with na additional requirement. $\endgroup$
    – Planetary
    Commented Mar 30, 2022 at 10:06
  • $\begingroup$ @Planetary I edited with an answer to your additional requirement $\endgroup$
    – caduk
    Commented Mar 30, 2022 at 13:03
  • $\begingroup$ Great solution., thanks. $\endgroup$
    – Planetary
    Commented Mar 30, 2022 at 14:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .