Annales de l’institut Fourier (AIF)

Nešetřill, J.

Raspaud, André

Antisymmetric flows and strong colourings of oriented graphs

Kapoudjian, Christophe

Simplicity of Neretin's group of spheromorphisms

Cowling, Michael

Meda, Stefano

Pasquale, Roberta

Riesz potentials and amalgams

Neto, Alcides Lins

A note on projective Levi flats and minimal sets of algebraic foliations

Apostolov, Vestislav

Muškarov, Oleg

Weakly-Einstein hermitian surfaces

Pecker, Daniel

Sur la réalité des points doubles des courbes gauches

Tutte, William T.

ANNALES DE L’INSTITUT FOURIER
WILLIAM T. TUTTE
Bicubic planar maps
Annales de l’institut Fourier, tome 49, no 3 (1999), p. 1095-1102
<http://www.numdam.org/item?id=AIF_1999__49_3_1095_0>
© Annales de l’institut Fourier, 1999, tous droits réservés.
L’accès aux archives de la revue « Annales de l’institut Fourier »
(http://annalif.ujf-grenoble.fr/) implique l’accord avec les conditions gé-
nérales d’utilisation (http://www.numdam.org/conditions). Toute utilisa-
tion commerciale ou impression systématique est constitutive d’une in-
fraction pénale. Toute copie ou impression de ce fichier doit conte-
nir la présente mention de copyright.
Article numérisé dans le cadre du programme
Numérisation de documents anciens mathématiques
http://www.numdam.org/
Ann. Inst. Fourier, Grenoble
49, 3 (1999), 1095-1102
BICUBIC PLANAR MAPS (*)
by William T. TUTTE
Called to lecture at a conference that honours the memory of Francois
Jaeger I reflect that his interests in graph theory overlapped considerably
with my own. Thus I have been interested in nowhere-zero flows and
Francois proved the 8-flow conjecture for them. We have both worked on
edge-3-colourings of cubic graphs and he dealt with more general edge-
colourings too. I have considered a 2-variable polynomial for graphs and he
imported it into knot theory. We both had something to say about planar
bicubic maps. Perhaps it would be appropriate today to put our two sayings
together.
A cubic graph is a graph in which each vertex is trivalent. Such a graph
is "bicubic" if its vertex-set can be partitioned into two complementary
subsets U and V such that each edge has one end in each subset. It follows
that every circuit in a bicubic graph is of even length. A bicubic graph is
planar if it can be drawn in the plane (or on the sphere) with no crossing.
And when it is so drawn there results a "bicubic planar map".
Let M be a plane bicubic map and G its graph. If G is connected each
residual domain in the sphere is simply connected. But if G is disconnected
this rule no longer holds.
In the theory of cubic graphs it is often convenient to admit
"loose edges" that is edges incident with no vertex. A loose edge is
conveniently represented in a diagram by a simple closed curve. A loose
edge all by itself is said to constitute a cubic and even a bicubic graph. It is
referred to as a 0-circuit and as such said to have length zero. As part of a
bicubic graph it is exempted from the requirement of having one end in U
and one in V.
Keywords: Bicubic map - Polynomial - Alternating map.
Math. classification: 05 C.
1096 WILLIAM T. TUTTE
We can get a useful theorem about bicubic planar maps by applying
the Euler formula to each component of G not constituted by a single
loose edge. As with any cubic map in the sphere there has to be a face of
valency <, 5 in that component. But all circuits in a bicubic graph are even.
Hence:
THEOREM 1. — A planar bicubic map M has either a loose edge or a
face that is a 2-gon or a 4-gun.
Referring to a paper by Francois we find a list of operations whereby
simpler bicubic maps are derived from a given one [3]. They are the following
operations (i), (ii) and (hi):
(i) A loose edge is deleted from G, forming G' and M'.
(ii) An edge is deleted from a digon and the resultant 2-valent vertices
are suppressed, forming G' and M1'.
(iii) Two opposite edges of a 4-gon are deleted and the resulting 2-valent
vertices are suppressed. This can be done in two ways, forming M' and M"
(and G and G").
V4___B/
/ D C \
M' M'1
Figure 2
Frangois now looks for functions of planar bicubic maps having
recursion formulae simply related to his three operations. The first one he
presents is
T(G)=T(M),
the number of edge-3-colourings of G in three colours a, b and c. This
function is of course defined for all cubic graphs. And for planar cubic
BICUBIC PLANAR MAPS 1097
maps it is well known that T is non-zero if and only if the map is face-
4-colourable [5]. I once used the theory of these "Tait-colourings" in a
new proof of Smith's Theorem, that the number of Hamiltonian circuits
through any edge of a cubic graph, planar or non-planar, is even [6]. In
their improved form of the Four Colour Theorem [4] Robertson, Sanders,
Seymour and Thomas reformulate the problem in terms of Tail colourings.
For bicubic planar maps Francois points out that
• T(M) = 3T(M') for operation (i);
. T(M) == 2r(M') for operation (ii);
• T(M) = r(M') + T{M") for operation (hi).
If we conventionally put
T(M) = 3
when G consists of a single loose edge we can compute T for any M by
repeated use of these three recursions, without leaving the realm of planar
bicubic maps. Francois now goes on to discuss the flow polynomial F(G, X)
of G. I now quote from his paper:
"For positive integer values of A this polynomial counts the flows (in
an arbitrary orientation) of G with non-zero values in an arbitrary abelian
group of A elements. For instance, by considering edge-3-colourings as
flows with non-zero values in Zs x Zs we see that F(G,4) = T(G). For
our purposes we can be satisfied with the following definition: F(G, A) is
the chromatic polynomial of the dual of G divided by A."
Apparently Francois was unable to fit F(G,A) to his scheme for
every A but succeeded in doing so for the special case A = r + 1, where r
is the golden ratio ^(1 + \/5). There are some curious theorems about
chromatic polynomials that apply only to that value of A (see [8]). I have
worked on them myself and I was much gratified to find Francois using one
of them.
To cut the story short he showed
• for his operation (i),
F(G,T+1)=TF(G / ,T+1);
• furthermore for operation (ii),
F (G,T+l)=(r - l )F(G' ,T+l ) ;
1098 WILLIAM T. TUTTE
• and for operation (iii), with the help of one of these special theorems,
F(G, T + 1) = (-3r + 5){F(G', r + 1) + F(G^\ r + 1)}.
Again we have recursion formulae enabling us to calculate F(M, r 4-1)
form the conventional F(M, r + 1) = r of the single-loose-edge case.
The paper now invites us to consider these two map-functions as a
special case of a more general function U{M) that satisfies:
(o) U{0) = 1 for the loose-edge graph 0;
(i) U(G) = xU{G') with operation (i);
(ii) U(G) = yU(G') with operation (ii);
(iii) U(G) = z[U{ff) + ^(G")) with operation (iii).
Figure 3
However by evaluating U for the map shown in Figure 3 in two ways,
first by two applications of Rule (ii) and then by Rule (iii) it is found
that a U is possible only when
y2 ==z(x+l).
But the paper goes on to give a proof that whenever this restriction holds
a U exists. There we have a new invariant.
Having got so far into the paper I began to wonder where further
information about planar cubic maps could be found. I bethought me of a
paper by Brooks, Smith, Stone and Tutte [2] published in 1975 (see also [9]).
In this connection let me remind you of a theorem of P.J. Heawood, that
a connected bicubic planar map can be face-3-coloured in essentially only
one way. So let us take an M, this time with no loose edges, and 3-colour
the faces in red, blue and yellow (J?, B and V). Take the bipartition (?7, V)
calling U and V respectively positive and negative. We can do this so that
the cyclic sequence (RBY) goes anticlockwise around the positive vertices
(on the sphere) and clockwise around the negative ones.
1099BICUBIC PLANAR MAPS
Note that there is a way of constructing a plane directed graph DR
from M. We put one vertex of DR in each red face. Each edge of M that
goes from one red face to another is extended into each red face to end at
the corresponding vertices of DR. Thus we get the edges of Dp. We direct
each from the positive vertex of M on it to the negative.
M D,
Figure 4
Note that Dp in this plane drawing is "alternating"; incoming and
outgoing edges alternate at each vertex.
Likewise we have Dp and Dy-
Now the four authors of the 1975 paper had much to do with alter-
nating directed maps. Each such map, to them, represented a dissection
of an equilateral triangle into equilateral triangles. With such a dissection
there are three choices for which side of the dissected triangle is to be called
horizontal. The three choices give three alternating directed maps [7].
It seemed to us that this association of alternating directed maps in triads
was analogous of that of undirected maps in dual pairs.
It would be too long a digression to give a full theory relating an
alternating map to a dissected triangle. Very briefly, the head of one directed
edge is detached from its vertex. Then each directed edge is expanded as an
equilateral triangle, the arrow having its tail in the horizontal side and its
head at the opposite vertex. If the sizes of the triangles are made to satisfy
some evident equations a dissection of an equilateral triangle is obtained.
For a long time we lacked a description of just how three "trine"
alternating maps were related. And then Smith realized that they were the
Dp, DB and DY of some bicubic map.
1100 WILLIAM T. TUTTE
For each alternating directed map D we had been interested in the
number of spanning trees converging to a vertex v, that is having every
edge directed to v in the tree. There were also spanning trees diverging
from v, that is with every edge directed away from v. We had theorems
saying that the number of directed trees converging to v was equal to the
number diverging from it, that this number was independent of z?, and that
it was the same for each member of a triad. We called it the "diplexity"
of the alternating maps and of the triad. The triad being determined by a
bicubic map M, the diplexity could be seen as a function of bicubic planar
maps.
It was Smith who found a simple characterization of the diplexity in
terms of the structure of a bicubic planar map M. This is explained in the
BSST paper [2] as follows.
For each cubic map (whereof M is one) there is an integer n such
that the map has 3n edges, 2n vertices and n + 2 faces. Let us distinguish
one positive vertex v of M as the root-vertex and the three faces incident
with v as the root-faces, one of each colour. There are now n — 1 non-root
positive vertices and the same number of non-root faces.
A pairing of each non-root face with an incident non-root positive
vertex (if such is possible) is a "vertex-face matching" (with respect to the
root-vertex v). It is pointed out that if M is disconnected no such mapping
exists. For a component without v has too many faces. Theorem 9.1 of the
paper asserts that the number of vertex-face mappings with respect to v is
independent of the choice of v. Moreover it is unaltered by an interchange
of black and white vertices. So it is an invariant of M.
The paper then proceeds to the proof of the main theorem, the
equating of this invariant to the diplexity of each of the three associated
alternating directed maps.
The last section of the paper presents some recursion formulae for the
invariant — call it the match-number m{M) = m(G) of M. They can be
associated with Francois' operations (ii) and (iii). We can extend the list
by the following trivial rule for operation (i):
m(G)=0-m(G').
This is conventional but it fits the rule that m(G) = 0 when G is
disconnected. There is no harm now in writing
m(G) = 1
BICUBIC PLANAR MAPS 1101
for the loose-edge graph. (It does embarrass us when we try to calculate
m(G) for the null-graph.)
The rules from the BSST paper are:
• m(G) = m{G') for operation (ii);
• m(G) = m(Gf) 4- TT^G") for operation (iii).
So the match number is a special case of the Jaeger function U. It has
x=Q, 2 /=1 , z=l.
I am happy to pay contribute to Francois5 memory by drawing
attention to this slight extension of the theory of his paper.
A theory of dissected triangles was published in 1948. But the
existence of such a theory is briefly noted in an earlier paper of Brooks,
Smith, Stone and Tutte [1] published in 1940.
Nineteen forty! Some years before Francois was born. How that
emphasizes for me the shortness of his life and the tragic loss to Mathematics
imposed by his premature death.
BIBLIOGRAPHY
[1] R.L. BROOKS, C.A.B. SMITH, A.H. STONE and W.T. TUTTE, The dissection of
rectangles into squares, Duke Math. J., 7 (1940), 312-340.
[2] R.L. BROOKS, C.A.B. SMITH, A.H. STONE and W.T. TUTTE, Leaky electricity
and triangulated triangles, Philips Research Reports, 30 (1975), 205-219.
[3] P. JAEGER, A new invariant of plane bipartite cubic graphs, Discrete Maths., 101
(1992), 149-164.
[4] N. ROBERTSON, D. SANDERS, P. SEYMOUR and R. THOMAS, The four colour
Theorem, J. Comb. Theory B, 70 (1997), 2-44.
[5] P.G. TAIT, Note on a theorem in geometry of position, Trans. Royal Soc.
Edinburgh, 29 (1880), 657-660.
[6] W.T. TUTTE, On Hamiltonian Circuits, J. London Math. Soc., 21 (1946), 98-101.
[7] W.T. TUTTE, The dissection of equilateral triangles into equilateral triangles,
Proc. Cambbridge Phil. Soc., 44 (1948), 463-482.
1102 WILLIAM T. TUTTE
[8] W.T. TUTTE, On chromatic polynomials and the golden ratio, J. Comb. Theory,
9 (1970), 289-296.
[9] W.T. TUTTE, Graph theory as I have known it, Chapter 4, Oxford University
Press, 1998.
Wilham T. TUTTE,
151 Mandeston Road
Newmarket, Suffolk CB8 ONS (England).


Bicubic planar maps

Dloussky, Georges

Oeljeklaus, Karl

Vector fields and foliations on compact surfaces of class ${\rm VII}_0$

Raikov, Georgi D.

Eigenvalue asymptotics for the Pauli operator in strong nonconstant magnetic fields

Pitt, Nigel J. E.

On pairs of closed geodesics on hyperbolic surfaces

Not a member yet