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.

enter image description here


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.

enter image description here

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

enter image description here

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:

enter image description here

(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.

  • $\begingroup$ Thanks, especially for the pedagogy. Based on these techniques it seems that (assuming above hypotheses) that a square and a triangle must share an edge, no? (This would be sufficient for my purposes.) $\endgroup$ Dec 31 '18 at 10:46
  • $\begingroup$ I’ve added this condition to the question. $\endgroup$ Dec 31 '18 at 10:56
  • 1
    $\begingroup$ I've addressed this condition, but maybe you can share whatever is driving you to add these extra conditions? Rather than saying "yes, is possible" to each of your questions, it might be best to address the underlying problem. $\endgroup$ Dec 31 '18 at 16:01
  • 1
    $\begingroup$ @MishaLavrov You are suggesting (correctly, I think) that the OP is asking an xy question: en.wikipedia.org/wiki/XY_problem, $\endgroup$ Dec 31 '18 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.