B ULLETIN DE LA S. M. F.

ROLAND BACHER
P IERRE DE L A H ARPE
TATIANA NAGNIBEDA
The lattice of integral flows and the lattice of
integral cuts on a finite graph
Bulletin de la S. M. F., tome 125, no 2 (1997), p. 167-198
<[Link]

© Bulletin de la S. M. F., 1997, tous droits réservés.

L’accès aux archives de la revue « Bulletin de la S. M. F. » (http:
//[Link]/Publications/Bulletin/[Link]) implique l’accord
avec les conditions générales d’utilisation ([Link]
conditions). Toute utilisation commerciale ou impression systématique
est constitutive d’une infraction pénale. Toute copie ou impression de
ce fichier doit contenir la présente mention de copyright.

Article numérisé dans le cadre du programme

Numérisation de documents anciens mathématiques
[Link]
Bull. Soc. math. France,
125, 1997, p. 167-198.

THE LATTICE OF INTEGRAL FLOWS AND THE

LATTICE OF INTEGRAL CUTS ON A
FINITE GRAPH
BY

ROLAND BACHER, PlERRE DE LA HARPE

and TATIANA NAGNIBEDA (*)

ABSTRACT. — The set of integral flows on a finite graph F is naturally an integral

lattice A^F) in the Euclidean space Ker(Ai) of harmonic real-valued functions on
the edge set of F. Various properties of F (bipartite character, girth, complexity,
separability) are shown to correspond to properties of A^F) (parity, minimal norm,
determinant, decomposability). The dual lattice of A^F) is identified to the integral
cohomology .^(r.Z) in Ker(Ai). Analogous characterizations are shown to hold for
the lattice of integral cuts and appropriate properties of the graph (Eulerian character,
edge connectivity, complexity, separability).
These lattices have a determinant group which plays for graphs the same role as
Jacobians for closed Riemann surfaces. It is then harmonic functions on a graph (with
values in an abelian group) which take place of holomorphic mappings.
RESUME.—Les flots entiers sur un graphe fini F constituent naturellement un reseau
entier A^F) dans Pespace euclidien Ker(Ai) des fonctions harmoniques a valeurs reelles
sur Pensemble des aretes de F. On montre Inequivalence de diverses proprietes de F
(caractere biparti, tour de taille, complexite, separabilite) avec des proprietes conve-
nables de A^F) (parite, norme minimale, determinant, decomposabilite). Le reseau
dual de A^F) est identifie a la cohomologie entiere .^(r^Z), plongee dans Ker(Ai).

(*) Texte recu le 5 avril 1996, accepte le 18 janvier 1997.

R. BACHER, Universite de Grenoble 1, Institut Fourier, Laboratoire de Mathematiques
associe au CNRS, B.P. 74, 38402 Saint-Martin-d'Heres CEDEX (France).
Email: bacher@[Link]
P. DE la HARPE, T. NAGNIBEDA, Section de Mathematiques, Universite de Geneve,
C.P. 240, CH-1211 Geneve 24 (Suisse).
Email: [Link]@[Link] et [Link]@[Link].
The first author has been partially supported by the Fonds National Suisse de la
Recherche Scientifique.
Keywords: Graph, lattice, combinatorial Laplacian, integral flows, cutsets, Jacobian.
AMS classification: 05C38, HE 39.

BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE 0037-9484/1997/167/$ 5.00

© Societe mathematique de France
168 R. BACHER, P. DE LA HARPE AND T. NAGNIBEDA

On montre des traductions analogues pour Ie reseau des coupures entieres et les
proprietes convenables du graphe (caractere eulerien, connectivite d'aretes, complexite,
separabilite).
Ces reseaux ont un groupe determinant qui joue pour les graphes Ie meme role que la
jacobienne pour une surface de Riemann close. Ce sont alors les fonctions harmoniques
sur un graphe (a valeurs dans un groupe abelien) qui tiennent lieu d'applications
holomorphes.

1. Introduction: The lattices A^F) and 7V1 (F)

Several classical results relate geometrical properties of a finite graph
to properties of various matrices or polynomials attached to the graph.
For this algebraic graph theory , see among others [Bil], [BCN], [CDS].
The purpose of this paper is to show that lattices and quadratic forms
fit most naturally in this theory. From another point of view, our aim is
to show how finite graphs provide numerous examples of positive definite
integral lattices.
More precisely, consider a finite graph F with vertex set V and
with edge set E (loops and multiple edges are allowed). Following Serre
(see [Ser, §2, n° 1]) we introduce the set E of oriented edges of F (the
cardinality of E is twice that of E) and we denote by e C E the inverse
of an oriented edge e € E. The vertex space C°(T, M) of all real functions
on V and the edge space C^F.K) of all functions g:E -^ R such that
g(e) = —g{e) for all e e E are Euclidean spaces for inner products
defined by

</i,/2) = ^fi{v)f2^ (gi^g2) = \ ^9i(e)g^e)

v^V eeE

for all /i,/2 C C'°(r,]R) and g^g^ € G^r.R). One defines an "exterior
differential"
d:c°(r,R) —^(r.R)
by
(d/)(e)=/(e+)-/(e_)

where e+ and e- denote respectively the head and the tail of an oriented
edge e. The adjoint operator
d^.C^F.R) —>C°(T,R)

is given by
(d*g)(v)=^g{e)
e€E
e+=v

and can be viewed as the usual incidence matrix of F.

TOME 125 — 1997 — ? 2

 LATTICES DEFINED BY FINITE GRAPHS 169

The corresponding Laplacians

Ao=d*d:C'°(r,]R) —>C'°(r,]R),

Ai = dd*: C1 (r, R) —> C1 (F, K)

are given by the familiar formulas

(Ao/)(v) = deg(z;)/(i;) - ^ f{w)

weV
w^v

(where the sum means more precisely ^g^ e =v /(e-)) an<^

(Aip)(e) = 2ff(e) - ^ ff(e0 - ^ ^O.

e'GE e^GE
<=e- e//=e+

One has orthogonal decompositions

C°(r,]R) = Ker(Ao) ©Im(d*),

C'^r,^) = Ker(Ai) elm(d).

(Short proof for the first equality: if x is an element of Ker(Ao) then
(Aox.x} = {[Link]) = 0 and x e Ker(d); thus Ker(Ao) = Ker(d); the
equality follows because Ker(c?) is the orthogonal complement of Im(d*)
inC'°(r,R).)
The kernel Ker(Ao) is the set of functions V —> M which are constant
on the connected components of the graph; the space Ker(Ai) is often
called the cycle subspace and Im(d) the cut subspace of r (see e.g.
[Bil, Chap. 4]). We rather think of Ker(Ao) and Ker(Ai) as spaces of
harmonic functions and harmonic one-forms on F ("forms" in the sense
of differential forms on manifolds).
Integral valued functions on E provide a lattice (^(I^Z) C C^r,]^)
which is isomorphic to the trivial lattice V C V (where m = \E\ = \ |E|).
By intersection with the two factors of the orthogonal decomposition
of (^(r,]^), one obtains the lattice of integral flows
A^F) = C^Z) nKer(Ai) C Ker(Ai)
and the lattice of integral cuts
N^T) = C^Z) nlm(d) C Im(d).
These are the fundamental objects of our interest in this work. They are
clearly integral lattices as (A, A) € Z for all A e A^F) (resp. A € A^^))-

BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE

170 R. BACHER, P. DE LA HARPE AND T. NAGNIBEDA

One may of course define similarly two lattices A°(r) C Ker(Ao) and
M°(r) C Im(d*). But these are of little interest. If r is connected and
has n vertices, it is easy to check that A°(r) is the infinite cyclic group
generated by the constant function of value 1, so that A°(r) C Ker(Ao)
is isomorphic to y^Z C K, and that M°(r) is the lattice of integral
valued functions in the space Im(d*) of functions f:V —> R such that
Z^ey/C^) = ° (the root lattice of type An-i). In general, A°(r)
and M°(r) are direct sums of factors corresponding to the connected
components of F.
Let us recall some terminology on lattices. Consider a Euclidean
space 7^; the inner product of two vectors x ^ y € H is denoted by ( x ^ y ) .
A lattice in H is a discrete subgroup A of H such that the quotient H / A is
compact. If A is a lattice in 7Y, its determinant det(A) is the square of the
volume of a fundamental domain for the action of A on H by translations,
and its minimal norm is the number
min(A) = min {(A, A) | A C A, A ^ 0}.
The dual lattice is
A^ = [x C H | {x, A) e Z for all A € A}
(it is also called the "polar lattice"). A lattice A is decomposable if there
exists a non trivial orthogonal decomposition H = Hz © H^ such that
A = (A D T^i) © ( A n ^2)5 and indecomposable otherwise.
A lattice A is integral if (A,^) € Z for all A./z C A, or equivalently
if A C A^. An integral lattice A is even if (A, A) € 2Z for all A € A.
The determinant group of an integral lattice A is the group A^/A; it is
a finite group of order det(A). (Another term for "determinant group"
is quotient group.) It comes with a non-degenerate Q/Z-valued bilinear
form
6A:AVAxAVA—^Q/Z
defined by b^(x,y) = (A,/^) mod Z where A,/^ e A^ are respectively
representants of x, y € A^/A. The finite inner product module (A^/A,^)
is called the discriminant form of the lattice A. In particular one may
attach to any lattice A the Witt class w(A) of its discriminant form, which
is an element of the Witt group TV(Q/Z); for the Witt group TV(Q/Z)
see e.g. §5.1 in [Sch].
There are open problems formulated at the ends of Sections 2, 3 and 9.
It is a pleasure to acknowledge several useful conversations with
Marc Burger, Shalom Eliahou, Francois Jaeger, Michel Kervaire, Edouard
Lebeau and Boris Venkov. We are also grateful to Norman Biggs for his
interest in our work [Bi3], [Bi4].

