LIE ALGEBRAS AND THE FOUR COLOR THEOREM
DROR BAR-NATAN
Appeared in Combinatorica 17-1 (1997) 43–52.

Abstract. We present a statement about Lie algebras that is equivalent to the Four Color
Theorem.

Contents
1. Introduction
1.1. Acknowledgement
2. Understanding Wsl(N )3. Understanding Wsl(2)References

1
3
3
5
7

1. Introduction
Let us start by recalling a well-known construction that associates to any finite dimensional metrized Lie algebra L a numerical-valued functional WL defined on the set of alloriented trivalent graphs G (that is, trivalent graphs in which every vertex is endowed witha cyclic ordering of the edges emanating from it). This construction underlies the gaugegroup dependence of gauge theories in general and of the Chern-Simons topological field
theory in particular (see e.g. [B-N1, AS1, AS2]) and plays a prominent role in the theory offinite type (Vassiliev) invariants of knots ([B-N2, B-N3, B-N4]) and most likely also in thetheory of finite type invariants of 3-manifolds ([O, GO, R]).
Fix a finite dimensional metrized Lie algebra L (that is, a finite dimensional Lie algebraLwith an ad-invariant symmetric non-degenerate bilinear form), choose some basis {La }dima=1
abof L, let tab = hLa , Lb i be the metric tensor, let t be the inverse matrix of tab , and let fabc
be the structure constants of L relative to {La }:fabc = hLa , [Lb , Lc ]i.
Let G be some oriented trivalent graph. To define WL , label all half-edges of G by symbols
from the list a, b, c, . . . , a1 , b1 , . . . , and sum over a, b, . . . , a1 , . . . ∈ {1, . . . , dim L} the productover the vertices of G of the structure constants “seen” around each vertex times the productover the edges of the t·· ’s seen on each edge. This definition is much better explained by an
example, as in figure 1.
Date: This edition: October 22, 1999; First edition: August 18, 1995.
This paper is available electronically at http://www.ma.huji.ac.il/∼drorbn
http://xxx.lanl.gov/abs/q-alg/9606016.
1

and

at

2

DROR BAR-NATAN

fb1 b2 b3
b3

b1

ta3 b2 (or tb2 a3 )a3
b2
fa1 a2 a3 (or ... )
a1
a2
bb
t 1
taa1
a
b

−→

c

tb3 c2tc3 a2

tcc1
c2

c1
fc1 c2 c3

c3

dim
XL

fabc fa1 a2 a3 fb1 b2 b3 fc1 c2 c3 taa1 tbb1 tcc1 tb3 c2 tc3 a2 ta3 b2

a,b,... ,c3 =1

fabc (or fbca or fcab )Figure 1. An example illustrating the construction of WL (G). Notice that when G is drawn
in the plane, we assume counterclockwise orientation for all vertices (unless noted otherwise),and that the cyclic symmetry fabc = fbca = fcab of the structure constants and the symmetrytab = tba of the inverse metric ensures that WL (G) is well defined.

By introducing an explicit change-of-basis matrix as in [B-N2] or by re-interpreting WL (G)in terms of abstract tensor calculus as in [B-N3], one can verify that WL (G) does not dependon the choice of the basis {La }. Typically one chooses a “nice” orthonormal (or almost
orthonormal) basis {La }, so that most of the constants tab and fabc vanish, thus greatly
reducing the number of summands in the definition of WL (G).
Unless otherwise stated, whenever dealing with a Lie algebra of matrices, we will take themetric to be the matrix trace in the defining representation: hLa , Lb i = tr(La Lb ).
Lemma-Definition 1.1. (proof in section 2) If a connected G has v vertices, then Wsl(N ) (G)top
is a polynomial in N of degree at most v2 + 2 in N . Thus we can set Wsl(N) (G) to be thev+2coefficient of N 2 in Wsl(N ) (G).
The following statement sounds rather reasonable; it just says that if G is “sl(2)-trivial”,
then it is at least “sl(N )-degenerate”. For us who grew up thinking that all that there is tolearn about sl(N ) is already in sl(2), this is not a big surprise:
topStatement 1. For a connected oriented trivalent graph G, Wsl(2) (G) = 0 implies Wsl(N) (G) =
0.

