Skip to main content
added 145 characters in body
Source Link
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

Yes, there is an extremely short and elegant proof by Carsten Thomassen. See this paper, Prop 2.5.

In fact it is so short that I'll give it in full:

Proof (by induction on $|V(G)|$). If $|V(G)|\le 4$ this holds by inspection so assume $|V(G)|\ge 5$.

Using induction, we can reduce the statement to the case where $G$ is 3-connected. So assume that $G$ is 3-connected. We claim that $G$ has a vertex $v$ which is not contained in any separating triangle. For, if $xyzx$ is a separating triangle in G such that $G - (x, y, z)$ has a component of smallest possible order, then no vertex in that component is contained in a separating triangle of $G$. Now consider any planar embedding of $G$. By the induction hypothesis, the edges of $G - v$ can be coloured in two colours such that no monochromatic triangle occurs. Now we colour the edges incident with $v$ in the same two colours such that no two consecutive edges are part of a monochromatic facial triangle. Then there is no monochromatic triangle at all and the proof is complete.

Added: Gordon has kindly pointed out that Carsten is colouring edges rather than vertices. So the original question is not yet answered.

Yes, there is an extremely short and elegant proof by Carsten Thomassen. See this paper, Prop 2.5.

In fact it is so short that I'll give it in full:

Proof (by induction on $|V(G)|$). If $|V(G)|\le 4$ this holds by inspection so assume $|V(G)|\ge 5$.

Using induction, we can reduce the statement to the case where $G$ is 3-connected. So assume that $G$ is 3-connected. We claim that $G$ has a vertex $v$ which is not contained in any separating triangle. For, if $xyzx$ is a separating triangle in G such that $G - (x, y, z)$ has a component of smallest possible order, then no vertex in that component is contained in a separating triangle of $G$. Now consider any planar embedding of $G$. By the induction hypothesis, the edges of $G - v$ can be coloured in two colours such that no monochromatic triangle occurs. Now we colour the edges incident with $v$ in the same two colours such that no two consecutive edges are part of a monochromatic facial triangle. Then there is no monochromatic triangle at all and the proof is complete.

Yes, there is an extremely short and elegant proof by Carsten Thomassen. See this paper, Prop 2.5.

In fact it is so short that I'll give it in full:

Proof (by induction on $|V(G)|$). If $|V(G)|\le 4$ this holds by inspection so assume $|V(G)|\ge 5$.

Using induction, we can reduce the statement to the case where $G$ is 3-connected. So assume that $G$ is 3-connected. We claim that $G$ has a vertex $v$ which is not contained in any separating triangle. For, if $xyzx$ is a separating triangle in G such that $G - (x, y, z)$ has a component of smallest possible order, then no vertex in that component is contained in a separating triangle of $G$. Now consider any planar embedding of $G$. By the induction hypothesis, the edges of $G - v$ can be coloured in two colours such that no monochromatic triangle occurs. Now we colour the edges incident with $v$ in the same two colours such that no two consecutive edges are part of a monochromatic facial triangle. Then there is no monochromatic triangle at all and the proof is complete.

Added: Gordon has kindly pointed out that Carsten is colouring edges rather than vertices. So the original question is not yet answered.

added 945 characters in body
Source Link
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

Yes, there is an extremely short and elegant proof by Carsten Thomassen. See this paper, Prop 2.5.

In fact it is so short that I'll give it in full:

Proof (by induction on $|V(G)|$). If $|V(G)|\le 4$ this holds by inspection so assume $|V(G)|\ge 5$.

Using induction, we can reduce the statement to the case where $G$ is 3-connected. So assume that $G$ is 3-connected. We claim that $G$ has a vertex $v$ which is not contained in any separating triangle. For, if $xyzx$ is a separating triangle in G such that $G - (x, y, z)$ has a component of smallest possible order, then no vertex in that component is contained in a separating triangle of $G$. Now consider any planar embedding of $G$. By the induction hypothesis, the edges of $G - v$ can be coloured in two colours such that no monochromatic triangle occurs. Now we colour the edges incident with $v$ in the same two colours such that no two consecutive edges are part of a monochromatic facial triangle. Then there is no monochromatic triangle at all and the proof is complete.

Yes, there is an extremely short and elegant proof by Carsten Thomassen. See this paper, Prop 2.5.

Yes, there is an extremely short and elegant proof by Carsten Thomassen. See this paper, Prop 2.5.

In fact it is so short that I'll give it in full:

Proof (by induction on $|V(G)|$). If $|V(G)|\le 4$ this holds by inspection so assume $|V(G)|\ge 5$.

Using induction, we can reduce the statement to the case where $G$ is 3-connected. So assume that $G$ is 3-connected. We claim that $G$ has a vertex $v$ which is not contained in any separating triangle. For, if $xyzx$ is a separating triangle in G such that $G - (x, y, z)$ has a component of smallest possible order, then no vertex in that component is contained in a separating triangle of $G$. Now consider any planar embedding of $G$. By the induction hypothesis, the edges of $G - v$ can be coloured in two colours such that no monochromatic triangle occurs. Now we colour the edges incident with $v$ in the same two colours such that no two consecutive edges are part of a monochromatic facial triangle. Then there is no monochromatic triangle at all and the proof is complete.

Source Link
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

Yes, there is an extremely short and elegant proof by Carsten Thomassen. See this paper, Prop 2.5.