TOME 125 — 1997 — ? 2

 LATTICES DEFINED BY FINITE GRAPHS 171

2. Some properties ofA^r) and JV^r)

Let F be a graph. If F is not connected, both A^F) and 7V1 (F) are
orthogonal sums of the contributions of the connected components of r.
We assume from now on that F is connected.
If r is a tree, then Ker(Ai) = {0} and the lattice A^F) is trivial;
observe that 7V1 (T) c (^(r.M) is isometric to Z771 c R^ where m is the
number of edges of r. Dually, if F is a wedge of loops, then Im(d) = {0}
and the lattice 7V1 (r) is trivial; observe that A^F) C 07^,11) is again
isometric to V C V where m is the number of loops of F. Whenever
appropriate, the reader may assume from now on that the graphs which
appear below are neither trees nor wedges of loops.
Let us recall some terminology on graphs (see e.g. [VLW]).
An oriented circuit in a graph r is an oriented simple closed curve.
Each oriented circuit c in F determines a cochain gc: E —> Z defined by
^c(e) = 1 (resp. gc(e) = —1) if the oriented edge e appears in c (resp. if e
appears in c) and gc(e) = 0 otherwise; this gc is clearly in A^F).
The girth of r is the smallest length of a circuit in F.
An oriented cut a in F is a non empty subset of E of the following form:
there is a partition V = V^ U V? of the vertex set V in two non empty
subsets, and a is the set of edges with heads in V^ and tails in V^. To
each such a corresponds a cochain ga: E —^ Z defined by ga(e) = 1 (resp.
9a(e) = —1) if the oriented edge e appears in a (resp. if e appears in a)
and ga(e) = 0 otherwise. Denoting by \a ^ C°(r,Z) the characteristic
function of V^, one has ga = d(\a) € 7V1 (F).
If moreover the subgraphs induced by V^ and K? in F are connected,
we say that a is an oriented bond .
The edge connectivity of r is the minimal number of edges in a bond
(or in a cut) of F (see [Bol, Chap. 1]).
The complexity of a connected graph is the number of its spanning
trees.
The following results are proved in Section 4 below.
PROPOSITION 1. — Let r be a connected graph.
(i) The lattice A^F) is even if and only if the graph F is bipartite.
(ii) The minimal norm o/A^F) is equal to the girth ofF.
(hi) The determinant of A^F) is equal to the complexity ofF.

PROPOSITION 2. — Let r be a connected graph.

(i) The lattice N1 (F) is even if and only if the graph F is Eulerian
(namely if and only if all vertices in F are of even degrees).
(ii) The minimal norm o/A^^F) is equal to the edge connectivity ofY.

BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE

172 R. BACHER, P. DE LA HARPE AND T. NAGNIBEDA

(in) The determinant o/TV^F) is equal to the complexity ofT.

About Part (iii) of Proposition 1, it is classical that the complexity ^(F)
of r is equal to
^ydet'(Ao),

where del/ indicates the product of the non zero eigenvalues (see Cor. 6.5
in [Bil]). One has also

K^-de^Ai)

because d*d and dd* have the same non zero eigenvalues (see e.g.
[Dix, App. B 26]). But Part (iii) says slightly more, namely that this num-
ber ^(F) is the order of the finite abelian group (A^F^/A^F) attached
to the graph F (more on this group in Section 3 below). Thus /^(F) has
two natural factorizations. One has firstly

K(T) = - 02 • • • On
n

where 0:2 < • • • < a.n are the non zero eigenvalues of Ao == d*d (or
equivalently of Ai = dd*). The group (A1 (T))^ / A1 (T) is canonically
isomorphic to a direct product of cyclic groups of orders n\,..., np, where
rij divides n^+i for all .7 in { 1 , . . . , p — l } (the n/s are the invariant factors
of the finite abelian group). It follows that one has secondly

/t(r) = ni - - ' r i p .
This factorization is the "canonical factorization" of Berman [Ber], and
examples show that it may be quite distinct from the previous factoriza-
tion (see Section 9 below). Part (iii) of Proposition 1 appears in a different
setting as Theorem 3 of [Bi2].
As for any CW-complex (see Remark 4 of Section 9), the first integral
cohomology group ^(I^Z) is torsion free, for example because of the
canonical isomorphism ^(I^Z) w Hom(7Ti(r),Z). As for any compact
CW-complex, there exists a natural embedding ^(I^Z) ^-> ^([Link])
with cocompact image; this follows for example from the universal coeffi-
cient theorem for cohomology. (See e.g. Thm. 12.15 in [Rot]; for graphs,
there are of course elementary ad hoc arguments.) For graphs, from the
decomposition
C^r.I^Ke^A^eIm^),

TOME 125 — 1997 — ? 2

 LATTICES DEFINED BY FINITE GRAPHS 173

one may identify the real cohomology group ^(r.R) with the Euclidean
space Ker(Ai) of harmonic 1-forms, so that ^(F, Z) is naturally a lattice
in^r.R^Ke^Ai).
Recall from the end of Section 1 that any lattice A has a Witt class
w(A) in the group TV(Q/Z).
PROPOSITION 3. — Let T be a connected graph.
(i) The lattices A1 (F) and N1 (T) have isomorphic determinant groups.
(ii) One has w{Kl{T)) + w(Nl(^)) = 0.
(iii) In the space Ker(Ai), the lattices A^F) and ^(F.Z) are dual to
each other.

We do not know any interesting statement for N1 (F) corresponding to

Claim (iii) for A^F).
A cut-vertex in a connected graph F is a vertex v such that the
graph obtained from r by deleting v and its incident edges has several
connected components. A connected graph without cut-vertex is said to
be nonseparable (another term for "nonseparable" is 2-connected). The
blocks of a connected graph are its maximal nonseparable connected
subgraphs. For example, the blocks of a tree with more than one vertex are
graphs with two vertices connected by one edge. If a connected graph F is
separable, both A^F) and 7V1 (F) are orthogonal sums of the contributions
of the blocks of r. More generally, one has
PROPOSITION 4. — Let r be a connected graph which has no loop and
no vertex of degree one. The following are equivalent.
(i) The graph F is nonseparable,
(ii) the lattice A1 (r) is indecomposable,
(iii) the lattice N1 (r) is indecomposable,
(iv) the polygon matroid of F is connected.

(For connectedness ofmatroids, see e.g. Chap. 4 in [0x1].) About (iv),

one should distinguish carefully the polygon matroid M(T) and the lattice
A^F) of a graph r. Indeed, elements of M(T) are given as subsets of
the set E of all edges, while the structure of A^F) is defined without
its actual embedding in the space C^F.Z) of all cochains. For example,
if Fi, FS are two trees with unequal numbers of edges, .M(Fi), M.(T'z) are
not isomorphic, but A^Fi) ^ A^I^) ^ {0}.
Let r be a connected nonseparable graph. Suppose that F is obtained
from the disjoint graphs Fi, I^ by identifying the vertices HI of Fi and u^
of F2 as the vertex u of F and the vertices v^ of Fi and v^ of I^
as the vertex v of r. Then r' is a twisting of F about {u, v} if it is

BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE

174 R. BACHER, P. DE LA HARPE AND T. NAGNIBEDA

obtained from Fi and I^ by identifying u\ with v^ and v\ with u^. Two

connected nonseparable graphs are said to be 2-isomorphic if they can
be transformed into isomorphic graphs by a sequence of twistings. Notice
that 3-connected 2-isomorphic graphs are isomorphic.
As the graphic matroids (see [0x1, p. 148]), the lattices A^F) and
7V1 (r) are invariant under 2-isomorphisms of graphs. More precisely,
one has
PROPOSITION 5. — If two graphs r,!^ are 2 -isomorphic^ one has iso-
morphisms of lattices

