<p>Every planar graph can be colored by 4 color, take dual of graph, the faces of dual are able to be colored by 4 color because of 4 color theorem, but they are also vertices of original graph.</p>

CC BY-SA 3.0
2014-03-25T00:25:00.353Z
But we need computers to prove 4-color thm, right?
What I want is a human-doable proof to this weaker problem.
nuk
CC BY-SA 3.0
2014-03-25T01:01:30.643Z
@nuk, We don't need to invent a wheel, 4 color theorem is a famous theorem and we don't need to prove it. But if you looking for non computer proof, take a look at seymour etal proof, here you can find a brief overview by one of a authors (Robin Thomas): http://people.math.gatech.edu/~thomas/FC/fourcolor.html
Saeed
CC BY-SA 3.0
2015-07-19T07:36:38.827Z
As Tommy Jensen mentions below, even this second-generation proof of Robertson, Sanders, Seymour and Thomas uses computer verification, albeit a shorter a more trustworthy one. Recently Gonthier and his team came up with a completely formalized computer-aided proof, which should remove any doubts regarding the correctness of the previous proofs. Another computer-aided proof is due to John Steinberger: http://iiis.tsinghua.edu.cn/~john/4c.pdf.
Yuval Filmus
CC BY-SA 3.0
2014-03-24T23:22:13.913Z
2014-03-24T23:22:13.913Z
Saeed
<p>I can think of a way that to prove a 3-connected 5-regular planar graph does not contain a 5-critical subgraph.</p>

<p>We can choose two non-adjacent vertices a,b and contract them into a single vertex. If a and b has common neighbours, the resultant graph will still be a planar graph G'. But how can I prove chromatic number of G' is less or equal than 4?</p>

<p>Furthermore, how to prove that a 5-regular planar graph has chromatic number &lt;= 4?</p>

CC BY-SA 3.0
2014-03-25T03:36:54.350Z
This is not quite a research-level question.
Yuval Filmus
<graph-theory><planar-graphs>
How to prove that a 3-connected 5-regular planar graph has chromatic number <= 4?
nuk
# How to prove that a 3-connected 5-regular planar graph has chromatic number <= 4?

(Asked by: username_0 on 2014-03-24)

I can think of a way that to prove a 3-connected 5-regular planar graph does not contain a 5-critical subgraph.

We can choose two non-adjacent vertices a,b and contract them into a single vertex. If a and b has common neighbours, the resultant graph will still be a planar graph G'. But how can I prove chromatic number of G' is less or equal than 4?

Furthermore, how to prove that a 5-regular planar graph has chromatic number <= 4?

**Tags:** graph-theory, planar-graphs
> **Comments:**
> **username_1**: This is not quite a research-level question.  

---

## 1 answers

### Answer by username_2 on 2014-03-24. Score: 2

Every planar graph can be colored by 4 color, take dual of graph, the faces of dual are able to be colored by 4 color because of 4 color theorem, but they are also vertices of original graph.

> **Comments:**
> **username_0**: But we need computers to prove 4-color thm, right? What I want is a human-doable proof to this weaker problem.  
> **username_2**: @nuk, We don't need to invent a wheel, 4 color theorem is a famous theorem and we don't need to prove it. But if you looking for non computer proof, take a look at seymour etal proof, here you can find a brief overview by one of a authors (Robin Thomas): http://people.math.gatech.edu/~thomas/FC/fourcolor.html  
> **username_1**: As Tommy Jensen mentions below, even this second-generation proof of Robertson, Sanders, Seymour and Thomas uses computer verification, albeit a shorter a more trustworthy one. Recently Gonthier and his team came up with a completely formalized computer-aided proof, which should remove any doubts regarding the correctness of the previous proofs. Another computer-aided proof is due to John Steinberger: http://iiis.tsinghua.edu.cn/~john/4c.pdf.  

---

