Mutually disjoint triangles in certain planar graph

98 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 whose only odd faces are triangles, and for which no two such triangles 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.)

2

There are 2 best solutions below

1
On BEST ANSWER

Here is one such graph - or, more precisely, one such plane embedding of a graph, since the lengths of the faces are not properties of the graph itself. It has two faces of length 3 (including the external face), two faces of length 4, and two faces of length 6.

enter image description here

(Motivation: we start with a triangular pyramid, which has all the required properties except for the degree-2 vertex, and modify it a little to make it work.)

2
On

Take two cycles of the same order 2n+1, $C_a$ and $C_b$ and number each in clockwise fashion.

"Glue together" $v_{1a}$ and $v_{1b}$, and then do the same for $v_{2a}$ and $v_{2b}$, so that there is just one edge between $v_1$ and $v_2$.

Then, for each $i > 2$ create an edge between $v_{ia}$ and $v_{ib}$.

Finally, subdivide the edge between $v_1$ and $v_2$.