Mutually disjoint odd cycles in certain planar graph

100 Views Asked by At

Let G be a connected, planar graph for which every vertex has degree 3, except that one vertex has degree 2.

Is it possible to construct an example of such G for which no two faces of odd length share a common vertex?

(For my purposes I may assume there are no faces of length 1 or 2, in which case there must be an odd face of length at least 3. By the handshake lemma, there are an even number of, hence at least 2, such odd faces.)

1

There are 1 best solutions below

1
On BEST ANSWER

Infinite counter examples of this form (just keep adding two more squares):

The key is to have a face with even degree incident to only one face with odd degree. Here's another way to achieve this goal.

Consider any cubic polyhedron $P$, which has a face, $f$, of odd degree.

Chamfer $P$ once to get $P'$. $P'$ is still cubic, and any face originally in $P$ is now only incident to hexagons.

Now, chamfer $P'$ to get $P''$. Here, every face incident to $f$ will be a hexagon, which is incident to hexagons on every other edge. Thus you can subdivide any edge in $f$ to get your desired kind of graph.