Lie-theoretically, there is much to say about sl(2) and sl(N ). There are representations ofsl(2) into sl(N ), there is an “almost decomposition” of sl(N ) into a product of sl(2)’s1 , andthere are many other similarities. A-priori, the above statement sounds within reach. The
purpose of this note is to explain why statement 1 is equivalent to the Four Color Theorem2 .
This equivalence follows from the following two propositions, proven in sections 2 and 3,
respectively:
Proposition 1.2. Let G be a connected oriented trivalent graph. If G is 2-connected,
top|Wsl(N) (G)| is equal to the number of embeddings of G in an oriented sphere. Otherwise,
top
Wsl(N ) (G) = 0.
1

See [B-NG] for a similar context in which the different sl(2)’s “decouple”.
The Four Color Theorem was conjectured by Francis Guthrie in 1852 and proven by K. I. Appel and
W. Haken [AH] in 1976. See also [SK].
2

LIE ALGEBRAS AND THE FOUR COLOR THEOREM

3

Proposition 1.3. (Penrose [P]. See also [Ka1, Ka2, KS].) If G is planar with v verticesv
and Gc is the map defined by its complement, then |Wsl(2) (G)| is 2 2 −2 times the total numberof colorings of Gc with four colors so that adjacent states are colored with different colors.
Indeed, statement 1 is clearly equivalent totop|Wsl(N) (G)| 6= 0⇒

|Wsl(2) (G)| 6= 0,

which by propositions 1.2 and 1.3 is the same as sayingµ¶G has a planar embedding⇒ (Gc has a 4-coloring ) .
with Gc a map
Notice that if G is connected, Gc is a map (does not have states that border themselves) iff
G is 2-connected.
Remark 1.4. We’ve chosen the formulation of statement 1 that we felt was the most appealing. With no change to the end result, one can replace sl(N ) = AN −1 by BN , CN , DN , orgl(N ) and sl(2) by so(3) in the formulation of statement 1. In fact, in the proofs we actuallywork with gl(N ) and so(3) rather than with sl(N ) and sl(2).
1.1. Acknowledgement. I wish to thank G. Brinkmann, D. Goldberg, J. Goldman, M.
Hutchings, L. Kauffman, D. P. Thurston and M. Wunderlich for many helpful conversations.
2. Understanding Wsl(N )As Lie algebras, gl(N ) is just sl(N ) plus an Abelian factor. As Abelian Lie algebras havevanishing structure constants, Wsl(N ) (G) = Wgl(N ) (G) for any oriented trivalent graph G.
So let us concentrate on computing Wgl(N ) (G) for such G. For the basis of gl(N ), we pick2N
the matrices {La }N
a=1 = {Lij }i,j=1 , where Lij is the matrix with 1 in the ij entry and 0
everywhere else. As the basis is indexed by a double index rather than by a single index, it
is convenient to label every half-edge of G by two symbols from the list i, j, . . . , i1 , . . . anddouble all the edges:
a

b

j

k

i

l

.

(1)

The metric tab = t(ij)(kl) of gl(N ) is given by t(ij)(kl) = tr Lij Lkl = δjk δil , and its inverse isgiven by the same formula:t(ij)(kl) = δjk δli .
This formula means that in the summation defining Wgl(N ) (G) we can assume the equalities
j = k and l = i along each edge as in (1). In other words, it is enough to label every doublededge with just one pair of indices, getting an overall picture like
u
k

t

j

l
q

p

i
m

n

−→
r s

N
X

f(ij)(kl)(mn) f(ji)(rs)(ut) f(lk)(tu)(qp) f(nm)(pq)(sr) ,i,j,... ,u=1