A^r^A^r) and N\r) ^ Tv^r').

Let A be a lattice in a Euclidean space H. The Voronoi polyhedron of A
is the fundamental domain
VorA = [x € H | (x, x) ^ (x - A, x - A) for all A € A \ {0}}
for the action of A on H by translations. It is a compact convex polytope.
A vector A C A is said to be relevant if it corresponds to a codimension-
one-face of the Voronoi polyhedron. Otherwise said, if "H\ denotes the
hyperplan of equation {x^x} = {x — A, x — A) in 7^, the vector A is relevant
if A 7^ 0 and if VorA ^H\ contains a non empty open subset of /H\.
PROPOSITION 6. — Lei F be a connected graph.
(i) There is a natural bijection between oriented circuits ofT and faces
of codimension 1 of the Voronoi polyhedron o/A^r); more precisely^ a
vector A e A^F) is relevant if and only if it is of the form gc for some
oriented circuit cofF.
(ii) There is a natural bijection between oriented bonds of F and faces
of codimension 1 of the Voronoi polyhedron of N1^)^ more precisely^ a
vector v € N1 (F) is relevant if and only if it is of the form g^ for some
oriented bond b q/T.
(For the notations gc^Qb see the beginning of Section 2.) Similar
characterization for the faces of Voronoi polyhedra appear in Prop. 5.2
of [OdS]; our proof below is simpler and more direct.
It would be interesting to understand when two oriented circuits c\, 03
in r correspond to faces F\,F^ of the Voronoi polyhedron for A^r)
such that FI D F-^ is of codimension 2 in Ker(Ai). More ambitiously,
one would like to understand the combinatorics of this polyhedron in
terms of oriented circuits in the graph. (And similarly for oriented bonds
and 7V1 (F).)

TOME 125 — 1997 — ? 2

 LATTICES DEFINED BY FINITE GRAPHS 175

3. The Jacobian of a graph

Graphs give rise to a toy-kit which refers to classical achievements of
last century analysis. Let us first recall the following notions, for which
one out of many good references is Narasimhan's lecture course [Nar].
Let X be a compact Riemann surface. Denote by H°(X^) the space
of holomorphic 1-forms on X (which is finite dimensional), by HQ{X^ f^)*
the dual space and by H-^(X,'Z) the first integral homology group of X.
There is a positive definite sesquilinear form

H°(X^) xH°(X^) ——>C,

(^15^2)1—^ I
L
Jx
^i A c<^2

and a corresponding sesquilinear form on the dual space jFf°(X, f^)*. There
is also a natural mapping

^i(jc,z) —>H°(x^y
which applies the homology class of a loop 7: [0,1] —> X to the linear form
[<jj] i—^ f uj on H°(X,^l). This mapping is an isomorphism of ^(X.Z)
onto a lattice in H°(X^)* and the quotient

J{X)=H°(X^r/H,{X^)

is the Jacobian of X.
Given a base point XQ € X, the Abel-Jacobi map

A:X—>J(X)

applies a point x € X to the class in J(X) of the linear form uj i-^ f uj

on H°(X^)^ where 7 is some path from XQ to x. For each integer
TV > 1, let SN(X) denote the quotient of XN by the obvious action
of the symmetric group on N letters. One has also a map

A^^pO — > J { X )

N
which applies the class of (.TI, . . . , x^) to ^ A{xj).
j==i
BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE
 176 R. BACHER, P. DE LA HARPE AND T. NAGNIBEDA

Let Div(X) be the group of divisors of X , which is the free abelian

group on X. Let Div°(X) denote the subgroup of divisors of degree zero,
i.e. of divisors of the form

Y^ n^x with V^ n^ = 0.
XEX xex

The group P(X) of principal divisors (i.e. of divisors of meromorphic

functions on X) is a subgroup of Div°(X) and the quotient

Pic(X) = Div°(X)/P(X)

is the Picard group of X.

Let us recall the following classical results, where g = dimcH°(X^)
denotes the genus of X; we assume g > 1.
1) The map A^ : SN{X) -> J(X) is holomorphic for all N ^ 1.
2) If g = 1, the map A: X —^ J{X) is an isomorphism.
3) The Abel-Jacobi map induces a group homomorphism Pic(X) —>
J{X) which is an isomorphism.
4) The map A: X —> J(X) is an embedding.
5) The map A^'.S^X) -> J(X) is birational and onto (Abel's
theorem).
Moreover, J{X) determines X in the appropriate sense (this is Torelli's
Theorem; see [Nar]).
Let r be a connected graph. As before (see before Proposition 3) we
identify the cohomology group ^(I^M) to Ker(Ai), so that one has an
orthogonal projection TT : G^F, R) -^ ^(F, R). We denote by

ArC^r.z) —. (A^r))^
the restriction of TT to the group of integral cochains (see Lemma 1 of
Section 4). For e e E, let 6e € C^F.Z) be defined by

6e(e)=l, 6e{e)=-l and ^(<°') = 0 for e' € E \ {e,e};

observe that A(6e) = 0 if and only if e is an isthmus (i.e. is contained

in no cycle), that A(6e) is of length one if and only if e is a loop, and
consequently that
0<(A(^),A(^))<1
in all other cases.

TOME 125 — 1997 — ? 2

 LATTICES DEFINED BY FINITE GRAPHS 177

Choose a base point VQ € V. For each v 6 V and for each oriented

path 7 from VQ to v, one has a corresponding element
A^)=^A(6e)e(Al(r)Y.
e€7

If 7 is a closed oriented path from VQ to VQ^ one has clearly A(7) € A^F).
It follows that there is a well denned map
A^y-^A^r^/A^r).
DEFINITION. — The Jacobian of a finite connected graph F is the
determinant group
J(F) = (A^r^/A^r)
of its lattice of integral flows. Given VQ C V, the corresponding Abel-Jacobi
map is the map A^: V -^ J7'(r) defined above.
The map ArC^r.Z) -> (A^F^ is onto (by Lemma 1), so that
(A^r)) is generated by elements of the form A(7). It follows that the
image of A^p is a set of generators for j7(F).
Let Div(F) denote the free abelian group on the vertices of F. (This is,
viewed differently, the group (7°(r,Z) of integral cochains.) Let
Div°(r) = { ^ n^v C Div(F) | ^ n, = 0}
veV v^V

be the group of divisors of degree zero. (This is, viewed differently, the
group M°(r) of Section 1.) Given any VQ e V, one may see Div°(r) as the
free abelian group on the generators v — VQ (for v E V and v ^ vo). The
restriction of d* to integral cochains is a group homomorphism
rf^c^r.z) —.Div°(r)
which is onto because, when e describes E, the images rf*(^e) = Oe+ ~ 6e_
generate Div°(r). Let
P(r)=d^N\r))
be the subgroup of principal divisors of r.
DEFINITION. — The Picard group of a finite connected graph r is the
quotient
pic(r) = Div°(r)/P(r)
of the group of divisors of degree zero by the group of principal divisors.
Given VQ G V, we denote by P^y: V —> Pic(r) the map which assigns to
v e V the class of v — VQ in Pic(r).
Observe that the image of P^p generates the group Pic(r).

BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE

178 R. BACHER, P. DE LA HARPE AND T. NAGNIBEDA

DEFINITION. — A harmonic map from a graph F = (V,E) to an abelian

group G (written additively here) is a map h: V —^ G such that

deg(v)h(v) = ^ h{w) for all v € V,

wGV
w~r

where deg(^) is the number of non oriented edges incident to v in F

and where v ~ w indicates that the sum is taken over all edges e G E
for which e_ = w and e+ = v. (Our "harmonic maps" are the "balanced
maps" ofBerman [Ber].)
OBSERVATION. — Let h:V —> G be a harmonic map as above', assume
that h(vo) = 0 for some VQ € V. Then there exists a unique group
homomorphism h: Pic(r) —^ G such that h=hoP^.
Proof. — As Div°(r) is the free abelian group on V \ {vo}, any map
h: V —>• G such that h^vo) = 0 provides naturally a group homomorphism
h: Div°(r) -^ G such that h(v - vo) = h{v) for all v e V.
As 7V1 (r) is generated by the d(^)'s for v € V, the group P(r) is
generated by the d*d(^)'s for v € V, namely by the divisors

deg(v)v — V^ w.
wev
w^v

Thus h factors through Pic(F) if and only if h is harmonic.

