結論から言えば、「与えられた連結な３正則グラフが辺３彩色可能、すなわち、次数３の頂点のみからなる連結なグラフが辺３彩色可能ならば、そのグラフにさら次数２の頂点を丁度２個付け加えた連結なグラフもまた辺３彩色可能である」事と、四色定理は同値である。
面４彩色の可否は、３正則グラフの辺３彩色の可否と同値である事は述べた。が、辺３彩色の可否を証明する事自体、それほど簡単でない事も過去に言及した通りである。
そこで、これまでに多くの数学者がしてきたように、数学的帰納法により、証明する事を考える。
まず、対象となる３正則グラフには必ず、２辺国、３辺国、４辺国、５辺国、のいずれかが含まれている。これは、多面体定理から、全ての面の頂点数の平均が、
6-24/(n+4)
と算出され、決して6以上の値をとらない事から直ちにわかる。ここでnはグラフの頂点数である。
例えば、頂点数をn=20とすると、面の平均角数は5となる。
今、ある面数のグラフまでは彩色可能である事がわかっているものとし、これより一つ面が多いグラフについて考える。
詳細は省くが、２辺国と３辺国を含むグラフが彩色可能である事はほとんど自明なので、割愛する。
４辺国の場合、多少の調整が必要な場合もあるが、４辺国を取り除いてから彩色を施し、再び４辺国を元通りに戻しても彩色可能となる事が容易にわかる。
したがって、問題はグラフで最少の頂点を持つ面が５辺国の場合だけ考えれば良い。
なお、頂点が２彩色可能な３正則グラフ、すなわち、任意のサイクルが偶数頂点のグラフは必ず３彩色可能である事が自明であるが、この場合、サイクルの次元が一つ減るため、このあとの行列計算の際に都合が悪いが、実は最少のサイクルが５辺国の場合には、この事は考慮する必要がない事をここで示しておく。
まず、グラフに含まれる奇数頂点のサイクルが５辺国一つのみだった場合、この５辺国と隣接する偶数頂点のサイクルを隔てる辺を取り除いて一つのサイクルとする。面が一つへり、やはり奇数頂点のサイクルが残る。
もし５辺国の他に奇数頂点のサイクルがある場合、その２つが隣接している場合は、隣接している偶数頂点のサイクルと一つのサイクルとすれば良く、５辺国のまわりに隣接する奇数頂点のサイクルが３つ以上あれば、必ずひとつは奇数頂点のサイクルが残る。
要は、５辺国を取り除く際には適切に辺を一つ取り除いて隣接するサイクルと併合すれば、面が一つ少なく、奇数頂点のサイクルを少なくとも一つ含むグラフになる。
ここで、位数３の体上の多変数多項式について考えておく。
面頂点行列は、頂点数分の変数からなる連立多項式の係数行列と考える事ができる。各行は対応する列の成分を係数とする変数の一次結合である。各変数は彩色の方向を表す２つの数値、1か2をとり（決して0はとらない）、その一次結合は0とならなければならない。
これを対角化すると、対角化されあなかった部分の変数の一次結合は対角化された部分の（１個の）変数との和が0という事なので、これら対角化されていなかった列を係数とする変数の一次結合で表される多項式と、全ての変数とを、全て掛け合わせたものが恒等的に0とならないという条件を満たせば、このサイクル頂点行列に対応するグラフは辺３彩色可能となり、逆も成り立つ。
ここで、変数の値が1または2のいずれかしかとらないため、変数と対応する列の係数の符号をまるごと入れ換えても題意を失わない事がわかる（体格された列の符号の交換は、対応する行をまるごと符号を変える事に対応する事に注意）。
今、グラフから辺を１つだけ取り除いたとする。取り除いた辺の両端の頂点も取り除いてできた３正鵠グラフは、面の数が１つ少ないため、これは辺３彩色できる。
辺を取り除いてできた面を外周として、サイクル頂点行列を作る。外周部分の辺の上に、次数２の頂点を配置すると、サイクル頂点行列では対応する列に零でない成分ただ１つだけ存在する事になる。取り除いた辺の両端の頂点に対応する次数２の頂点をこの要領で追加する。
すると、対角化する際、この頂点を含む行を残して対角化する事ができ、対角化されあずに残った部分は正方行列となる。
ここはまだ証明できていない（つまり、これが四色定理の本質）が、このようにしてできた正方行列は正則行列となる。
すると、この行列の逆行列を求めて、この正方行列の部分に対応する多項式が0にならないような解を求める事ができる。
したがって、３正則グラフに次数２の頂点を２個付け加えたグラフはやはり辺３彩色可能であると言える。
ここで、辺３彩色されたグラフは、そのうち２色を交互につないで行くと必ずサイクルとなる事が２色のサイクルが組み合わさっている事が、頂点辺行列の研究でわかっている。
すると、付け加えた次数２の頂点には同一の２色の組み合わせ以外はあり得ない事が容易にわかる（付け加えられた２頂点が、サイクルの切れ目の両端にならなければならないから）。つまり、残りの１色で、取り除いた辺を彩色すれば、もとのグラフは辺３彩色される。
故に、元のグラフもまた四色で塗りわけられる。