where f(ij)(kl)(mn) are the structure constants in our basis:
k

j

l

i
m

n

= f(ij)(kl)(mn) = hLij , [Lkl , Lmn ]i = tr(Lij Lkl Lmn ) − tr(Lmn Lkl Lij )4DROR BAR-NATANk= δjk δlm δni − δnk δli δjm =

j

l

k
i

m

n

−

j

l

i
m

.

(2)

n

In the last equation, indices connected by a line can be assumed to be equal in the summation
defining Wgl(N ) (G). Once the edges and vertices of G are “thickened” as in (1) and (2), thesummation over i, j, . . . becomes the counting of the number of solutions of the equalities
determined by the connected components of the thickened G. This number is simply N
raised to the number of connected components:
u
k

t

j
i

l
q

p

m

n

−→
r s

N
X

δil δlp · · ·i,j,... ,u=1½¾
i=l=p=m=j=t=k=n=r= # 1 ≤ i, j, . . . ≤ N := N 2.
u=q=s
Summarizing, we find the formula3
Wgl(N ) (G) =X

sign(M )N b(TM ) ,(3)markings M of G

where:• A markings M of G is a marking of each vertex of G by a sign in {+, −}, and sign(M )is the product of these signs.
• The thickening TM corresponding to a marking M is the oriented surface with boundary
obtained from G as follows:– Replace the vertices marked by a “+” with “joints” and the vertices marked by a“−” with “twisted joints” as in (2).
– Orient these surface pieces using the following black(b)/white(w) convention for the
thickening of vertices:

+

−
w

b

.

w

In other words, “+”-vertices are embedded in the thickening of G so that they
are seen as oriented counterclockwise from the white side of the thickening, while“-”-vertices are seen as oriented clockwise from the white side of the thickening.
– Finally, connect the joints together along the edges of G by bands, in the only way
consistent with the orientations of the joints.
• b(TM ) is the number of boundary components of TM .
If M is a marking of G, let SM be the closed oriented surface obtained by gluing a disk
into each boundary component of the thickening TM . With χ denoting Euler characteristic
and g denoting genus, we have2 − 2g(SM ) = χ(SM ) = χ(TM ) + b(TM ) = χ(G) + b(TM ).
3

Compare with [B-N3, equation (36)]; for similar formulas in the cases of so(N ) and sp(N ), see [B-N3,
equation (33)] and [B-N3, exercise 6.37].

LIE ALGEBRAS AND THE FOUR COLOR THEOREM

5Remembering that G is trivalent and thus χ(G) = − v2 , we getvb(TM ) = −χ(G) + 2 − 2g(SM ) = + 2 − 2g(SM ).
2
Thus b(TM ) is maximal when g(SM ) = 0 and in that case b(TM ) = v2 + 2. With (3), thisproves lemma 1.1. Furthermore, calling a marking M spherical when SM is a sphere, we get
the formula
X
top
top
Wsl(N
(G)
=
W
(G)
=
sign(M ).
)gl(N )
spherical markings M of G

Proof of proposition 1.2. Let G be 2-connected, and consider the mapΘ : {spherical markings M of G} −→ {embeddings of G in an oriented sphere}
defined by mapping M to the natural embedding of G in SM . It is clear that Θ is a bijection.
Indeed, if an embedding of G in an oriented sphere S 2 is given, one can reconstruct M bymarking the vertices that are oriented counterclockwise within SM (as seen from the whiteside of SM ) by a “+” sign, and marking all other vertices by a “−”.
To conclude the proof, it is enough to show that for spherical markings, sign(M ) is independent of the marking. Clearly, sign(M ) is also equal to (−1)v− , where v− is the number ofvertices of G that are embedded clockwise in SM by Θ(M ) (with SM viewed from its whiteside). By a theorem of H. Whitney [W1, W2]4 , one can get from any spherical embeddingof a trivalent 2-connected graph G to any other such embedding by a sequence of flips asin figure 2. Such flips do not change the parity of v− , since the number of vertices that is
flipped is even.