When h is harmonic, the unicity of h follows from the fact that the
image of P^ generates Pic(r). \\
In analogy with Results (1) to (4) recalled above for Riemann surfaces,
we offer the following.
PROPOSITION 7. — Let F be a connected graph and let VQ be a vertex
off. The notations being as above, one has the following:
(i) the map Ayy: V —> J{^) is harmonic and its image gene-
rates J(T);
(ii) ifT is a polygon, then Ay^ is a bijection',
(iii) the group homomorphism Pic(r) —> J{T) induced by A^ is an
isomorphism and applies P^ (v) onto Ay^ (v) for all v e V.
If moreover the graph F is nonseparable, and not the link-graph made
of one edge connecting two distinct vertices, then
(iv) the map A^: V —> J(T) is injective.

Let S be the subset of (A^r))^ of elements of the form A{6e), e € E,

and denote by S the canonical projection of S in J(T). Then S is a

TOME 125 — 1997 — ? 2

 LATTICES DEFINED BY FINITE GRAPHS 179

symmetric set of generators of J^F), because (^e)eeE contains a basis of

C^r.Z). It is the corresponding Cayley graph
Cay(^(r)^)
that should probably be called the Jacobian of F, rather than the
group J^r) itself. Observe that, for each VQ C V and under the hypo-
thesis of (iv) in Proposition 7, the map A^ may be viewed as an isomor-
phism of r onto a subgraph of Cay(J'(r), 5). It is an open problem for us
to obtain a good analogue of Abel's theorem in our setting (see Result (5)
recalled above); here are more precise formulations of this problem. (The
radius of a Cayley graph Cay(G^ S) is the largest combinatorial distance
between the vertex 1 and another vertex g of the graph.)
(v) How do the radius and diameter of Cay^^),;?) depend on the
geometry of r?
(v') For each vertex VQ € V and for each integer TV, one has a natural
map
A^:sN(v)-.J(^).
Let <7jac(r,^o) denote the smallest integer N for which A^ is onto. How
does this "Jacobian genus" of F depend on the graph, and possibly on the
base point VQ?
A naive analogue of Torelli's Theorem does not hold, because there
are pairs of non-isomorphic graphs with isomorphic Jacobians. Examples
are given by planar graphs and their duals, as it follows from our last
proposition.
PROPOSITION 8. — Let r be a planar graph and r* a planar dual
of r. Then A^r) is isomorphic to 7V1 (F*) and 7V1 (F) is isomorphic
to A^r*). In particular the Jacobians J^F) and J(T*) are isomorphic
abelian groups. Moreover the Witt classes satisfy
l
w{A\r)) + w(A (^*)) = o e TV(Q/Z).

4. A lemma on lattices and proof of Proposition 3

Claims (i) - (iii) of the following Lemma essentially repeat Theorem 1
in Chapter 4 of [CoS], for which we give a proof.
LEMMA 1. — Let "H be a Euclidean space and let f^Q be two orthogonal
subspaces, not reduced to {0}, such that 7i = f (B Q. Let TT^- (resp. ng)
denote the orthogonal projection ofJ~L onto F (resp. onto G). We assume
the situation defined over Q in the following sense: 7i is given together
with a Q-subspace T^Q such that
dimQ(7<Q) = dim]R(7Y), Hq = (Hq H F} © (T^Q H Q)

BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE

180 R. BACHER, P. DE LA HARPE AND T. NAGNIBEDA

and {x,y) e Q for all x,y € Hq. Let A be a unimodular integral lattice
in H such that A C Hq. Set M = A H F and N = A H Q. Then
(i) M is a lattice in F and N is a lattice in Q,
(ii) M^ = 7r,r(A) and N^ = TT^(A),
(iii) the lattices M C T and N C Q have isomorphic determinant
groups^
(iv) the Witt classes of M and N satisfy w(M)4-w(TV) = 0 in the Witt
group IY(Q/Z).
Proof.
Claim (i). This holds because Hq coincides with the subset of 1-L of
those vectors x for which some integral multiple nx is in A.
Claim (ii). Let r denote the dimension of F. Choose a Z-basis
{ & ! , . . . , br} of M. As A/M is torsion-free, one may find a Z-basis

{6i,...,6y.,&y.+i,...,6^}

of A (see [Bou, VII, p. 18, cor.]). Let {b[,..., b^} denote the dual basis
defined by (b^bk} = 6j^ for j,k E { ! , . . . , m}; it is again a Z-basis
of A because A is unimodular. As ^y{b1-) = 0 for j > r, the set
{^(^ • • ' , ^W} is a Z-basis of TT^(A). Any x € F is of the form
r

^XjTT^)
J=l

where x^,...,Xr C R; and (a;,M) € Z if and only if (x,bj} e Z for

j € {!,..., r}, namely if and only if r c i , . . . , Xr € Z. It follows that M^
and 7T7-(A) coincide. Similarly N^ = 7r^(A).
Claim (iii). Consider now the restriction A —> M11 of TT^-. It factorizes
firstly as a map A/TV —^ M^, and secondly as a map

(RM : A/(M C TV) —> M^/M

which is onto by (ii). Choose A € A and denote by [A] its class modulo
Me TV. Assume that ^M([A]) = 0, namely that 7r^(A) <E M; as A-7Tjr(A)
is in A H Ker(7T7-), one has A - TT^(A) € TV and consequently A C M C TV.
It follows that (pM is injective, namely that (^M is an isomorphism. As
one has similarly an isomorphism

^v:A/(M©TV)—>N^/N
this ends the proof of Claim (iii).

TOME 125 — 1997 — ? 2

 LATTICES DEFINED BY FINITE GRAPHS 181

Claim (iv). Let ( p : M ^ / M —> N ^ / N be the isomorphism of (iii). For

each pair m^^m^ G M^/M, choose a pair of vectors Ai, X^ € A such that
TT^(Ai), TT^-(As) are respectively representants ofm^ and m^. Then Tr^(Ai),
^(As) are representants of ^p{m^)^{m^) € N ^ / N . As

(7r^(Ai),7r^(A2))+<7rc;(Ai),7r<?(A2)) = (Ai^) € Z,

one has
<7r^(Ai),7r^(A2)> EE -<^(Ai),7r^(A2)) modZ.

Thus, with the notations of Section 1, (M^/M,^) ^ ( N ^ / N , -^v),

namely w(M) + w(AQ = 0 € IV(Q/Z). []
Proo/ o/ Proposition 3. — The first two claims of Proposition 3 are
particular cases of the claims of Lemma 1.
For Claim (iii) of the Proposition, observe that the cohomology space
^(r.R) = C1 {T ^V) / l~m(d) may be viewed as the image of the first pro-
jection with respect to the orthogonal decomposition

C^r.M) = Ker(Ai) Clm(d).

Therefore the integral cohomology ^(F, Z), which is a discrete subgroup

of ^([Link]), can be viewed as the orthogonal projection of (^(I^Z)
on Ker(Ai). Claim (iii) of Proposition 3 is consequently a particular case
of Lemma 1 (ii). []

5. Proof of (i) and (iii) in Propositions 1 and 2.

As in Sections 1 and 2, we consider a connected graph F = (V, E) and
the lattices
A^F) c Ker(Ai), N^F) c Im(d).
Recall from Section 2 that each oriented circuit c in F defines a 1-form
Qc ^ A^r) and that each oriented bond b in F defines a 1-form g^ € 7V1 (r).
Let T be a spanning tree in F; denote by T the set of oriented edges of T.
For any edge e G E not in T, there is a unique oriented circuit c(e) in r
containing e and edges in T. For any edge e € E which is in T, there is a
unique oriented bond b{e) containing e and edges not in T.
Let F be a subset of E such that e € F if and only if e C F. An
orientation of F is a choice of a subset 0(F) of F which contains exactly
one oriented edge from each pair {/, /} C F. Let 0(E\T) be an orientation
of E \ T and let 0(T) be an orientation of T; they constitute together an
orientation of E, also called an orientation of the graph F.

BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE

 182 R. BACHER, P. DE LA HARPE AND T. NAGNIBEDA

It is well known that

• (^c(e))eeO(E\T) is a basis ofKer(Ai),
• (^b(e))eeO(T) is a basis oflm(d)
(see Theorem 5.2 in [Bil]). More precisely, one has the following.
LEMMA 2. — Let T be a spanning tree in F and let 0(E) c E be an
orientation ofT. The notations being as above, one has:
• (^c(e))eeo(E\T) ^ a Z-basis of the lattice A^F) in Ker(Ai),
• (^(e))eeo(T) ^ a Z-basis of the lattice 7V1 (r) in Im(d).

Proof.— Choose an orientation 0(E) ofFand let A = ^ A(e)<?e C A^F).

Then eeO(E)
A-^A^^cA^r)
eeO(E\T)

may be viewed as an integral harmonic 1-fbrm on T and is consequently

zero. Hence (^c(e))eeO(E\T) is a Z-basis of A^F).
Let v = ^ ^(e)6e € TV^F). Then
eeO(E)

^-Y, ^{e)g^^N\T)
eeO(T)

may be viewed as a boundary whose restriction to T is zero, and is

