Jtdylktuy

I have a planar, connected graph with vertices of degree 3 except for one with degree 2. There is an odd, outer face of length at least 5, containing the degree 2 vertex. The inside faces consist of 3 mutually disjoint triangles,disjoint from the outer face, and the rest even.

EDIT: further suppose that no triangle and square share an edge. (Adjacent squares are permitted.)

Is such a graph possible?

Below is a non-example. It only has 1 triangle, and this is not disjoint from the outer, length 5, face (which contains the degree 2 vertex). Plus there is a square sharing an edge with a triangle.

The plan:

1. Start with a 3-regular planar graph which has 4 triangular faces and a bunch of even faces.


2. Subdivide an edge between a triangular face and an even face. That face becomes the external odd face, and the triangular face now has length 4. (But the three other triangular faces remain intact.)


3. The other triangular faces might touch the odd face, or each other. To fix this, subdivide them as shown in the diagram below (adding the edges in red). This leaves one triangular face, creates two length-4 faces, and leaves the parity of adjacent faces unchanged. We can do this in three different directions, and we should choose one that moves the triangle away from the face it's not supposed to be touching. Repeat this until the triangles are disjoint from everything they're supposed to be disjoint from.

For example, if we do this to the truncated tetrahedron (with three triangular and three hexagonal faces) we get the graph below:

If you are likely to have more such questions, you should be looking at the general principles at work here. To figure out this plan, we work backwards, simplifying the conditions required one at a time.

The degree-2 vertex is awkward, so let's look at what happens when we smooth it out (deleting it and connecting its neighbors by an edge directly). Then the odd exterior face becomes even, and the interior even face becomes odd. So now we have a 3-regular planar graph with 4 odd faces, at least 3 of them triangles. (All four of them might as well be triangles.)

The condition that the triangular faces be disjoint to each other and to the external face is awkward. So we develop a construction that lets us push a triangular face away from an exterior face. Now that condition goes away.

Finally, it's easy to find 3-regular planar graphs with the right number of faces among various polyhedral graphs, so those should be the places you start looking.

Step 3 of the plan can be changed to replace each triangle with the structure below:

(When we add it, the length of each face adjacent to the former triangle increases by 2, so the parity does not change.)

This not only makes sure that no triangles are adjacent, but also that each triangle is only adjacent to hexagons.