rest of the graphrest of the graph

Figure 2. A flip takes a part of a graph that connects to the rest via only two edges, andflips it over.

3. Understanding Wsl(2)Proposition 1.3 is due to Penrose [P] (see also [Ka1, Ka2, KS]). For completeness, we
reproduce its proof in this section.
As Lie algebras, sl(2) is isomorphic to so(3), so let us work with so(3) instead. The
standard basis of so(3) is given by the matrices






0 0
0
0 0 1
0 −1 00 0 .
L1 =  0 0 −1  , L2 =  0 0 0  and L3 =  1
0 1
0−1 0 00
0 0
4

Check [L, corollary 6] for a version closer to what we need, and remember that our graph is 2-connected
and hence some of the moves in [L] are irrelevant for us.

6

DROR BAR-NATAN

Let us pick the scalar product h·, ·i on so(3) to be the one that makes this basis orthonormal,
and let us denote the corresponding functional on graphs by Wso(3)] , with the “ e ” on top of
the so(3) to remind us that we are not using the standard matrix-trace scalar product.
One can easily verify that 12 h·, ·i is the scalar product induced on so(3) from matrix-trace
in sl(2). Thus, remembering that in the construction of WL vertices scale with the scalar
product and edges scale with its inverse, we find thatµ ¶v−ev
12
Wsl(2) (G) =Wso(3)(4)] (G) = 2 Wso(3)] (G),
2
where G is an oriented trivalent graph with v vertices and e edges. Let us fix such a G once
and for all, and let us assume that it is planar and that all the vertices of G are oriented
counterclockwise in the plane. Flipping the orientation of any given vertex just reverses thesign of Wso(3)] (G), and so the latter assumption does not limit the generality of our arguments.
Proof of proposition 1.3. With (4) in mind, proposition 1.3 clearly follows from the following
two lemmas.
Lemma 3.1. (Penrose [P]. See also [Ka1, Ka2, KS].) For a planar G as above, |Wso(3)] (G)|
is the number of colorings of the edges of G with three colors {1, 2, 3}, so that the edges
emanating from any single vertex are of different colors.
Lemma 3.2. (Tait’s theorem [T]) Edge-3-colorings as in the previous lemma are in a bijective correspondence with 4-colorings of the map Gc that fix the color of the “state at infinity”.
Proof of lemma 3.1. In the basis {La }, the structure constants of so(3) are given by(sign(abc) if abc is a permutation,fabc = ²abc =0otherwise.
Remembering also that {La } is orthonormal by choice, the computation of Wso(3)] (G) is given(on a simple example) by:
f
a

3
X

b

−→
d

c

e

²abc ²aef ²bf d ²cde .

a,b,c,d,e,f =1

The ² symbols force the indices coming into each vertex to be different, and hence clearlyX
Y
Wso(3)(G)=(a sign per vertex) ,(5)]edge-3-colorings of G

where the sign at each vertex is the sign of the permutation of {1, 2, 3} induced by anedge-3-coloring, as read counterclockwise around the vertex.
The only thing left to show is that the product of signs in (5) is independent of the edge3-coloring. A clever way to do that, discovered by L. H. Kauffman, is to replace every edge
colored by a “3” by a pair of edges colored “1” and “2” (in symbols, 1 + 2 = 3). This defines
two families of circles in the plane, labeled by “1” and by “2” (see figure 3). By lumping

LIE ALGEBRAS AND THE FOUR COLOR THEOREM

7

together the signs on each end of a “3” edge and taking the product over all of those edges,
one sees that the overall sign depends only on the parity of the number of “3” edges (alwayse), and the Z/2Z intersection number of the “1” family of circles with the “2” family of3
circles. By the Jordan curve theorem, the latter is always 0.
2
3
1

2
1

1

3

1

2
2

1

2
1

2

Figure 3. The two families of circles obtained by splitting every “3” edge.