consequently zero as a boundary of F. Hence (^e))ecom ls a Z-basis
ofA^F). D
Proof of (i) and (Hi) in Propositions 1 and 2.
The graph F is bipartite if and only if all its circuits have even lengths.
The length of an oriented circuit c of F is the norm (gc,9c) where gc is as
above. Hence Claim (i) of Proposition 1 follows from Lemma 2.
The graph is Eulerian if and only if all its vertices have even degrees.
Let v-t,...,Vn be an enumeration of the vertex set V of F. For each
j € { 1 , . . . ,n}, let 6j € C7°(r,R) denote the characteristic function of Vj.
The degree ofvj is the norm (d(^-),d(^)). Now (c?(^))i<^<n-i is a basis
of the vector space Im(c?), because F is connected, and it is also a Z-basis
ofTV^F), because

d(c°(r^))=c\r^)nim(d).
Claim (i) of Proposition 2 follows.

TOME 125 — 1997 — ? 2

 LATTICES DEFINED BY FINITE GRAPHS 183

The determinant of the lattice 7V1 (r) is the determinant of its Gram
matrix G = {{d{6j),d(6k)})i<j,k<n-i, and one has

( d ( 6 - } d(6 ) } = ( de^) if k
=^
[ —)) {edges between vj and Vk} otherwise
(we agree here that loops do not contribute to degrees). It is a standard
result that the determinant of G is precisely the complexity of the graph r
(see Theorem 6.3 in [Bil]). Lemma 1 shows that the determinant ofTV^F)
is equal to that of A^F). Claims (iii) of Propositions 1 and 2 follow. []
Claims (ii) in Propositions 1 and 2 could be proved now, but they are
also straightforward consequences of Proposition 6, proved in Section 7
below.

6. Proof of Propositions 4 and 5

Given a graph r, the circuit graph Cir(r) of F is the following simple
graph:
• its vertices are the circuits in F (a circuit being here an unoriented
simple closed curve, possibly a loop);
• two circuits Ci,C2 of r are connected by an edge in Cir(r) if they
have at least one common edge in F.
For example, if r is a complete graph with 4 vertices, then Cir(r) is a
complete graph with 7 vertices.
It follows from the definitions that saying that Cir(r) is connected is a
reformulation of saying that the polygon matroid of r is connected.
LEMMA 3. — Let r be a connected graph which has no loop and no
vertex of degree 1. Then the following are equivalent:
(i) r is separable,
(ii) Cir(r) is not connected,
(iii) A^F) is decomposable.
Proof.
(i) => (ii) and (iii). Let F i , . . . , F^ be the blocks of r, with b ^ 2. As r
has no vertex of degree 1, none of the graphs Cir(F^) is empty, and Cir(r)
is the disjoint union of these. For the same reason, none of the lattices
A^Fj) is reduced to {0}, and A^F) is the orthogonal sum of these.
(ii) =^ (i). Let Ciri,..., Cir^ denote the connected components of
Cir(F), with b > 2. For each j C { 1 , . . . . &}, set

Ej = {e e E | e belongs to at least one circuit contributing to Cir^- }

BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE

184 R. BACHER, P. DE LA HARPE AND T. NAGNIBEDA

and let Tj denote the subgraph of F consisting of edges in Ej and their

incident vertices. One has £'1 U ... U E^ = E because r has no vertex of
degree 1, and this is a disjoint union by definition of the Cir/s. It follows
that F i , . . . , Fb are the blocks of F, and F is separable because b > 2.
(iii) => (ii). We assume that Cir(r) is connected, and we will show
that A^F) is indecomposable. For this, as A^F) is spanned by vectors
associated to cycles (see e.g. Lemma 2), it is enough to show the following:
given two oriented cycles c ' ^ c " in F, there exist oriented cycles Co = c',
ci,..., Ck = c" such that (^_i, 9c,} + 0 for all j € { ! , . . . , k}.
As Cir(r) is connected, possibly upon changing the orientation of c",
we may assume without loss of generality that d and c" share at least one
oriented edge, say eo- Let F C E be the set of oriented edges such that

9c' + Qc" = 2<?eo + y^ OLe^e

eGF

with Og e {1,2} for all e € F. There are also oriented cycles c i , . . . , Cm

with support in F U {eo} such that

9c' + Qc" = Pci + • • • + gem

and we may assume that ci contains eo. Both (gc^Oa) and l\gc"•>9c^
are sums over eo U F of integers which are all > 0, with the integers
corresponding to eo being > 0. Hence

(9c',9c,) T ^ O + (fi^^ci)

and this ends the proof. []

An analogous result holds for the lattice 7V1 (F).
LEMMA 4. — Lei T be a connected graph. Then the following are
equivalent:
(i) r is separable,
(ii) TV^r) is decomposable.
Proof.
(i) => (ii). Let VQ e V be a cut vertex and let F i , . . . , F^ be the connected
components of the subgraph of F induced by V \ {vo}. For j € { 1 , . . . , 6},
let Vj denote the vertex set of 1^; observe that V\ U . • . U V^ = V \ {vo}.
Then (^))^eyiU...UVb is a basis of TV ^r) and {d(6y),d(6^)) = O i f v e V^
w € Vk, j 7^ k. It follows that TV^F) is an orthogonal sum of factors, one
for each block of F.

TOME 125 — 1997 — ? 2

 LATTICES DEFINED BY FINITE GRAPHS 185

(ii) => (i). Let 7V1 (T) = TV' ® TV" be a non trivial orthogonal decompo-
sition. Let b be an oriented bond in F. Writing gb = {g' , g " ) € N1 © TV",
one has either </' = 0 or </ = 0. Indeed, as

(g^gb} = (gi9b} + {g'b^'b}

is the number of edges in &, the support of b is the disjont union of
the support of b' and of that of b". One concludes by minimality of b
that gb = gb or ^ = g ^ .
Consider now the cuts d(6y) for v € V. If all of them were bonds, we
could define V = {v e V \ d{6y) e N ' } , and similarly for TV", and the
corresponding induced subgraphs would be disconnected from each other,
in contradiction with the hypothesis. Hence there exists at least one vertex
VQ C V such that d(6y^) is not a bond. Then d(6y^) properly contains some
bond, hence VQ is a cut vertex of F, so that F is separable. []
Proposition 4 is a rephrasement of Lemmas 3 and 4.
Proof of Proposition 5.
There is no loss of generality if we assume that F and F' are obtained as
follows. Given a graph Fi with two distinct vertices u\^v\ and a graph FS
with two distinct vertices -us, ^2; the graph F is obtained from the disjoint
union Fi U F^ by the identifications

u\ = u-2 = u and v\ = i^ = v

and the graph r' is obtained similarly by the identifications

ui = ^2 = u' and v^ = u^ = v'.

According to the definition in Section 2, V is obtained from r by twisting

about {u^v}.
For each A G A^F), define V € C^F'.Z) by

A(e) ife€E ^l
vn=<f
v /
( )'
f-A(e) ifeGE^).

We claim that A' € A^F'); it follows that the application A i—^ A' is an
isomorphism A^F) -^ A^F'). The claim means that (d*A')(^) = 0 for
all v G ^(F'); the non trivial equalities in the claim are

^\f)(uf)=0=^\f){vf).

BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE

186 R. BACHER, P. DE LA HARPE AND T. NAGNIBEDA

As A c A^F), one has

(d*A)(w)= ^ A(e)=0
e€E(r)
e-^.=w

for all w C ^(F), where e+,e_ denote respectively the head and the tail
of e. In particular
^A(e) = ^A(e),
eGE(ri) eGE(r2)
e-)-='ui e—='U2

^A(e) = ^A(e),
eeE(ri) e€E(r2)
e—=v\ e-(-=='V2

^A(e) = ^A(e)
e€E(r2) eGE(r2)
e—==tt2 e4-='y2

(the last equality is easily obtained from ^ (d*A)(w) =0). It follows

that one has also wev(ri)

^\\u1) = ^ A'(e) + ^ A'(e)

eGE(ri) eeE(F2)
e+=ni e+=V2
=
E A^) - E ^= °
eeE(ri) eGE(r2)
e
+=ul e+=V2

and similarly (d*A')('y 7 ) = 0, so that the claim is proved.

For each v e ^(r), define v ' € C'^F^Z) by

^(e}=(
v /
"(e) i f e e E ^ ) -
l-^(e) i f e C E ^ ) .

We claim that v ' € A^ l (^'); it follows that the application v \—> v ' is an
isomorphism TV^F) -^ TV^FQ.
To prove the claim, it is enough to check that v ' is orthogonal to A^F').
But any element of A^F') is the image A' of some A e A^F) by the
isomorphism above. Thus

^^f}=(^\)=0

and the claim is proved. []

