Annales de l’institut Fourier (AIF)

Wunsch, Jared

The trace of the generalized harmonic oscillator

Suzuki, Masakazu

Affine plane curves with one place at infinity

Berge, Claude

Reed, Bruce

ANNALES DE L’INSTITUT FOURIER
CLAUDE BERGE
BRUCE REED
Edge-disjoint odd cycles in graphs with
small chromatic number
Annales de l’institut Fourier, tome 49, no 3 (1999), p. 783-786
<http://www.numdam.org/item?id=AIF_1999__49_3_783_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), 783-786
EDGE-DISJOINT ODD CYCLES
IN GRAPHS WITH SMALL CHROMATIC NUMBER
by C. BERGE and B. REED
Dedicated to the memory of Francois Jaeger
1. A positional game.
An interesting positional game can be described as follows: two
players, called respectively Red and Blue, play alternately by coloring
with their color an edge in a graph G. The first one who achieves a
monochromatic odd cycle wins and his opponent loses; if no monochromatic
odd cycle is obtained, it is a draw. It would be interesting to know for which
graphs one of the players can win.
A non-constructive proof for the existence of a winning strategy is:
THEOREM 1. — If the players Red and Blue play the game with a
graph G of chromatic number > 4, there exists a winning strategy for the
first player.
Proof. — Assume that Red is the first player and has no winning
strategy with a graph G; we shall show that this leads to a contradiction.
Clearly, for his opponent, no strategy a is winning, because otherwise
Red could win by using the same strategy a (determined for a fictitious
game where Blue starts, his first move being an arbitrary chosen edge),
Keywords: Graph - Games.
Math. classification: 05C - 05.
784 C.BERGE &; B.REED
which is a contradiction. Thus both Red and Blue can guarantee a draw.
At the end of the game, all the edges of G have been colored; the red edges
define a partial graph GR with no odd cycles and the blue edges define
a partial graph GB with no odd cycles. Since the graph Gp, is bipartite,
its vertices can be colored with only two colors, say a and a', so that no
two adjacent vertices have the same color; also, the vertices of GB can
be colored with two colors /3 and ft' so that no two adjacent vertices of
GB have the same color. If we assign to each vertex a label (a,/?), (a,/?'),
(a',/3) or (a',/?'), corresponding to the pair of colors used for this vertex
in GR and in GB, no two adjacent vertices of G have the same label. This
implies that the graph G is 4-colorable. A contradiction.
For 4-colorable graphs, and in particular for planar graphs, no simple
structural property has been found so far to see that the game is unfair.
2. The Konig property.
Given a simple graph G = (X, E), the edge-transversal number Te(G)
is the least number of edges to remove from G in order to destroy all the
odd cycles. The edge-packing number Ve(G) is the maximum number of
paiwise edge-disjoint odd cycles; if G has no odd cycles, we put ^e(G) = 0.
Clearly, we have always Tg(G) >, Ve(G), and if for some graph G
this inequality holds with equality, it is easier to check that some edge-
transversal is minimum (or that some edge-packing is maximum). It would
be interesting to determine the graphs for which the values of these two
coefficients can be obtained in polynomial time (see [2], [9] for some related
results where the words "edge" and "vertex" are interchanged).
When these two coefficients are equal, we say that we have the Konig
property (for the odd cycles).
We do not always have this Konig property, even for planar graphs; for
instance, the complete graph K^ is planar, but Te{K^) = 2 and Ve{K^) = 1.
However we have proved in [3] that for all the planar graphs having a fixed
edge-packing number, their edge-transversal numbers are bounded.
Graphs for which each pair of odd cycles has at least one vertex in
common and yet the number of vertices needed to hit them all is large,
have been considered by Lovasz [7]. Similarly, we have considered in [3] a
family of graphs G for which ^e(G) = 1 and their edge-transversal numbers
can be arbitrarily large.
EDGE-DISJOINT ODD CYCLES 785
We do not know any simple characterization for the graphs whose
odd cycles satisfy the Konig property, but we have:
THEOREM 2. — Let G be a graph such that Te(G?/) = ^e(G') for
every partial graph G' of G. Then its chromatic number is < 4.
Proof. — Catlin [4] proved that every graph with chromatic number
^ 4 contains a subdivision of the complete graph K^ such that each triangle
of K^ is subdivided to form an odd cycle (see [10] and [11]). If the graph G
was not 3-colorable, then a partial graph G' would be a subdivision of K^ of
the type described above. However Te(G') = 2 is different from i^e(G') = 1.
A contradiction.
Similar results can also be obtained by using some basic results of
Hypergraph Theory. Let HG be the hypergraph whose vertices are the
edges of G and whose edges are the elementary odd cycles of G. So, using
usual notations r and v for the two main coefficients of a hypergraph (see
for instance [1]), we can write Tg(G) = r{Hc) and Ve(G) = i/{Hc)'
Every hypergraph H satisfies r(H) > v{H). If r(H) == v(H), the
hypergraph H is said to have the Konig property. A hypergraph H has
the Helly property if every family of pairwise intersecting edges has a
non-empty intersection. For a hypergraph H with the Helly property, the
most usual way to prove that H satisfies the Konig property is to show
that the line-graph (or "intersection graph") L{H) is a perfect graph;
but unfortunately, as we have seen above, the hypergraph HG does not
necessarly satisfy the Helly property.
The property of G described in the statement of Theorem 2 implies
that HG is a normal hypergraph (Lovasz [6]). Fournier and Las Vergnas [5]
have shown that the vertex-set of a normal hypergraph can be split into
two classes, the "red" vertices and the "blue" vertices, so that no edge of
the hypergraph is monochromatic. This shows that this graph G can be
split into two partial graphs which are bipartite. This result is implied by
Theorem 2. However, perhaps this alternative approach, via Hypergraph
Theory, can shed some light on the problem.
786 C.BERGE & B.REED
BIBLIOGRAPHY
[I] C. BERGE, Hypergraphs, Combinatorics of finite sets, North-Holland, Amsterdam,
New York, 1989.
[2] C. BERGE, J.-L. FOUQUET, On the optimal transversals of the odd cycles, Discrete
Math., 169 (1997), 169-176.
[3] C. BERGE, B. REED, Optimal packings of edge disjoint odd cycles, to appear.
[4] P.O. CATLIN, Hajos'Graph Coloring Conjecture, J. of Combinat. Theory, B26
(1979), 268-274.
[5] J.-C. FOURNIER, M. LAS VERGNAS, Une classe d'hypergraphes bichromatiques,
Discrete Math., 2 (1979), 407-410 (see also [I], p. 156).
[6] L. LOVASZ, Normal hypergraphs and the perfect graph conjecture, Discrete Math.,
2 (1972), 253-267.
[7] L. LOVASZ, Private communication.
[8] B. REED, Mango and Blueberries (to appear).
[9] B. REED, Tree widht and tangles, a new measure of connectivity and some
applications, Survey in Combinatorics, R. Bailey editor, London Math. Soc.
Lecture Notes Series 241, Cambridge University Press, Cambridge 1997, 87-162.
[10] C. THOMASSEN, On the presence of disjoint subgraphs of a specified type, J. of
Graph Theory, 12 (1988), 101-111.
[II] B. TOFT, T.R. JENSEN, Graph coloring problems, Wiley Interscience, 1995.
C. BERGE,
C.A.M.S.
54, boulevard Raspail
75270 Paris Cedex 06 (France).
B.REED,
Universite Paris VI
Equipe Combinatoire
4, place Jussieu
75252 Paris Cedex 05 (France).


Edge-disjoint odd cycles in graphs with small chromatic number

Khelladi, Abdelkader

Colorations généralisées, graphes biorientés et deux ou trois choses sur François

Lovász, Lászlo

Schrijver, Alexander

ANNALES DE L’INSTITUT FOURIER
LÁSZLO LOVÁSZ
ALEXANDER SCHRIJVER
On the null space of a Colin de Verdière matrix
Annales de l’institut Fourier, tome 49, no 3 (1999), p. 1017-1026
<http://www.numdam.org/item?id=AIF_1999__49_3_1017_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), 1017-1026
ON THE NULL SPACE
OF A COLIN DE VERDIERE MATRIX
by L. LOVASZ and A. SCHRIJVER
1. Introduction and results.
Let G = (Y^E) be an undirected graph, with vertex set {1, . . . ,n}.
Let M{G) be the set of symmetric n x n matrices M = (rrizj) satisfying
(1) (i) M has exactly one negative eigenvalue, of multiplicity 1;
(ii) for all % , j with i -^- j one has :
if i and j are nonadjacent then rriij = 0,
if i and j are adjacent then rriij < 0.
Moreover, M is said to have the Strong Arnold Property (or to
satisfy the Strong Arnold Hypothesis) if for each symmetric n x n matrix
X = (xij) satisfying Xij == 0 if i == j or i and j are adjacent, and satisfying
MX = 6, one has X = 0.
Yves Colin de Verdiere [1] introduced the parameter /^(G), being
the maximum corank of any matrix in M.(G) having the Strong Arnold
Property. (The corank of a matrix is the dimension of its null space.)
Stimulated by discussions with Francois Jaeger (who suggested an
idea to show (ii) below), Colin de Verdiere showed that l^{H) <^ /^(G) if H
Keywords'. Null space — Colin de Verdiere matrix — Planar graph — Outerplanar graph.
Math. classification: 05C10 - 05C50.
1018 L. LOVASZ & A. SCHRIJVER
is a minor of G, and that
(2) (i) /^(G) < 1 if and only if G is a disjoint union of paths;
(ii) f^(G) < 2 if and only if G is outerplanar;
(iii) y^(G) < 3 if and only if G is planar.
In [5], we showed that
(3) (iv) ^(G) < 4 if and only if G is linklessly embeddable.
(A graph G is linklessly embeddable if it can be embedded in R3 so that
any two disjoint circuits in G form unlinked closed curves in R3.)
It was shown by Hein van der Hoist [3] that if G is 3-connected and
planar, then any matrix in M.{G) has corank at most 3 — also those not
having the Strong Arnold Property.
The main result in this paper is that if G is 3-connected and planar,
then for any matrix M € M.{G) of corank 3, the null space kerM of M
yields an embedding of G in the 2-sphere S2. We also show the related
but easier results that if G is a path, then for any matrix M e M(G)
of corank 1, the null space kerM of M yields an embedding of G in the
line; furthermore, if G is 2-connected and outerplanar, then for any matrix
M e M{G) of corank 2, the null space kerM of M yields a representation
of G as a convex polygon with non-crossing diagonals.
To make this more precise, assume that G is connected. In this
case condition (l)(ii) implies that the eigenvector TT belonging to the
negative eigenvalue is (up to scaling) positive. We define the null space
representation derived from the matrix M as follows. Let r be the corank
of M, let ai, 0 2 , . . . , cir form a basis of kerM, and for each vertex i of G,
let Ui := (ai^, 02,^ ... dr^ C M^. As TT is orthogonal to each of a i , . . . , dr
we have
V^ TViUi = 0.
i
This way we define a mapping V —> W. Note that this mapping is
determined only up to a linear transformation of M7". In the results below,
we have to scale the vectors Ui. Note that arbitrary scaling of them can
be achieved through appropriate scaling of the rows and columns of M. In
particular, we consider the unit vectors
(4) v^=^\\u-
ON THE NULL SPACE OF A COLIN DE VERDIERE MATRIX 1019
and the vectors
(5) Wi=—Ui.
^i
For (4) to make sense, we'll have to show that the ui are non-null.
THEOREM 1.1. — Let G be a path. Then the mapping i i—^ wi,
together with the segments connecting Wz and Wj for i j € E(G), gives an
embedding of G in the line.
THEOREM 1.2. — Let G be a 2-connected outerplanar graph. Then
the mapping i \—f v^, together with the segments connecting Vi and Vj for
i j € E(G), gives an embedding of G in the plane as a convex polygon with
non-crossing diagonals.
THEOREM 1.3. — Let G be a 3-connected planar graph. Then the
mapping i \—> v^, together with the geodesic curves on S2 connecting Vi and
Vj for ij G E(G\ gives an embedding of G in S2.
Remarks. — 1. It seems curious that we had to scale differently in
the case of the path as in the other two cases. It may be the case that for
planar and outerplanar graphs the scaling (wi) provides an embedding with
interesting properties, say in the planar case an embedding in the skeleton
of a convex polyhedron; but we cannot prove this.
2. Our motivation has been to derive a similar result for one dimension
higher, that is, for linklessly embeddable graphs, where we would like to
obtain a linkless embedding of G in S3. Suppose that G is a 4-connected
linklessly embeddable graph and M is a matrix in M{G) of corank 4.
Perhaps kerM yields a proper embedding of G in S3: vertices of G are
embedded in S'3 in such a way that adding shortest arcs in S3 connecting
adjacent vertices, gives a linkless embedding of G in S3. We do not know
if this is true.
1020 L. LOVASZ & A. SCHRIJVER
2. Proofs.
2.1. Van der Hoist's lemma and its extensions.
For any vector x G R71, the support of x, denoted by supp(^), is the
set {z G l^l^i 7^ 0}. The positive support supp"*"^) of x is the set {i C
V|a^ > 0}, and the negative support s\ipp~(x) is the set {% € V\xi < 0}.
For any U C V, N(U) denotes the set of vertices i ^. U adjacent to at least
one vertex in U.
The following observation is useful:
(6) Let M C M(G) and let x € kerM. Then each vertex in ./V(supp(a;))
belongs to both ^(supp"^)) and N (s\ipp~ {x)).
To see (6), consider any i € 7V(supp(.z;)) (so xi =0), and note that
(7) E^A—O,
j
implying that, if Xj > 0 for some j adjacent to z, then xj < 0 for some j
adjacent to %, and conversely. (Here we use that mij < 0 i f j is adjacent to
z, and rriijXj == 0 otherwise.)
An important further tool we need is the following lemma proved by
van der Hoist [2]. A vector x in kerM is said to have minimal support if
x ^ 0, and each nonzero vector y € kerM with supp(2/) C supp(;r) satisfies
supp(2/) = supp(rc).
LEMMA 2.1 [van der Hoist]. — Let G be connected, let M C M(G)
and let x € kerM have minimal support. Then both supp^rc) and
supp~ {x) are nonempty and induce connected subgraphs of G.
Geometrically, this lemma expresses the following nice property of the
null space embedding: every hyperplane in W spanned by some vectors ui
separates the graph into two non-empty connected subgraphs.
We need the following variation on this lemma.
LEMMA 2.2. — Let M C M(G) and let x € R^ satisfy MX < 0.
Then supp"*"^) is nonempty and induces a connected subgraph of G.
One way to get a vector x with MX < 0 is to choose a vector in
the nullspace of M and add a positive multiple of TT to it. In this special
case, Lemma 2.2 has a nice geometric formulation: the nodes i for which
ON THE NULL SPACE OF A COLIN DE VERDIERE MATRIX 1021
Wz belongs to an open halfspace in W containing the origin induce a non-
empty connected subgraph.
We give a proof of a more general lemma, which also includes van der
Hoist's lemma and its extension given in [4]. To formulate this, we need to
describe a class of exceptions. Let G = (V, E) be a graph, M € M(G) and
S C V. Let Gi , . . . ,Gy. (r :> 2) be the connected components of G — 5,
and let Sz = V(Gi). We say that S is a regular cutset (in G, with respect
to M), if there exist non-zero, non-negative vectors x\,..., Xr and y in IR^
such that
(i) supp(;z^) = Si and supp(^) C 5;
(ii) Mx\ = Mx'2 = ... = Mxr = —y'
Note that if Mi and x\ are the restrictions of M and rc^ to 5^, then
^ > 0 and MiXi = 0. Thus by the Perron-Frobenius Theorem, the xi are
uniquely determined up to positive scaling.
LEMMA 2.3. — Let M e M{G) and let x e M1" satisfy MX < 0.
Then supp^o*) is nonempty. Furthermore, ifsupp^(x) induces a discon-
nected graph then G has a regular cutset S such that x is a linear combi-
nation
X = ̂  OiXi
i
of the corresponding vectors a * i , . . . , Xr, where ̂  0.1 >_ 0, and at least two
i
Oi are positive.
Proof. — We may assume that the negative eigenvalue of M is —1.
Then
^x == -T^MX > 0,
and since x -^ 0, it follows that supp^rc) is nonempty.
Suppose next that supp4" x can be decomposed into two disjoint
nonempty sets A and B such that no edge connects A and B. Let
C := supp~(.r) (this may be empty), and S = V \ supp(X). Let a^b and
c arise from x by setting to 0 the entries with index out of A, -B and (7,
respectively. Define
w := (j^b^a — (T^a^b.
Then ^w = 0, and hence by our assumption that M has exactly one
negative eigenvalue with eigenvector TT,
w^^Mw > 0.
1022 L. LOVASZ & A. SCHRIJVER
On the other hand, we have a^Mb == 0 (as there are no edges between A
and B) and a^Mc > 0 (as a >; 0, c <^ 0 and M is non-positive outside the
diagonal). Furthermore, MX < 0 implies that
a^Ma < -a^Mb - c^Mc < 0.
Thus
wTMw = (7^Tb)2aTMa - 2(7^Tb)(7^Ta)aT Mb+ (^T a)2^ Mb < 0.
This implies that w7Mw = 0. Moreover, we must have equality in
a^Mc > 0, which implies that there are no edges between A and C7, and
similarly, between B and (7.
Thus (Ma)i = (Mx)i < 0 for i € A, and so a^Ma = 0 implies that
(Ma)i = (Mx)i = 0 for i e A. Similarly, (M^), == (M.r), = 0 for z € B.
Thus supp(Ma),supp(M6).supp(Mc) C S.
Since M is positive semidefinite on vectors orthogonal to TT, w1Mw =
0 implies Mw = 0. This says that
(8) ^Ma = (A)^-
To conclude, let 6'i, 62, . . . 5'y be the connected components of G — S.
The fact that supp(Mc) C S implies that if z 6 M^ is defined by zi = |a^|,
then Mz <_ 0. Thus we can apply the above argument choosing any two
components Si as A and B. If z^ denotes the restriction of z to 5^, and
Xi = ( l / ^ Zi}zi^ then (8) above implies that Mx\ = ... = Mxr. We
have also seen that this vector has support in S, and since its support is
disjoint from the support of the Xi, it is non-positive. Clearly x is a linear
combination of the Xi, and the conditions on the coefficients are trivially
verified. D
2.2. Proof of Theorem 1.1.
Look at the null space representation (ui) of M € A4(P) with corank
1, where P is a path with n nodes labelled 1,2, . . . , n (in this order on the
path), and the scaled version (wz). Note that the Wi are numbers now. We
claim that either Wi < W2 < ... < Wn or w\ > w^ > .. • > w^' It suffices to
argue that w^_i < wi > 1^4-1 cannot occur. There are 3 cases to consider:
(a) Wi > 0. Then the vector x G R77' defined by xj = (wi — Wj^TTj
satisfies MX < 0, and has Xz = 0, a^-i > 0, and a^-i-i > 0. Let
^ ( X j - £ , i f j = Z + l ,
3 \^j-> otherwise,
ON THE NULL SPACE OF A COLIN DE VERDIERE MATRIX 1023
for a small positive e. Then My < 0, and yi = 0, ^_i,^+i > 0, which
means that supp"^?/) is disconnected, contradicting Lemma 2.3.
(b) Wi = 0. It is trivial from Mu = 0 that if a node i with ui = 0 has
a neighbor j with uj < 0, then it must also have a neighbor k with Uk > 0
(by (6)), which is not satisfied here.
(c) Wi < 0. We know by Lemma 2.1 that there is a node k with
Wk > 0. If i < A;, then let j be the index with i < j < k and Wj minimum;
this j then violates (a) (with signs flipped). If k > %, the argument is
similar. D
2.3. Proof of Theorem 1.2.
As G is outerplanar, we may fix an embedding of G in R2. When
speaking of faces below, we mean faces with respect to this embedding.
Similarly for the outer face. We can assume that the vertices 1,..., n occur
in this order along the outer face.
We first show:
(9) if a and b are consecutive vertices along the outer face, then Ua and
Ub are linearly independent.
Suppose not. Then there exists a nonzero vector x € kerM such that
Xa -= Xb = 0. Take such an x with supp(a;) minimal. Lemma 2.1 implies
that both supp^rc) and supp~(.r) are nonempty and induce connected
subgraphs of G.
As G is 2-connected, G has vertex-disjoint paths P\ and ?2, each
starting in A^(supp(a;)), and ending in a and b respectively. By (6), Pi
starts in a vertex that is both in TV^supp"^)) and N {s\ipp~ {x)). However,
since supp^rr) and supp~(;c) induce connected subgraphs of G, this is
topologically not possible, showing (9).
(9) implies that each u^ is nonzero, and hence Vz is defined. To show
that z ? i , . . . , Vjc occur in this order along 51, it suffices to show that (using
the symmetry of 1,..., k):
(10) let I be the line through v-^ and 0. Then there is a A; such that
z ? 2 , . . . , Vk-i all are at one side of I and z^+i , . . . , Vn are at the other
side of L
1024 L. LOVASZ & A. SCHRIJVER
Suppose this is not true. Let a; be a nonzero vector x € kerM with
x\ = 0. Then there are h,i,j with 2 < h < i < j < n such that x^ > 0,
Xi <, 0, and Xj > 0. Since supp^rc) induces a connected subgraph of G,
there is a path P connecting fa and j and traversing vertices in supp^a;)
only. Then 1 and i are in different components of G — P. Both components
contain vertices m with Xm < 0 (namely 1 and z), and hence vertices
m C TV^supp'^a;)) (using the 2-connectivity of G). Any such vertex belongs
to supp" (x) or is adjacent to a vertex in supp" (x). So both regions intersect
supp~(a;). This contradicts the fact that supp~(a;) induces a connected
subgraph of G, which proves (10). D
2.4. Proof of Theorem 1.3.
As G is planar, we may fix an embedding of G in S2. When speaking
of faces below, we mean faces with respect to this embedding.
We first show:
(11) if a ,&,c are distinct vertices on a face of G, then Ua, u^ and Uc are
linearly independent.
Suppose not. Then there exists a nonzero vector x G kerM such
that Xa = Xb = Xc = 0. Take such an x with supp(o-) minimal. Lemma
2.1 implies that both supp^a;) and supp~(a;) are nonempty and induce
connected subgraphs of G.
As G is 3-connected, G has pairwise vertex-disjoint paths Pi, ?2, PS,
each starting in -/V(supp(rr)) and ending in a, b and c respectively. By (6),
the Pi start in a vertex that are both in ^(supp^a;)) and N {s\ipp~ (x)). As
supp^rc) and supp~(a;) induce connected subgraphs of G, we can contract
each of supp'^a;), supp~(a;), Pi, ?2, and ?3 to one vertex, so as to obtain
a J<2,3 with the three vertices of degree 2 on one common face, which is
not possible. This shows (11).
This implies that each Ui is nonzero, and hence Vi is defined. It also
implies that Vi and Vj are linearly independent if i and j are adjacent.
So for adjacent vertices i and j there exists a unique shortest geodesic on
S'2 connecting Vi and vj. This gives an extension of i —> u^ to a mapping
'0 : G —> 5'2. We will show that this is in fact an embedding.
To this end we show:
ON THE NULL SPACE OF A COLIN DE VERDIERE MATRIX 1025
(12) Let (say) 1,. . . , k be the vertices around a face F of G, in this cyclic
order. Then ^i, . . . ,^ are the extremal rays of the convex cone C
they generate in R3, in this cyclic order.
Consider two consecutive vertices along F, say 1 and 2. Let H be
the plane spanned by ni, u^ and 0. It suffices to prove that ^3, . . . , uj, are
all at the same side of H. Let a; be a nonzero vector in kerM satisfying
xi = x^ == 0 {x is unique up to scalar multiplication, as u^ and u^
are linearly independent.) By (11), 3, . . . . A: belong to supp(a:), and hence
none of u^... ,Uk are on H. Suppose that they are not all at the same
side of H. That is, both supp^a;) and supp-(a:) intersect {3 , . . . . k}. As
G is 3-connected, there exist vertex-disjoint paths Pi and P^ starting
in 7v(supp(a;)) and ending in 1 and 2 respectively. Contracting each of
supp+(;r), supp-Qr), Pi, and ?2 to one vertex, we obtain a K^ embedded
in S2 with all four vertices on one face, which is not possible. This shows
(12).
Next:
(13) Let a € V, and let (say) 1,.... A; be the vertices adjacent to a, in this
cyclic order. Then the geodesies on S2 connecting Va to ^ i , . . . .vj,
issue from Va in this cyclic order.
Consider a nonzero vector x e kerM with Xa = x^ = 0. We claim
(14) there are no h,ij with 2 <h<i <j <k such that XH > 0, Xi ^ 0,
and Xj > 0.
Suppose that such ij and h do exist. Since supp-^) induces a
connected subgraph of G, there is a path P connecting h and j and
traversing vertices in supp-^a:) only. Together with a this gives a circuit C,
dividing S2 into two (open) regions. Both regions contain vertices m with
Xm ^ 0 (namely 1 and %), and hence vertices m G 7V(supp+(a;)) (using the
3-connectivity of G). Any such vertex belongs to supp-(a;) or is adjacent to
a vertex in supp-(a;). So both regions intersect supp-(:r). This contradicts
the fact that supp-(a;) induces a connected subgraph of G. This proves
(14).
This implies that v-z and Vk are on different sides of the plane H
through Va, vi, and 0. Otherwise we can assume that x^ > 0 and xj, > 0.
As a € 7V(supp(:r)), we know that a 6 7v(supp-(^)). So x, < 0 for some
i with 2 < i < k. This contradicts (14). Moreover, (14) implies that the
nodes i with Xi > 0 occur contiguously, and also the i with xi < 0 occur
contiguously. This implies (13) (using the symmetry of the 1,.... k).
1026 L. LOVASZ &; A. SCHRIJVER
Now it is easy to complete the proof. (12) and (13) imply that we can
extend the mapping ^ : G —» S2 to a mapping ^ : S2 —> S2 such that '0
is locally one-to-one. We show that ^ is one-to-one. To see this, note that
there is a number k such that [^^(p)] = k for each p e S2. Now let H
be any 3-connected planar graph embedded in 52, with v vertices, e edges,
and / faces. Then ̂ ^(H) is a graph embedded in 52, with kv vertices, ke
edges, and kf faces. Hence by Euler's formula, 2k = kv — ke + kf = 2, and
so k == 1. Therefore, ^ is one-to-one, and ^ embeds |G| in 5'2. D
BIBLIOGRAPHY
[1] Y. COLIN de VERDIERE, Sur un nouvel invariant des graphes et un critere de
planarite, Journal of Combinatorial Theory, Series B, 50 (1990), 11-21 [English
translation: On a new graph invariant and a criterion for planarity, in: Graph
Structure Theory (N. Robertson, P. Seymour, eds.), Contemporary Mathematics,
American Mathematical Society, Providence, Rhode Island, 1993, 137-147].
[2] H. van der HOLST, A short proof of the planarity characterization of Colin de
Verdiere, Journal of Combinatorial Theory, Series B, 65 (1995), 269-272.
[3] H. van der HOLST, Topological and Spectral Graph Characterizations, Ph.D.
Thesis, University of Amsterdam, Amsterdam, 1996.
[4] H. van der HOLST, L. LOVASZ, A. SCHRIJVER, On the invariance of Colin de
Verdiere's graph parameter under clique sums, Linear Algebra and its Applica-
tions, 226 (1995), 509-517.
[5] L. LOVASZ, A. SCHRIJVER, A Borsuk theorem for antipodal links and a spectral
characterization of linklessly embeddable graphs, Proceedings of the American
Mathematical Society, 126 (1998), 1275-1285.
L. LOVASZ,
Department of Computer Science
Yale University
New Haven CT 06520 (USA).
A. SCHRIJVER,
CWI
Kruislaan 413
1098 SJ Amsterdam (The Netherlands).
&
University of Amsterdam
Department of Mathematics
Plantage Muidergracht 24
1018 TV Amsterdam (The Netherlands).


On the null space of a Colin de Verdière matrix

Noble, Steven D.

Welsh, Dominic J. A.

A weighted graph polynomial from chromatic invariants of knots

Baldoni, Welleda

Frajria, Pierluigi Möseneder

The Harish-Chandra homomorphism for a quantized classical hermitian symmetric pair

Neeb, Karl-Hermann

On the complex geometry of invariant domains in complexified symmetric spaces

Even, Christian

Étude d'une fonction remarquable associée aux moyennes de convolution

Las Vergnas, Michel

The Tutte polynomial of a morphism of matroids I. Set-pointed matroids and matroid perspectives

Not a member yet