Proof of lemma 3.2. This is a well known result (see e.g. [BM, theorem 9.12]), so let us only
sketch the proof. Consider the group H = Z/2Z × Z/2Z. Given any 4-coloring of Gc by
elements of H, one may associate to it an edge-3-coloring of G by the non-zero elements of
H, by coloring every edge by the difference of the colors in the two faces adjacent to it. One
then verifies that this edge 3-coloring is well defined and that we get a bijection between theset of 4-colorings of Gc that color the state at infinity with 0 and the set of edge-3-coloringof G.
References[AH]

K. I. Appel and W. Haken, Every planar map is four colorable, Contemp. Math. 98, Amer. Math.
Soc., Providence 1989.
[AS1] S. Axelrod and I.M. Singer, Chern-Simons perturbation theory, Proc. XXth DGM Conference (NewYork, 1991) (S. Catto and A. Rocha, eds.), World Scientific, 1992, 3–45.
[AS2], Chern-Simons perturbation theory II, Jour. Diff. Geom., 39 (1994) 173–213.
[B-N1] D. Bar-Natan, Perturbative aspects of the Chern-Simons topological quantum field theory, Ph.D.
thesis, Princeton Univ., June 1991, Dep. of Mathematics.
[B-N2], Weights of Feynman diagrams and the Vassiliev knot invariants, February 1991, preprint.
[B-N3], On the Vassiliev knot invariants, Topology 34 (1995) 423–472.
[B-N4], Bibliography of Vassiliev Invariants, http://www.ma.huji.ac.il/~drorbn.
[B-NG]and S. Garoufalidis, On the Melvin-Morton-Rozansky Conjecture, Invent. Math. 125 (1996)
103–133.
[BM] J. A. Bondy and U. S. R. Murty, Graph theory with applications, Elsevier, New-York 1976.
[GO]
S. Garoufalidis and T. Ohtsuki, On finite type 3-manifold invariants III: manifold weight systems,
MIT and Tokyo Inst. of Tech. preprint, August 1995.
[Ka1] L. H. Kauffman, Map coloring and the vector cross-product, J. Comb. Theo. B 48 (1990) 145–154.
, Map coloring, q-deformed spin networks and Turaev-Viro invariants for 3-manifolds, Int.
[Ka2]
J. of Mod. Phys. B 6 (1992) 1765–1794.
and H. Saleur, An algebraic approach to the planar coloring problem, Commun. Math. Phys.
[KS]
152 (1993) 565–590.
[L]
A. S. Lipson, Link signature, Goeritz matrices, and polynomial invariants, L’Enseignement Math.
36 (1990) 93–114.
[O]
T. Ohtsuki, Finite type invariants of integral homology 3-spheres, Jour. of Knot Theory and its
Ramifications 5(1) (1996) 101–115.
[P]
R. Penrose, Applications of negative dimensional tensors, Combinatorial mathematics and its applications (D. J. A. Welsh, ed.), Academic Press, San-Diego 1971, 221–244.

8DROR BAR-NATAN

[R]
[SK]
[T]
[W1]
[W2]

L. Rozansky, The trivial connection contribution to Witten’s invariant and finite type invariants ofrational homology spheres, q-alg/9503011 preprint, March 1995.
T. L. Saaty and P. C. Kainen, The four color problem, assaults and conquest, McGraw-Hill, NewYork 1977.
P. G. Tait, Remarks on colourings of maps, Proc. Royal Soc. Edinburgh Ser. A., 10 (1880) 729.
H. Whitney, A set of topological invariants for graphs, Amer. J. Math. 55 (1933) 231–235.
, On the classification of graphs, Amer. J. Math. 55 (1933) 236-244.

Institute of Mathematics, Århus University, 8000 Århus C, Denmark
Current address: Institute of Mathematics, The Hebrew University, Giv’at-Ram, Jerusalem 91904, Israel
E-mail address: drorbn@math.huji.ac.il