TOME 125 — 1997 — N° 2

 LATTICES DEFINED BY FINITE GRAPHS 187

7. On Voronoi polyhedra: proof of Proposition 6

As announced in Section 2, we characterize here the codimension-one-
faces of the Voronoi polyhedra

VorAi(r) = [x € Ker(Ai) | {x, x) < (x - A, x - X)

forallAeA^r)^}}
and Vcr^yi en-
Recall that a vector A -^ 0 in a lattice A C H is called relevant if the
affine hyperplane

[x € U | (x, x) = (x - A, x - A)}

contains a codimension-one-face of the Voronoi polyhedron of A. For the

following lemma, we agree that a vector A € A is reduced if (A, A) ^ (A', A'}
for all A' € A + 2A.
LEMMA 5. — A vector A C A \ {0} is relevant if and only if A is reduced
and A, — A are the only reduced vectors in A + 2A.

Proof. — See Theorem 10, Chap. 21 of the second edition of [CoS]. []

Consider a connected graph r and the associated lattices

A^F) c Ker(Ai) and N^T) C Im(d).

Proof of Proposition 6.
Claim (i). Let c be an oriented circuit of F. As Qc takes values in
{-1,0,1}, any A' € Qc + 2A 1 (^) takes even values outside the edge-set of
c and odd values on the edge-set of c. If moreover A' -^ ±gc there exists
e e E such that |V(e)| > |^c(e)|, so that (V.V) > (pc^c). It follows
from Lemma 5 that gc is relevant.
Conversely, let A C A^r) be a relevant vector; we have to show that
there exists a circuit c in F such that A = g^ As A -^ 0 there exists an
oriented edge ei € E such that A(ei) ^ 1. As A is a flow, there exists
an oriented circuit c with cyclically ordered edges ei, 625 • • • , ^ki e/c+i = ei
such that A(e^) > 1 for all j e { 1 , . . . , k}', in particular

(\9c) >k= {gc,9c)-

On the other hand

(A - 2g^ A - 2^) = (A, A) + 4(^, ^) - 4(A, ^) > (A, A)

BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE

 188 R. BACHER, P. DE LA HARPE AND T. NAGNIBEDA

because A is reduced. It follows that

(A,^c) =k
and that A(e) € {-1,0,1} for all e € E. If one had A ^ g^ there would
exist by the same argument (A is a flow) another oriented circuit c' with
edge-set disjoint from that of c, and one would have
(A, A) = (A - 2g^ A - 2^) = (A - 2^, A - 2^)

in contradiction with Lemma 5. Thus \ = gc-

Claim (ii). If b is a bond in F, then g^ is relevant by the same argument
as in the previous step.
Conversely, let v e 7V1 (T) be a relevant vector. Let / e C7°(r,Z) be
such that v = df and set
VQ = [x € V | f(x) > f(y) for all y e V}.

Observe that VQ depends only on v (because F is connected so that / is

well defined up to an additive constant) and that VQ is a proper subset
of V (because v ^ 0 so that / is not a constant function).
The subgraph of Y induced by VQ may have several connected compo-
nents. Let FI be one of them and let V\ be the vertex set of Fi. We set
b = [e € E | e+ € Vi and e_ € V \ Vi}.
If \b\ = k one has
{^9b) >k= (g^gb)-
The end of the argument runs as in the previous step. []

8. Proof of Propositions 7 and 8

Proof of Proposition 7.
Claim (i). Let v be a vertex of F. As d(6y) e lm(d) is orthogonal
to A^F)^ one has

A(d^))= ^ A ( ^ ) = 0 .
e€E
e+=v

Choose an oriented path 7 from VQ to v. Join VQ to each w ~ v by an

oriented path 7^ which begins by 7 and which ends by an edge from v
to w. Then

deg(^)A(7) - ^A(7.) = - ^ A(^) = ^ A(^) = 0

wCV eGE eGE
w~v e-=v e-^-==v

TOME 125 — 1997 — ? 2

 LATTICES DEFINED BY FINITE GRAPHS 189

and consequently
deg(^)A^ - ^A^(w) = 0.
w^V
w^v

In other words, A-yy is harmonic.

The image of A^o generates the Jacobian of F, as has already been
observed just after the definition of the Jacobian.
Claim (ii). If r is a polygon with n vertices and n edges, its Jacobian
(A^F)) /A^r) is a cyclic group of order n. As A-up is clearly surjective,
it is a bijection.
Claim (iii). By (i) and by the observation of Section 3 which precedes
Proposition 7, there exists a group homomorphism

a:Pic(r)——J(T)

which maps the class of v — VQ to A^y (v) for each v € V and which is onto.
We have already observed in Section 3 that the linear map

d^.C\r,R) —.Im(d*)

restricts to a homomorphism from (^(I^Z) onto Div°(r). As d* is the

composition of the orthogonal projection Tr.'C^r.R) —> lm(d) and of
some linear isomorphism Im(c?) —> Im(c?*), the map d* restricts also to a
homomorphism

Tr^r.z)) = (^(r))^ —. Div°(r)

which is onto (the equality holds by Lemma 1). As ^(A^r)) = P(F) by
definition, one has a homomorphism

(3N: (A^r^/A^r) — Div°(r)/P(r) = pic(r)

which is onto. The composition of the isomorphism

<^(r) ^ (A^r))^1^)
(see Lemma 1) and of (3^ provides a group homomorphism

/?A:^(r)—Pic(r)
which is onto.
Let v € V and let 7 be some oriented path from VQ to v. As A^(v} is
the class in J(T) of the orthogonal projection of ^ 6e onto Ker(Ai), the
eG7

BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE

190 R. BACHER, P. DE LA HARPE AND T. NAGNIBEDA

proof of Lemma 1 shows that (j){A^(v)) is the class in (N1 (F))^ / N1 (F)
of the orthogonal projection of ^g^ 6e onto Im(d). Hence /?A(Ayo('y)) is
the class of d"(^^ 6e) = v — VQ in Pic(r), or in other terms

(3A{A^{v))=P^(v).

It follows that the homomorphisms f3\ and a are inverse to each other.
Claim (iv). Let x^ y be two distinct vertices of F. As F is nonseparable,
there exists an oriented circuit c which contains x and y . (This is a
consequence of Monger's theorem; see e.g. [VLW, p. 407].) Let n be the
size of c and let

V l = X , Z>2, • • • ^fc-1, Vk = V, Vk+l, " - 5 Vn, ^n+1 = Vl

be a cyclic enumeration of the vertices of c. Let h: V —f Z/nZ be the map

which applies a vertex v € V to the class of j e Z if v = Vj and to 0
otherwise. It is easy to check that h is harmonic, and that h{x) ^ h(y).
(Observe that the map v \—^ h{v) — h{vo) has the same properties and
maps moreover VQ to 0.)
We have just shown that harmonic maps separate the vertices of F. It
follows from the observation of Section 3 that P^p: V —> Pic(F) is injective.
Claim (iii) implies now that A^p: V —> J(T) is also an isomorphism. []
Recall that a graph r is planar if it embedds in the sphere. One
defines the dual graph F* of r with respect to an embedding of r in the
sphere. The vertices of r* are the components of the complement of F in
the sphere. There is a natural bijection e \—> e* between edges of F and
edges of F*; the ends of e* in F* are the vertices corresponding to the
components with which e is incident. (See e.g. [VLW, Chap. 32].)
Proof of Proposition 8.
Denote by E the set of oriented edges of r (or of F*). A subset F'
(resp. F") of E is the set of some oriented circuit c' (resp. c") in r if and
only if it is the set of oriented edges of some oriented bond V (resp. b")
in r*; moreover, if this is so, then

{Oc^gc"} = {gb'^gb"}
where the left-hand side is an inner product of two vectors in A^r)
and where the right-hand side is the inner product of the corresponding
vectors in TV1^*). As A^F) has a Z-basis {^ci? • • • ^9cm-n+i} where
ci,... ^Cm-n+i are oriented circuits in r (e.g. by Proposition 6), the
vectors {gb^ " ", gbm-n+i} defined by the corresponding oriented bonds
in r* constitute a Z-basis of 7V1 (F*). The two resulting Gram matrices

TOME 125 — 1997 — ? 2

 LATTICES DEFINED BY FINITE GRAPHS 191

being equal, the two lattices A^r) and TV^r*) are isomorphic. Similarly
7V1 (F) and A^r*) are isomorphic. The last claim of Proposition 8 follows
now from Proposition 3. []

9. Remarks and Examples

Remarks.
1) The automorphism group Aut(r) of the graph r acts naturally by
isometrics on G°(r,]R) and C^r.R), preserving (7°(r,Z) and (^(F.Z)
respectively. One may also check that d and d* are equivariant operators
for these actions, so that Aut(T) acts naturally as isometrics of the lattices
A^r) and 7V1 (r).

2) There would be no difficulty to extend all previous considerations to

