Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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:
Without additional requirement, this should be a counter example:
To solve the additional requirement, we will need the following gadget (which incidentally is another counter example without the additional requirement) :
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.
