Mixing
4 color theorem equivalent to cubic planar bridgeless are 3 edge colorable
$begingroup$
To follow on
[How to prove Tait's theorem about planar cubic bridgeless graph being 3-edge-colorable?
The four-color theorem is equivalent to the claim that every planar cubic bridgeless graph is 3-edge-colorable.
I disagree with the solution given (As stated in my comment). The provided links does not proove the equivalence. It shows
1) from 4 color-theorem, how to build a 3-edge coloring for bridgeless cubic graph
2) from a 3-edge-coloring, how to build a 4 face coloring for the same graph
The theorem by Tait is much more powerful. If I can 3-edge color any cubic bridgeless planar graph, then I can 4-color ANY planar graph (not just cubic bridgeless planar).
Any idea how to prove the equivalence. I cannot find the original paper from Tait. Lots of reference but never the actual proof.
The implication 4CT $Rightarrow$ 3-edge-coloring for bridgeless planar cubic graph is easy.
The other implication is the one missing :
$$ { forall G, text{ cubic, planar, bridgeless}, exists text{ a 3-edge coloring}}$$
$$Rightarrow$$
$${forall G, text{ planar,} exists text{a 4-vertex-coloring}}$$
graph-theory coloring
asked Jan 8 at 12:18
Thomas LesgourguesThomas Lesgourgues
51114
$endgroup$
add a comment |
$begingroup$
To follow on
[How to prove Tait's theorem about planar cubic bridgeless graph being 3-edge-colorable?
The four-color theorem is equivalent to the claim that every planar cubic bridgeless graph is 3-edge-colorable.
I disagree with the solution given (As stated in my comment). The provided links does not proove the equivalence. It shows
1) from 4 color-theorem, how to build a 3-edge coloring for bridgeless cubic graph
2) from a 3-edge-coloring, how to build a 4 face coloring for the same graph
The theorem by Tait is much more powerful. If I can 3-edge color any cubic bridgeless planar graph, then I can 4-color ANY planar graph (not just cubic bridgeless planar).
Any idea how to prove the equivalence. I cannot find the original paper from Tait. Lots of reference but never the actual proof.
The implication 4CT $Rightarrow$ 3-edge-coloring for bridgeless planar cubic graph is easy.
The other implication is the one missing :
$$ { forall G, text{ cubic, planar, bridgeless}, exists text{ a 3-edge coloring}}$$
$$Rightarrow$$
$${forall G, text{ planar,} exists text{a 4-vertex-coloring}}$$
graph-theory coloring
asked Jan 8 at 12:18
Thomas LesgourguesThomas Lesgourgues
51114
$endgroup$
add a comment |
$begingroup$
To follow on
[How to prove Tait's theorem about planar cubic bridgeless graph being 3-edge-colorable?
The four-color theorem is equivalent to the claim that every planar cubic bridgeless graph is 3-edge-colorable.
I disagree with the solution given (As stated in my comment). The provided links does not proove the equivalence. It shows
1) from 4 color-theorem, how to build a 3-edge coloring for bridgeless cubic graph
2) from a 3-edge-coloring, how to build a 4 face coloring for the same graph
The theorem by Tait is much more powerful. If I can 3-edge color any cubic bridgeless planar graph, then I can 4-color ANY planar graph (not just cubic bridgeless planar).
Any idea how to prove the equivalence. I cannot find the original paper from Tait. Lots of reference but never the actual proof.
The implication 4CT $Rightarrow$ 3-edge-coloring for bridgeless planar cubic graph is easy.
The other implication is the one missing :
$$ { forall G, text{ cubic, planar, bridgeless}, exists text{ a 3-edge coloring}}$$
$$Rightarrow$$
$${forall G, text{ planar,} exists text{a 4-vertex-coloring}}$$
graph-theory coloring
asked Jan 8 at 12:18
Thomas LesgourguesThomas Lesgourgues
51114
$endgroup$
To follow on
[How to prove Tait's theorem about planar cubic bridgeless graph being 3-edge-colorable?
The four-color theorem is equivalent to the claim that every planar cubic bridgeless graph is 3-edge-colorable.
I disagree with the solution given (As stated in my comment). The provided links does not proove the equivalence. It shows
1) from 4 color-theorem, how to build a 3-edge coloring for bridgeless cubic graph
2) from a 3-edge-coloring, how to build a 4 face coloring for the same graph
The theorem by Tait is much more powerful. If I can 3-edge color any cubic bridgeless planar graph, then I can 4-color ANY planar graph (not just cubic bridgeless planar).
Any idea how to prove the equivalence. I cannot find the original paper from Tait. Lots of reference but never the actual proof.
The implication 4CT $Rightarrow$ 3-edge-coloring for bridgeless planar cubic graph is easy.
The other implication is the one missing :
$$ { forall G, text{ cubic, planar, bridgeless}, exists text{ a 3-edge coloring}}$$
$$Rightarrow$$
$${forall G, text{ planar,} exists text{a 4-vertex-coloring}}$$
graph-theory coloring
graph-theory coloring
asked Jan 8 at 12:18
Thomas LesgourguesThomas Lesgourgues
51114
asked Jan 8 at 12:18
Thomas LesgourguesThomas Lesgourgues
51114
edited Jan 8 at 12:29
Thomas Lesgourgues
asked Jan 8 at 12:18
Thomas LesgourguesThomas Lesgourgues
51114
asked Jan 8 at 12:18
Thomas LesgourguesThomas Lesgourgues
51114
asked Jan 8 at 12:18
Thomas LesgourguesThomas Lesgourgues
51114
51114
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Suppose we want to 4-color the vertices of a planar graph.
We may assume it's simple, because loops are forbidden and multiple edges don't affect coloring.
We may assume it's a maximal planar graph (that is, a planar triangulation), because adding more edges to triangulate the graph only makes the problem harder.
All planar triangulations on at least 4 vertices are 3-connected.
Instead of coloring the vertices of this graph, we can color the faces of its dual. The dual is another planar graph. It is cubic (because we started with a triangulation) and it is 3-connected (because it's the dual of a simple planar 3-connected graph) so in particular it is bridgeless.
So we have reduced the problem to coloring the faces of a planar cubic bridgeless graph, which is the kind of graph that Tait's theorem applies to.
answered Jan 8 at 17:39
Misha LavrovMisha Lavrov
45.8k656107
$endgroup$
$begingroup$
I under the reduction to the dual problem. But how do you go from a 3-edge coloring to a 4 face coloring? The provided link explain how to do it, but does not give a proof that the coloring is valid.
$endgroup$
– Thomas Lesgourgues
Jan 8 at 19:39
$begingroup$
The coloring is valid because two adjacent faces are either separated by a cyan-or-orange edge (and are different in the first picture) or by a cyan-or-magenta edge (and are different in the second picture), so they're different in the overlay.
$endgroup$
– Misha Lavrov
Jan 8 at 20:35
$begingroup$
I had an issue visualising why every map obtained by deleting one colored edges are two faces colorables. The fact that the map is cubic is used here to deduce that the cycle are disjoints. I have everything written down. thanks.
$endgroup$
– Thomas Lesgourgues
Jan 8 at 20:51
$begingroup$
Another way to think about the construction is to think of the face colors as $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$ and to think of the edge colors as $(+0,+1)$, $(+1,+0)$, $(+1,+1)$. Make two adjacent faces differ by adding the edge color (mod 2). This is obviously a proper coloring, but it takes work to check that it's well-defined.
$endgroup$
– Misha Lavrov
Jan 8 at 20:54
add a comment |
$begingroup$
Why do you say that the explanation in the link does not prove the equivalence? You can decide to color the faces of the map OR you can color the edges of the same map. Once you have finished coloring one or the other (faces or the edges) you can switch to the other the way described in the link. The difficulty of three coloring the edges or four coloring the faces is the same. Since one has already been proved the other is proved too.
About the theorem of Tait, there is no theorem of Tait, at least not about four coloring.
The equivalency only states that for the same map (not any map) if you find one coloring (faces of edges) you can switch to the other coloring, it does not say that it is easier to find one or the other coloring. To go from one coloring to the other (related to the same map) the algorithm is described in the link. The algorithm is the proof of the equivalency.
UPDATE (25/Jan/2019): The proof should be here:
- P.G. Tait, ”On the colouring of maps”, Proceedings of the Royal Society
of Edinburgh Section A, 10: 501-503, 1878-1880.
- https://www.cambridge.org/core/journals/proceedings-of-the-royal-society-of-edinburgh/article/4-on-the-colouring-of-maps/6385395D337371EE9ED16C6AA6694AC0
answered Jan 24 at 2:34
Mario StefanuttiMario Stefanutti
604614
$endgroup$
$begingroup$
I'm not sure what you mean by "there is no theorem of Tait" when answering a question that quotes Tait's theorem. Do you mean that the equivalency was proven by someone else?
$endgroup$
– Misha Lavrov
Jan 24 at 3:52
$begingroup$
No, this is not only about the equivalence between 4-face coloring and 3 edge coloring. it is more powerfull. If you can 3-edge color any bridgeless, cubic planar graph, then you can 4-face color any planar graph. Indeed if $G$ is a planar graph, then you can consider its maximum graph $G'$, hence a triangulation, and looking at the dual $G^{'*}$, this graph is cubic (because $G'$ is a triangulation), planar (because $G'$) and bridgeless (because $G'$ is a triangulation). Then you can 3-edge this graph, and transfer this to a 4-face coloring of $G'$, hence of $G$.
$endgroup$
– Thomas Lesgourgues
Jan 24 at 8:56
$begingroup$
And this equivalence was prooven prior to the 4 color theorem. Tait wanted to use it in order to proove the 4 color theorem, assuming that any bridgeless cubic planar graph admits an Hamiltonian cycle (and therefore 3 edge colorable). This was disprove by the Petersen Graph, the first example of cubic bridgeless planar graph being not hamiltonian.
$endgroup$
– Thomas Lesgourgues
Jan 24 at 9:14
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3066105%2f4-color-theorem-equivalent-to-cubic-planar-bridgeless-are-3-edge-colorable%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Suppose we want to 4-color the vertices of a planar graph.
We may assume it's simple, because loops are forbidden and multiple edges don't affect coloring.
We may assume it's a maximal planar graph (that is, a planar triangulation), because adding more edges to triangulate the graph only makes the problem harder.
All planar triangulations on at least 4 vertices are 3-connected.
Instead of coloring the vertices of this graph, we can color the faces of its dual. The dual is another planar graph. It is cubic (because we started with a triangulation) and it is 3-connected (because it's the dual of a simple planar 3-connected graph) so in particular it is bridgeless.
So we have reduced the problem to coloring the faces of a planar cubic bridgeless graph, which is the kind of graph that Tait's theorem applies to.
answered Jan 8 at 17:39
Misha LavrovMisha Lavrov
45.8k656107
$endgroup$
$begingroup$
I under the reduction to the dual problem. But how do you go from a 3-edge coloring to a 4 face coloring? The provided link explain how to do it, but does not give a proof that the coloring is valid.
$endgroup$
– Thomas Lesgourgues
Jan 8 at 19:39
$begingroup$
The coloring is valid because two adjacent faces are either separated by a cyan-or-orange edge (and are different in the first picture) or by a cyan-or-magenta edge (and are different in the second picture), so they're different in the overlay.
$endgroup$
– Misha Lavrov
Jan 8 at 20:35
$begingroup$
I had an issue visualising why every map obtained by deleting one colored edges are two faces colorables. The fact that the map is cubic is used here to deduce that the cycle are disjoints. I have everything written down. thanks.
$endgroup$
– Thomas Lesgourgues
Jan 8 at 20:51
$begingroup$
Another way to think about the construction is to think of the face colors as $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$ and to think of the edge colors as $(+0,+1)$, $(+1,+0)$, $(+1,+1)$. Make two adjacent faces differ by adding the edge color (mod 2). This is obviously a proper coloring, but it takes work to check that it's well-defined.
$endgroup$
– Misha Lavrov
Jan 8 at 20:54
add a comment |
$begingroup$
Suppose we want to 4-color the vertices of a planar graph.
We may assume it's simple, because loops are forbidden and multiple edges don't affect coloring.
We may assume it's a maximal planar graph (that is, a planar triangulation), because adding more edges to triangulate the graph only makes the problem harder.
All planar triangulations on at least 4 vertices are 3-connected.
Instead of coloring the vertices of this graph, we can color the faces of its dual. The dual is another planar graph. It is cubic (because we started with a triangulation) and it is 3-connected (because it's the dual of a simple planar 3-connected graph) so in particular it is bridgeless.
So we have reduced the problem to coloring the faces of a planar cubic bridgeless graph, which is the kind of graph that Tait's theorem applies to.
answered Jan 8 at 17:39
Misha LavrovMisha Lavrov
45.8k656107
$endgroup$
$begingroup$
I under the reduction to the dual problem. But how do you go from a 3-edge coloring to a 4 face coloring? The provided link explain how to do it, but does not give a proof that the coloring is valid.
$endgroup$
– Thomas Lesgourgues
Jan 8 at 19:39
$begingroup$
The coloring is valid because two adjacent faces are either separated by a cyan-or-orange edge (and are different in the first picture) or by a cyan-or-magenta edge (and are different in the second picture), so they're different in the overlay.
$endgroup$
– Misha Lavrov
Jan 8 at 20:35
$begingroup$
I had an issue visualising why every map obtained by deleting one colored edges are two faces colorables. The fact that the map is cubic is used here to deduce that the cycle are disjoints. I have everything written down. thanks.
$endgroup$
– Thomas Lesgourgues
Jan 8 at 20:51
$begingroup$
Another way to think about the construction is to think of the face colors as $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$ and to think of the edge colors as $(+0,+1)$, $(+1,+0)$, $(+1,+1)$. Make two adjacent faces differ by adding the edge color (mod 2). This is obviously a proper coloring, but it takes work to check that it's well-defined.
$endgroup$
– Misha Lavrov
Jan 8 at 20:54
add a comment |
$begingroup$
Suppose we want to 4-color the vertices of a planar graph.
We may assume it's simple, because loops are forbidden and multiple edges don't affect coloring.
We may assume it's a maximal planar graph (that is, a planar triangulation), because adding more edges to triangulate the graph only makes the problem harder.
All planar triangulations on at least 4 vertices are 3-connected.
Instead of coloring the vertices of this graph, we can color the faces of its dual. The dual is another planar graph. It is cubic (because we started with a triangulation) and it is 3-connected (because it's the dual of a simple planar 3-connected graph) so in particular it is bridgeless.
So we have reduced the problem to coloring the faces of a planar cubic bridgeless graph, which is the kind of graph that Tait's theorem applies to.
answered Jan 8 at 17:39
Misha LavrovMisha Lavrov
45.8k656107
$endgroup$
Suppose we want to 4-color the vertices of a planar graph.
We may assume it's simple, because loops are forbidden and multiple edges don't affect coloring.
We may assume it's a maximal planar graph (that is, a planar triangulation), because adding more edges to triangulate the graph only makes the problem harder.
All planar triangulations on at least 4 vertices are 3-connected.
Instead of coloring the vertices of this graph, we can color the faces of its dual. The dual is another planar graph. It is cubic (because we started with a triangulation) and it is 3-connected (because it's the dual of a simple planar 3-connected graph) so in particular it is bridgeless.
So we have reduced the problem to coloring the faces of a planar cubic bridgeless graph, which is the kind of graph that Tait's theorem applies to.
answered Jan 8 at 17:39
Misha LavrovMisha Lavrov
45.8k656107
answered Jan 8 at 17:39
Misha LavrovMisha Lavrov
45.8k656107
answered Jan 8 at 17:39
Misha LavrovMisha Lavrov
45.8k656107
answered Jan 8 at 17:39
Misha LavrovMisha Lavrov
45.8k656107
45.8k656107
$begingroup$
I under the reduction to the dual problem. But how do you go from a 3-edge coloring to a 4 face coloring? The provided link explain how to do it, but does not give a proof that the coloring is valid.
$endgroup$
– Thomas Lesgourgues
Jan 8 at 19:39
$begingroup$
The coloring is valid because two adjacent faces are either separated by a cyan-or-orange edge (and are different in the first picture) or by a cyan-or-magenta edge (and are different in the second picture), so they're different in the overlay.
$endgroup$
– Misha Lavrov
Jan 8 at 20:35
$begingroup$
I had an issue visualising why every map obtained by deleting one colored edges are two faces colorables. The fact that the map is cubic is used here to deduce that the cycle are disjoints. I have everything written down. thanks.
$endgroup$
– Thomas Lesgourgues
Jan 8 at 20:51
$begingroup$
Another way to think about the construction is to think of the face colors as $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$ and to think of the edge colors as $(+0,+1)$, $(+1,+0)$, $(+1,+1)$. Make two adjacent faces differ by adding the edge color (mod 2). This is obviously a proper coloring, but it takes work to check that it's well-defined.
$endgroup$
– Misha Lavrov
Jan 8 at 20:54
add a comment |
$begingroup$
I under the reduction to the dual problem. But how do you go from a 3-edge coloring to a 4 face coloring? The provided link explain how to do it, but does not give a proof that the coloring is valid.
$endgroup$
– Thomas Lesgourgues
Jan 8 at 19:39
$begingroup$
The coloring is valid because two adjacent faces are either separated by a cyan-or-orange edge (and are different in the first picture) or by a cyan-or-magenta edge (and are different in the second picture), so they're different in the overlay.
$endgroup$
– Misha Lavrov
Jan 8 at 20:35
$begingroup$
I had an issue visualising why every map obtained by deleting one colored edges are two faces colorables. The fact that the map is cubic is used here to deduce that the cycle are disjoints. I have everything written down. thanks.
$endgroup$
– Thomas Lesgourgues
Jan 8 at 20:51
$begingroup$
Another way to think about the construction is to think of the face colors as $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$ and to think of the edge colors as $(+0,+1)$, $(+1,+0)$, $(+1,+1)$. Make two adjacent faces differ by adding the edge color (mod 2). This is obviously a proper coloring, but it takes work to check that it's well-defined.
$endgroup$
– Misha Lavrov
Jan 8 at 20:54
$begingroup$
I under the reduction to the dual problem. But how do you go from a 3-edge coloring to a 4 face coloring? The provided link explain how to do it, but does not give a proof that the coloring is valid.
$endgroup$
– Thomas Lesgourgues
Jan 8 at 19:39
$begingroup$
I under the reduction to the dual problem. But how do you go from a 3-edge coloring to a 4 face coloring? The provided link explain how to do it, but does not give a proof that the coloring is valid.
$endgroup$
– Thomas Lesgourgues
Jan 8 at 19:39
$begingroup$
The coloring is valid because two adjacent faces are either separated by a cyan-or-orange edge (and are different in the first picture) or by a cyan-or-magenta edge (and are different in the second picture), so they're different in the overlay.
$endgroup$
– Misha Lavrov
Jan 8 at 20:35
$begingroup$
The coloring is valid because two adjacent faces are either separated by a cyan-or-orange edge (and are different in the first picture) or by a cyan-or-magenta edge (and are different in the second picture), so they're different in the overlay.
$endgroup$
– Misha Lavrov
Jan 8 at 20:35
$begingroup$
I had an issue visualising why every map obtained by deleting one colored edges are two faces colorables. The fact that the map is cubic is used here to deduce that the cycle are disjoints. I have everything written down. thanks.
$endgroup$
– Thomas Lesgourgues
Jan 8 at 20:51
$begingroup$
I had an issue visualising why every map obtained by deleting one colored edges are two faces colorables. The fact that the map is cubic is used here to deduce that the cycle are disjoints. I have everything written down. thanks.
$endgroup$
– Thomas Lesgourgues
Jan 8 at 20:51
$begingroup$
Another way to think about the construction is to think of the face colors as $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$ and to think of the edge colors as $(+0,+1)$, $(+1,+0)$, $(+1,+1)$. Make two adjacent faces differ by adding the edge color (mod 2). This is obviously a proper coloring, but it takes work to check that it's well-defined.
$endgroup$
– Misha Lavrov
Jan 8 at 20:54
$begingroup$
Another way to think about the construction is to think of the face colors as $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$ and to think of the edge colors as $(+0,+1)$, $(+1,+0)$, $(+1,+1)$. Make two adjacent faces differ by adding the edge color (mod 2). This is obviously a proper coloring, but it takes work to check that it's well-defined.
$endgroup$
– Misha Lavrov
Jan 8 at 20:54
add a comment |
$begingroup$
Why do you say that the explanation in the link does not prove the equivalence? You can decide to color the faces of the map OR you can color the edges of the same map. Once you have finished coloring one or the other (faces or the edges) you can switch to the other the way described in the link. The difficulty of three coloring the edges or four coloring the faces is the same. Since one has already been proved the other is proved too.
About the theorem of Tait, there is no theorem of Tait, at least not about four coloring.
The equivalency only states that for the same map (not any map) if you find one coloring (faces of edges) you can switch to the other coloring, it does not say that it is easier to find one or the other coloring. To go from one coloring to the other (related to the same map) the algorithm is described in the link. The algorithm is the proof of the equivalency.
UPDATE (25/Jan/2019): The proof should be here:
- P.G. Tait, ”On the colouring of maps”, Proceedings of the Royal Society
of Edinburgh Section A, 10: 501-503, 1878-1880.
- https://www.cambridge.org/core/journals/proceedings-of-the-royal-society-of-edinburgh/article/4-on-the-colouring-of-maps/6385395D337371EE9ED16C6AA6694AC0
answered Jan 24 at 2:34
Mario StefanuttiMario Stefanutti
604614
$endgroup$
$begingroup$
I'm not sure what you mean by "there is no theorem of Tait" when answering a question that quotes Tait's theorem. Do you mean that the equivalency was proven by someone else?
$endgroup$
– Misha Lavrov
Jan 24 at 3:52
$begingroup$
No, this is not only about the equivalence between 4-face coloring and 3 edge coloring. it is more powerfull. If you can 3-edge color any bridgeless, cubic planar graph, then you can 4-face color any planar graph. Indeed if $G$ is a planar graph, then you can consider its maximum graph $G'$, hence a triangulation, and looking at the dual $G^{'*}$, this graph is cubic (because $G'$ is a triangulation), planar (because $G'$) and bridgeless (because $G'$ is a triangulation). Then you can 3-edge this graph, and transfer this to a 4-face coloring of $G'$, hence of $G$.
$endgroup$
– Thomas Lesgourgues
Jan 24 at 8:56
$begingroup$
And this equivalence was prooven prior to the 4 color theorem. Tait wanted to use it in order to proove the 4 color theorem, assuming that any bridgeless cubic planar graph admits an Hamiltonian cycle (and therefore 3 edge colorable). This was disprove by the Petersen Graph, the first example of cubic bridgeless planar graph being not hamiltonian.
$endgroup$
– Thomas Lesgourgues
Jan 24 at 9:14
add a comment |
$begingroup$
Why do you say that the explanation in the link does not prove the equivalence? You can decide to color the faces of the map OR you can color the edges of the same map. Once you have finished coloring one or the other (faces or the edges) you can switch to the other the way described in the link. The difficulty of three coloring the edges or four coloring the faces is the same. Since one has already been proved the other is proved too.
About the theorem of Tait, there is no theorem of Tait, at least not about four coloring.
The equivalency only states that for the same map (not any map) if you find one coloring (faces of edges) you can switch to the other coloring, it does not say that it is easier to find one or the other coloring. To go from one coloring to the other (related to the same map) the algorithm is described in the link. The algorithm is the proof of the equivalency.
UPDATE (25/Jan/2019): The proof should be here:
- P.G. Tait, ”On the colouring of maps”, Proceedings of the Royal Society
of Edinburgh Section A, 10: 501-503, 1878-1880.
- https://www.cambridge.org/core/journals/proceedings-of-the-royal-society-of-edinburgh/article/4-on-the-colouring-of-maps/6385395D337371EE9ED16C6AA6694AC0
answered Jan 24 at 2:34
Mario StefanuttiMario Stefanutti
604614
$endgroup$
$begingroup$
I'm not sure what you mean by "there is no theorem of Tait" when answering a question that quotes Tait's theorem. Do you mean that the equivalency was proven by someone else?
$endgroup$
– Misha Lavrov
Jan 24 at 3:52
$begingroup$
No, this is not only about the equivalence between 4-face coloring and 3 edge coloring. it is more powerfull. If you can 3-edge color any bridgeless, cubic planar graph, then you can 4-face color any planar graph. Indeed if $G$ is a planar graph, then you can consider its maximum graph $G'$, hence a triangulation, and looking at the dual $G^{'*}$, this graph is cubic (because $G'$ is a triangulation), planar (because $G'$) and bridgeless (because $G'$ is a triangulation). Then you can 3-edge this graph, and transfer this to a 4-face coloring of $G'$, hence of $G$.
$endgroup$
– Thomas Lesgourgues
Jan 24 at 8:56
$begingroup$
And this equivalence was prooven prior to the 4 color theorem. Tait wanted to use it in order to proove the 4 color theorem, assuming that any bridgeless cubic planar graph admits an Hamiltonian cycle (and therefore 3 edge colorable). This was disprove by the Petersen Graph, the first example of cubic bridgeless planar graph being not hamiltonian.
$endgroup$
– Thomas Lesgourgues
Jan 24 at 9:14
add a comment |
$begingroup$
Why do you say that the explanation in the link does not prove the equivalence? You can decide to color the faces of the map OR you can color the edges of the same map. Once you have finished coloring one or the other (faces or the edges) you can switch to the other the way described in the link. The difficulty of three coloring the edges or four coloring the faces is the same. Since one has already been proved the other is proved too.
About the theorem of Tait, there is no theorem of Tait, at least not about four coloring.
The equivalency only states that for the same map (not any map) if you find one coloring (faces of edges) you can switch to the other coloring, it does not say that it is easier to find one or the other coloring. To go from one coloring to the other (related to the same map) the algorithm is described in the link. The algorithm is the proof of the equivalency.
UPDATE (25/Jan/2019): The proof should be here:
- P.G. Tait, ”On the colouring of maps”, Proceedings of the Royal Society
of Edinburgh Section A, 10: 501-503, 1878-1880.
- https://www.cambridge.org/core/journals/proceedings-of-the-royal-society-of-edinburgh/article/4-on-the-colouring-of-maps/6385395D337371EE9ED16C6AA6694AC0
answered Jan 24 at 2:34
Mario StefanuttiMario Stefanutti
604614
$endgroup$
Why do you say that the explanation in the link does not prove the equivalence? You can decide to color the faces of the map OR you can color the edges of the same map. Once you have finished coloring one or the other (faces or the edges) you can switch to the other the way described in the link. The difficulty of three coloring the edges or four coloring the faces is the same. Since one has already been proved the other is proved too.
About the theorem of Tait, there is no theorem of Tait, at least not about four coloring.
The equivalency only states that for the same map (not any map) if you find one coloring (faces of edges) you can switch to the other coloring, it does not say that it is easier to find one or the other coloring. To go from one coloring to the other (related to the same map) the algorithm is described in the link. The algorithm is the proof of the equivalency.
UPDATE (25/Jan/2019): The proof should be here:
- P.G. Tait, ”On the colouring of maps”, Proceedings of the Royal Society
of Edinburgh Section A, 10: 501-503, 1878-1880.
- https://www.cambridge.org/core/journals/proceedings-of-the-royal-society-of-edinburgh/article/4-on-the-colouring-of-maps/6385395D337371EE9ED16C6AA6694AC0
answered Jan 24 at 2:34
Mario StefanuttiMario Stefanutti
604614
edited Jan 25 at 8:21
answered Jan 24 at 2:34
Mario StefanuttiMario Stefanutti
604614
answered Jan 24 at 2:34
Mario StefanuttiMario Stefanutti
604614
answered Jan 24 at 2:34
Mario StefanuttiMario Stefanutti
604614
604614
$begingroup$
I'm not sure what you mean by "there is no theorem of Tait" when answering a question that quotes Tait's theorem. Do you mean that the equivalency was proven by someone else?
$endgroup$
– Misha Lavrov
Jan 24 at 3:52
$begingroup$
No, this is not only about the equivalence between 4-face coloring and 3 edge coloring. it is more powerfull. If you can 3-edge color any bridgeless, cubic planar graph, then you can 4-face color any planar graph. Indeed if $G$ is a planar graph, then you can consider its maximum graph $G'$, hence a triangulation, and looking at the dual $G^{'*}$, this graph is cubic (because $G'$ is a triangulation), planar (because $G'$) and bridgeless (because $G'$ is a triangulation). Then you can 3-edge this graph, and transfer this to a 4-face coloring of $G'$, hence of $G$.
$endgroup$
– Thomas Lesgourgues
Jan 24 at 8:56
$begingroup$
And this equivalence was prooven prior to the 4 color theorem. Tait wanted to use it in order to proove the 4 color theorem, assuming that any bridgeless cubic planar graph admits an Hamiltonian cycle (and therefore 3 edge colorable). This was disprove by the Petersen Graph, the first example of cubic bridgeless planar graph being not hamiltonian.
$endgroup$
– Thomas Lesgourgues
Jan 24 at 9:14
add a comment |
$begingroup$
I'm not sure what you mean by "there is no theorem of Tait" when answering a question that quotes Tait's theorem. Do you mean that the equivalency was proven by someone else?
$endgroup$
– Misha Lavrov
Jan 24 at 3:52
$begingroup$
No, this is not only about the equivalence between 4-face coloring and 3 edge coloring. it is more powerfull. If you can 3-edge color any bridgeless, cubic planar graph, then you can 4-face color any planar graph. Indeed if $G$ is a planar graph, then you can consider its maximum graph $G'$, hence a triangulation, and looking at the dual $G^{'*}$, this graph is cubic (because $G'$ is a triangulation), planar (because $G'$) and bridgeless (because $G'$ is a triangulation). Then you can 3-edge this graph, and transfer this to a 4-face coloring of $G'$, hence of $G$.
$endgroup$
– Thomas Lesgourgues
Jan 24 at 8:56
$begingroup$
And this equivalence was prooven prior to the 4 color theorem. Tait wanted to use it in order to proove the 4 color theorem, assuming that any bridgeless cubic planar graph admits an Hamiltonian cycle (and therefore 3 edge colorable). This was disprove by the Petersen Graph, the first example of cubic bridgeless planar graph being not hamiltonian.
$endgroup$
– Thomas Lesgourgues
Jan 24 at 9:14
$begingroup$
I'm not sure what you mean by "there is no theorem of Tait" when answering a question that quotes Tait's theorem. Do you mean that the equivalency was proven by someone else?
$endgroup$
– Misha Lavrov
Jan 24 at 3:52
$begingroup$
I'm not sure what you mean by "there is no theorem of Tait" when answering a question that quotes Tait's theorem. Do you mean that the equivalency was proven by someone else?
$endgroup$
– Misha Lavrov
Jan 24 at 3:52
$begingroup$
No, this is not only about the equivalence between 4-face coloring and 3 edge coloring. it is more powerfull. If you can 3-edge color any bridgeless, cubic planar graph, then you can 4-face color any planar graph. Indeed if $G$ is a planar graph, then you can consider its maximum graph $G'$, hence a triangulation, and looking at the dual $G^{'*}$, this graph is cubic (because $G'$ is a triangulation), planar (because $G'$) and bridgeless (because $G'$ is a triangulation). Then you can 3-edge this graph, and transfer this to a 4-face coloring of $G'$, hence of $G$.
$endgroup$
– Thomas Lesgourgues
Jan 24 at 8:56
$begingroup$
No, this is not only about the equivalence between 4-face coloring and 3 edge coloring. it is more powerfull. If you can 3-edge color any bridgeless, cubic planar graph, then you can 4-face color any planar graph. Indeed if $G$ is a planar graph, then you can consider its maximum graph $G'$, hence a triangulation, and looking at the dual $G^{'*}$, this graph is cubic (because $G'$ is a triangulation), planar (because $G'$) and bridgeless (because $G'$ is a triangulation). Then you can 3-edge this graph, and transfer this to a 4-face coloring of $G'$, hence of $G$.
$endgroup$
– Thomas Lesgourgues
Jan 24 at 8:56
$begingroup$
And this equivalence was prooven prior to the 4 color theorem. Tait wanted to use it in order to proove the 4 color theorem, assuming that any bridgeless cubic planar graph admits an Hamiltonian cycle (and therefore 3 edge colorable). This was disprove by the Petersen Graph, the first example of cubic bridgeless planar graph being not hamiltonian.
$endgroup$
– Thomas Lesgourgues
Jan 24 at 9:14
$begingroup$
And this equivalence was prooven prior to the 4 color theorem. Tait wanted to use it in order to proove the 4 color theorem, assuming that any bridgeless cubic planar graph admits an Hamiltonian cycle (and therefore 3 edge colorable). This was disprove by the Petersen Graph, the first example of cubic bridgeless planar graph being not hamiltonian.
$endgroup$
– Thomas Lesgourgues
Jan 24 at 9:14
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3066105%2f4-color-theorem-equivalent-to-cubic-planar-bridgeless-are-3-edge-colorable%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