graphs with positive weights on vertices and edges. Inner products would
then be defined by formulas such as

(/i,/2) =^rn(v)f,(v)Mv)^ (^2) = \^{e)g^e)g^e)

v^V e€E

where m: V —> R^_ and £: E —> R^_ are given weights. (More generally,
integral-valued negative weights would give rise to indefinite inner product
spaces over Z.)
If (r,-^) is a weighted graph with m(v) == 1 for all v € V and
£(e) = i{e) e {1,2,3,...} for all e € E, the corresponding lattice A^F,^)
is isomorphic to the lattice A^I^) where 1^ is obtained from r by
subdividing each edge e in £{e) edges. The lattice 7V1 (F,-^) in this case is
isomorphic to the lattice 7V1 (1^) where 1^ is obtained from r by replacing
each edge e by £(e) edges in parallel.
3) The operators d and d* can be identified to their matrices with
respect to the bases (^)^ev of C°(T, R) and (<?e)ecE of C^F, M). As these
matrices have integral entries, their reduction modulo 2 define linear maps
between the spaces C°(r^¥^) and (^([Link]) of functions from V and E
to the field of two elements.
In case r is a simple connected graph, the subspace

im^c^r^-^[Link]))
is known as the binary code C(T) of the graph F. In the \E\-dimensional
space FS' ' ^ C^I^Fs), the binary code C(T) is the subspace generated
by the columns of the matrix d or by the rows of the incidence matrix d*.
(See Chap. 32 in [VLW].)

BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE

192 R. BACHER, P. DE LA HARPE AND T. NAGNIBEDA

In some sense, the lattice 7V1 (T) is with respect to Z what the code
C(r) is with respect to Fa.
This can be generalized as follows: the lattices 7V1 (F) and A^F) are
sublattices of C^r.Z) w Zn'. Fixing an orthonormal basis of (^(F.Z)
(given by an orientation of the edge set) one gets a pair of codes
C^r)=N\r)^z^q and C^(F) = A^F) (g)z ¥q
where Fg denotes a finite field.
Let us check that the orthogonal of C^(F) is precisely C^(F). On one
hand, it is clear that C^(F) C C^T)1-. On the other hand, consider
A C CN(^)•L^ let (d(6j))\<j<n-\ be the basis of Im(d) considered at the
end of Section 5 and let (Z^)i<j<n-i be the corresponding basis of C^(F);
the conditions A -L hy (1 < j <: n — 1) imply that A is a g-flow on F; as
such a g-flow can be represented by a Z-flow [BrO, Prop. 6.3.7], it follows
thatAeC^(F).
The weight enumerators of the 2 codes are obtained as specializations of
Tutte's dichromatic polynomial and are related by Mac-Willams identity
[BrO, Prop. 6.5.1 and 6.5.2].
Is there anything analogous relating the i^-series of the lattices A1 (T)
and 7V1 (F)? (The obvious lattice analogue of the Mac-Williams identity
is the Poisson summation formula which relates the 19-series of a lattice
and its dual lattice.)
4) The setting exposed here has a straightforward generalization to
higher dimensional objects. For example, let X be a finite CW-complex
of dimension d. For each j G { 1 , . . . , d}, let E-7 denote the set of oriented
j -cells in X, and let C^X, M) denote the space of all functions /: E-7 -^ R
such that f(e} = —f(e) for all e € E-7 (where the bar indicates as above a
change of orientation). One has a Laplacian operator
A^- = d^dj +^-_idJ_i,
an orthogonal decomposition
(*) (^(X.R) = Ker(A^) C Im(^-i) C Im(^*)
and lattices
( A^X) = ^'(X.Z) n Ker(A^) C Ker(A^),
^ N^X) = ^'(X.Z) nlm(^_i) C Im(^-i),
[ M^X) = C^X.Z) H Im(dJ) C Im(^*)
as above.

TOME 125 — 1997 — N° 2

 LATTICES DEFINED BY FINITE GRAPHS 193

For example any finitely generated group

G=(5i,...,^|I?i,...,^)

with k generators and £ relations gives rise canonically to a CW-complex of

dimension 2 with 1 vertex, k edges (which are loops) and i faces. It would
be interesting to explore the properties of the resulting lattices A1 and M1.
The idea to write down a "Hodge decomposition" (*) in a combinatorial
setting is of course most classical (see e.g. [Eck] or [Bor]), but the
corresponding lattices have apparently not been systematically studied.
Here are some examples.
1. Polygons, bond graphs and root lattices. — Let F be a polygon
with n vertices and with n edges. Then A^r) C Ker(Ai) is clearly the
lattice \/nrL C K of minimal norm n and determinant n. The Jacobian
J^r) is the cyclic group of order n.
The lattice 7V1 (r) C lm(d) can be described as follows. Choose an
orientation ofF, let e i , . . . , en be a cyclic enumeration of the corresponding
oriented edges, and let 6j e C^r,]^) be defined by 6j(ej) = 1, ^-(e/c) = 0
if k ^ j. Then
n n
7V1(T = € z and
) {i^A-1 ^ ]L^' = °}
J=l .7=1

has a basis (^j+i — ^j)i<j<n-i' This is a root lattice of type A^_i, with
minimal norm 2 and determinant n (see [CoS, Chap. 4, § 6.1]). The Witt
class
w(N\r)) = w(An-i) = -w(A\r))
may be explicitly calculated (see [Ker, pp. 66-67]). The easiest cases are
those for which n = p° is a prime power. If c is even then w^N1^)) = 0.
If c is odd then '^(TV^r)) is not 0, and is the class of the bilinear form

b: Z/nZ x Z/nZ —> Q/Z

given by &(1,1) = n~1.

The plane dual F* of F is the bond graph with 2 vertices and n edges
between them. The minimal norm of A^F*) is 2.
Claim (ii) of Proposition 1 implies that a graph F is simple (no loop
and no multiple edge) if and only if the lattice A1 (r) has minimal norm
at least 3.

BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE

194 R. BACHER, P. DE LA HARPE AND T. NAGNIBEDA

Let A be a lattice in some Euclidean space which is a root lattice in the

sense that A is spanned by its vectors of norm 2. If A is of the form A^F)
for a connected graph F, then A is necessarily a root lattice A^. Indeed,
let ai, 0:2 be two distinct roots in A^F). Then aj corresponds necessarily
to two edges e^e'j joining the same ends {j = 1,2). If ([Link]) 7^ 0, then
the four edges ei, e[, 63, e^ must have the same ends. It follows that a graph
with A^r) a root lattice is necessarily a graph with two vertices only.
In particular, if a graph r has the lattice A^F) isomorphic to that of
the bond graph with n edges, then r itself is the bond graph with n edges.
2. Complete graphs. — Let Kn be a complete graph on n vertices,
where n > 4. Then P^(Kn) is the "lattice of thorns", studied in [Mar] in
relation with representations of the Mathieu groups Mi2 and M^.
Recall that the n-th lattice of thorns Tn is defined as follows. The trivial
lattice Z71 C M71 gives rise by exterior power to a lattice
An = Z71 A Z71 c E = M71 A R71
isomorphic to ^n-1)/2 c R71^-1)^. if ^... ,(°n is the canonical basis
of M71, a lattice vector
a=^aij€i/\ej € An
i<3

can be viewed as a directed graph with vertex set { 1 , . . . ,n} and with
|o^j| edges between i and ^', directed from z to j if a^j > 0 and from j to
i if aij < 0. Let F C E be the subspace of E of dimension j (n — 1) (n — 2)
defined by any (n — 1) among the n equations
Q / l,2+Q / l,3+ ' " ^ r ^ ^ n =0,

^n,l + ^n,2 + • • • + On^n-l = 0

(with Oj^ = —o^ij if j > i)' The n-tb. thorns lattice is by definition the
lattice
Tn = An n F C F.
A lattice vector a = ^ a^j-e^ A Cj C Tn can be viewed as a zero-sum
i<3
oriented graph on vertices { 1 , . . . ,n}, where "zero-sum" means that the
indegree and the outdegree of any vertex are equal.
Let Tij^k denote a "thorn" {%,J,A;}, namely a triangle on the vertices
{%,j, k} with
^J = aj,k = Oik.i = 1.

Then (Ti^j)i<^<yi is a Z-basis of the lattice Tn. This basis is isomorphic

to the basis of the lattice ^{Kn) associated to the spanning tree T in Kn
where the edge-set of T consists of (n — 1) edges adjacent to one vertex.

TOME 125 — 1997 — ? 2

 LATTICES DEFINED BY FINITE GRAPHS 195

The minimal norm of the lattice Tn is 3 (the girth of Kn) and the
determinant is n71"2 (the complexity of Kn). The dual lattice (A^J^n))^
is explicitly described in [Mar], and one could deduce from that description
the structure of the Jacobian of Kn. But we find it easier to turn to the
Picard group.
Let { ^ i , . . . ,^n} be an enumeration of the vertices of Kn^ and denote
by 6j the characteristic function of Vj(l < j < : n). The group P{Kn) of
principal divisors is generated by the elements
n

(n-l)6,-^6k=^^,k6k
Kk<n A;=l
W

for j G { ! , . . . , n}, where Ao = (^j,k)i<,j,k<,n is the n x n matrix of

the Laplacian. A routine computation shows that there exist matrices U
and V in GL(n, Z) such that
/I 0 0 ... 0 0\
0 n 0 ... 0 0
0 0 n ... 0 0
UAoV=
0 0 0 ... n 0
\0 0 0 ... 0 o7
(see e.g. [Bou, p. [Link].21]). It follows that

Pic(Kn) ^ J(Kn) ^ (Z/nZ)71-2.

Computations show that the corresponding Witt class is sometimes zero,

for example when n is a square, and sometimes not zero.
An element of the lattice N^(Kn) may be viewed as an oriented graph
on vertices { l , . . . , n — 1}, such that each vertex is either the head or the
tail of all edges incident to it. Let C1', 1 < i < n — 1 denote a "claw" {z},
namely an oriented graph with aij = 1 for each j ^ i and a^^ = 0 for
k ^ i and for any £. Then (C^K^n-i is a Z-basis of the lattice ^{Kn).
The number of non-oriented bonds in Kn is the number of non-trivial
partitions of the vertex set of Kn, namely
n
+••-+ = 271-1 - 1.
.n-1.

It follows from Proposition [Link] that the Voronoi cell of ^(Kn) has
^n-i _ ^ pairs of parallel faces. Now it is known that, for any lattice in

BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE

 196 R. BACHER, P. DE LA HARPE AND T. NAGNIBEDA

a Euclidean space of dimension (77, - 1), the number p of pairs of parallel

faces of the Voronoi cell satisfies the inequalities

n- 1 ^p< 2n~l - 1

(the first inequality is trivial, the second one is classical — see Thin. 10 of
Chap. 21 in the second edition of [CoS]). Thus the lattice A^(J^) is one
for which the second inequality above is an equality.
3. Strongly regular graphs. — Let T be a connected strongly regular
graph with parameters (n,k,\^i). There are classical formulas for the
eigenvalues and their multiplicities of the Laplacian Ao, so that the order
of the group J(T) is easy to compute (see e.g. [Bil]). But the actual
structure of J(T) requires further computations.
If Pet is the Petersen graph with parameters (10,3,0,1), the eigenvalues
of Ao are 0,2,5 (resp. with multiplicities 1,5,4), so that

\J(Pet)\=^^=20W.

The computation of the invariant factors of Ao (see the analogous formula

for U^oV in the previous example) shows that

J(Pet) w Z/2Z© (Z/10Z)3.

There are two non-isomorphic strongly regular graphs with parameters

(16,6,2,2), which are switching equivalent. Eigenvalues computations show
that their Jacobian has order
46
4 X„0
o9
^ 935
1 n '
16
The first of these is the lattice graph -L(4), for which one has

JT(L(4)) ^ (Z/8Z)5 © (Z/32Z)4.

(For this computations and all the next ones, we are most grateful to
Shalom Eliahou, who has used the function ismith of Maple V. Computa-
tions which are quite similar are reported in [BVE].) The other one is the
so-called Shrikhande graph (see [BrR, e.g. Fig. 5.2]), for which

^(Shr) w (Z/2Z) © (Z/8Z)2 © (Z/16Z)2 © (Z/32Z)4.

Thus the structure of J(T) for a strongly regular graph does not depend
on the parameters (or on the spectrum) only. Similarly, there are four non-
isomorphic strongly regular graphs with parameters (28,12,6,4), which

TOME 125 — 1997 — ? 2

 LATTICES DEFINED BY FINITE GRAPHS 197

are switching equivalent. The Jacobian of the triangular graph T(8) is the
direct sum of cyclic groups of orders 2 (multiplicity 2), 14 (multiplicity 13)
and 112 (multiplicity 6). For each of the other three, the so-called Chang
graphs, the Jacobian is the direct sum of cyclic groups of orders 14
(multiplicity 12), 56 (multiplicity 1) and 112 (multiplicity 6).
For each prime power q of the form 4:k + 1, the Paley graph Yq has
parameters
((^(g-l),^-5), }((?-!))

and the order of its Jacobian is

I ^r M - 1 ^-vW9"1^2^^^72 - 1 ^ 2 -^- 1 )/ 2
\JVLq)\~~q\~^~) \~2~) ~q[~4~)
A computation shows that, for q = 5,13,17,29,37,41,

J(T,) ^ (z/^- i)z) e (z/^(g-1)^"3^.

At the time of writing, we have not found a pair of 3-connected non-
isomorphic graphs with isomorphic A^F).

BIBLIOGRAPHIE

[Ber] BERMAN (K.A.). — Bicycles and Spanning Trees, SIAM J. Alg. Disc.
Meth., t. 7, 1986, p. 1-12.
[Bil] BIGGS (N.). — Algebraic Graph Theory. — Cambridge University
Press, 1974 (Second Edition 1993).
[Bi2] BIGGS (N.). — Homological Coverings of Graphs, J. London Math.
Soc (2), t. 30, 1984, p. 1-14.
[Bi3] BIGGS (N.). — The Potential of Potential Theory, Preprint, London
School of Economics, 1994, Preprint to appear in the volume "The
Future of Graph Theory".
[Bi4] BIGGS (N.). — Algebraic Potential Theory on Graphs, Bull. London
Math. Soc., to appear.
[Bol] BOLLOBAS (B.). —Extremal Graph Theory. —Academic Press, 1978.
[Bor] BOREL (A.). — Cohomologie de certains groupes discrets et laplacien
p-adique, Seminaire Bourbaki, t. 437, 1973/1974.

BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE

 198 R. BACHER, P. DE LA HARPE AND T. NAGNIBEDA

[Bou] BOURBAKI (N.). — Algebre, chapitres 4 a 7. — Masson, 1981.

[BCN] BROUWER (A.E.), COHEN (A.M.) and NEUMAIER (A.). — Distance
Regular Graphs. — Springer-Verlag, 1989.
[BVE] BROUWER (A.E.) and VAN EIJL (C.A.). — On the p-rank of the
adjacency matrices of strongly regular graphs, J. Alg. Combinatorics,
t. 1, 1992, p. 329-346.
[BrR] BRUALDI (R.) and RYSER (H.J.). — Combinatorial Matrix Theory.
— Cambridge Univ. Press, 1991.
[BrO] BRYLAWSKI (T.) and J. Oxiey. — The Tutte Polynomial and its
Applications, in "Matroid Applications", N. White Ed., Cambridge
University Press, 1992, p. 123-225.
[CoS] CONWAY (J.H.) and N.J.A. Sloane. — Sphere Packings, Lattices and
Groups. — Springer-Verlag, 1991.
[CDS] CVETKOVIC (D.M.), DOOB (M.) and SACHS (H.).— Spectra of Graphs.
— Academic Press, 1980.
[Dix] DIXMIER (J.). — Les C^-algebres et leurs representations, 26 edition.
— Gauthier-Villars, 1969.
[Eck] ECKMANN (B.). — Harmonische Funktionen und Radwertaufgaben in
einem Komplex, Comment. Math. Helv., 1.17,1944/1945, p. 240-255.
[Ker] KERVAIRE (M.). — Unimodular Lattices with a Complete Root
System, L'Enseignement mathematique, t. 40, 1994, p. 59-104.
[Mar] MARGOLIN (R.S.). — Representations of M^, J. Algebra, t. 156,
1993, p. 362-369.
[Nar] NARASIMHAN (R.). — Compact Riemann Surfaces. — Birkhauser,
1992.
[OdS] ODA (T.), SESHADRI (C.S.). — Compactification of the Generalized
Jacobian Variety, Trans. AMS, t. 253, 1979, p. 1-90.
[0x1] OXLEY (J.G.). — Matroid Theory. — Oxford University Press, 1992.
[Rot] ROTMAN (J.J.). — An Introduction to Algebraic Topology. —
Springer, 1988.
[Sch] SCHARLAU (W.). — Quadratic and Hermitian Forms. — Springer-
Verlag, 1985.
[Ser] SERRE (J.-P.). — Arbres, amalgames, SL^. — Asterique, t. 46, Soc.
Math. France, 1977.
[VLW] VAN LINT (J.H.) and WILSON (P.M.). — A Course in Combinatorics.
— Cambridge University Press, 1992.

TOME 125 — 1997 — ? 2