 322 pág.

Graph Theory

DisciplinaTeoria dos Grafos342 materiais1.556 seguidores
Pré-visualização50 páginas
with G1 and G2.)
For \u2022(G) 6 1, things become even simpler. However, the geometric
operations involved require some cumbersome shifting and scaling, even
if all the plane edges occurring are assumed to be straight.
4.4 Planar graphs: Kuratowski\u2019s theorem 83
The following more combinatorial route is just as easy, and may be
a welcome alternative.
Lemma 4.4.4. Let X be a set of 3-connected graphs. Let G be a graph [ 8.3.1 ]
with \u2022(G) 6 2, and let G1; G2 be proper induced subgraphs of G such
that G = G1 [G2 and jG1 \G2j = \u2022(G). If G is edge-maximal without
a topological minor in X , then so are G1 and G2, and G1 \G2 = K2.
Proof . Note flrst that every vertex v 2 S := V (G1 \G2) has a neigh- S
bour in every component of Gi ¡ S, i = 1; 2: otherwise S r f v g would
separate G, contradicting jSj = \u2022(G). By the maximality of G, every
edge e added to G lies in a TX µ G + e with X 2 X . For all the X
choices of e considered below, the 3-connectedness of X will imply that
the branch vertices of this TX all lie in the same Gi, say in G1. (The
position of e will always be symmetrical with respect to G1 and G2, so
this assumption entails no loss of generality.) Then the TX meets G2 at
most in a path P corresponding to an edge of X. P
If S = ;, we obtain an immediate contradiction by choosing e with
one end in G1 and the other in G2. If S = f v g is a singleton, let e
join a neighbour v1 of v in G1 ¡ S to a neighbour v2 of v in G2 ¡ S
(Fig. 4.4.3). Then P contains both v and the edge v1v2; replacing vPv1
with the edge vv1, we obtain a TX in G1 µ G, a contradiction.
G1 G2
TX
Pe
v
v1 v2
Fig. 4.4.3. If G+ e contains a TX, then so does G1 or G2
So jSj = 2, say S = fx; y g. If xy =2 G, we let e := xy, and in the x; y
arising TX replace e by an x{y path through G2; this gives a TX in G,
a contradiction. Hence xy 2 G, and G [S ] = K2 as claimed.
It remains to show that G1 and G2 are edge-maximal without a
topological minor in X . So let e0 be an additional edge for G1, say.
Replacing xPy with the edge xy if necessary, we obtain a TX either
in G1 + e0 (which shows the edge-maximality of G1, as desired) or in G2
(which contradicts G2 µ G). \u2044
Lemma 4.4.5. If jGj > 4 and G is edge-maximal with TK5; TK3;3 6µ G,
then G is 3-connected.
84 4. Planar Graphs
Proof . We apply induction on jGj. For jGj = 4, we have G = K4(4.2.9)
and the assertion holds. Now let jGj > 4, and let G be edge-maximal
without a TK5 or TK3;3. Suppose \u2022(G) 6 2, and choose G1 and G2 asG1; G2
in Lemma 4.4.4. For X := fK5;K3;3 g, the lemma says that G1 \G2 is
a K2, with vertices x; y say. By Lemmas 4.4.4, 4.4.3 and the inductionx; y
hypothesis, G1 and G2 are planar. For each i = 1; 2 separately, choose a
drawing of Gi, a face fi with the edge xy on its boundary, and a vertexfi
zi 6= x; y on the boundary of fi. Let K be a TK5 or TK3;3 in thezi
abstract graph G+ z1z2 (Fig. 4.4.4).K
G1 G2
z1 z2x
y
K
Fig. 4.4.4. A TK5 or TK3;3 in G+ z1z2
If all the branch vertices of K lie in the same Gi, then either Gi+xzi
or Gi + yzi (or Gi itself, if zi is already adjacent to x or y, respectively)
contains a TK5 or TK3;3; this contradicts Corollary 4.2.9, since these
graphs are planar by the choice of zi. SinceG+z1z2 does not contain four
independent paths between (G1 ¡G2) and (G2 ¡G1), these subgraphs
cannot both contain a branch vertex of a TK5, and cannot both contain
two branch vertices of a TK3;3. Hence K is a TK3;3 with only one branch
vertex v in, say, G2¡G1. But then also the graph G1 +v+f vx; vy; vz1 g,
which is planar by the choice of z1, contains a TK3;3. This contradicts
Corollary 4.2.9. \u2044
Theorem 4.4.6. (Kuratowski 1930; Wagner 1937)
The following assertions are equivalent for graphs G:
[ 4.5.1 ]
[ 12.4.3 ]
(i) G is planar;
(ii) G contains neither K5 nor K3;3 as a minor;
(iii) G contains neither K5 nor K3;3 as a topological minor.
Proof . Combine Corollary 4.2.9 and Proposition 4.4.2 with Lemmas(4.2.9)
4.4.3 and 4.4.5. \u2044
Corollary 4.4.7. Every maximal planar graph with at least four ver-
tices is 3-connected.
Proof . Apply Lemma 4.4.5 and Theorem 4.4.6. \u2044
4.5. Algebraic planarity criteria 85
4.5 Algebraic planarity criteria
In this section we show that planarity can be characterized in purely
algebraic terms, by a certain abstract property of its cycle space. Theo-
rems relating such seemingly distant graph properties are rare, and their
signiflcance extends beyond their immediate applicability. In a sense,
they indicate that both ways of viewing a graph|in our case, the topo-
logical and the algebraic way|are not just formal curiosities: if both are
natural enough that, quite unexpectedly, each can be expressed in terms
of the other, the indications are that they have the power to reveal some
genuine insights into the structure of graphs and are worth pursuing.
Let G = (V;E) be a graph. We call a subset F of its edge space
E(G) simple if every edge of G lies in at most two sets of F . For example, simple
the cut space C\u2044(G) has a simple basis: according to Proposition 1.9.3 it
is generated by the cuts E(v) formed by all the edges at a given vertex v,
and an edge xy 2 G lies in E(v) only for v = x and for v = y.
Theorem 4.5.1. (MacLane 1937)
A graph is planar if and only if its cycle space has a simple basis. [ 4.6.3 ]
Proof . The assertion being trivial for graphs of order at most 2, we
(1.9.2)
(1.9.6)
(4.1.1)
(4.2.1)
(4.2.5)
(4.4.6)
consider a graph G of order at least 3. If \u2022(G) 6 1, then G is the union
of two proper induced subgraphs G1; G2 with jG1 \G2j 6 1. Then C(G)
is the direct sum of C(G1) and C(G2), and hence has a simple basis if
and only if both C(G1) and C(G2) do (proof?). Moreover, G is planar if
and only if both G1 and G2 are: this follows at once from Kuratowski\u2019s
theorem, but also from easy geometrical considerations. The assertion
for G thus follows inductively from those for G1 and G2. For the rest of
the proof, we now assume that G is 2-connected.
We flrst assume that G is planar and choose a drawing. By Lemma
4.2.5, the face boundaries of G are cycles, so they are elements of C(G).
We shall show that the face boundaries generate all the cycles in G; then
C(G) has a simple basis by Lemma 4.2.1. Let C µ G be any cycle, and
let f be its inner face. By Lemma 4.2.1, every edge e with \u201de µ f lies on
exactly two face boundaries G [ f 0 ] with f 0 µ f , and every edge of C lies
on exactly one such face boundary. Hence the sum in C(G) of all those
face boundaries is exactly C.
Conversely, let fC1; : : : ; Ck g be a simple basis of C(G). Then, for
every edge e 2 G, also C(G ¡ e) has a simple basis. Indeed, if e lies
in just one of the sets Ci, say in C1, then fC2; : : : ; Ck g is a simple
basis of C(G ¡ e); if e lies in two of the Ci, say in C1 and C2, then
fC1 + C2; C3; : : : ; Ck g is such a basis. (Note that the two bases are
indeed subsets of C(G¡ e) by Proposition 1.9.2.) Thus every subgraph
of G has a cycle space with a simple basis. For our proof that G is planar,
it thus su\u2013ces to show that the cycle spaces of K5 and K3;3 (and hence
86 4. Planar Graphs
those of their subdivisions) do not have a simple basis: then G cannot
contain a TK5 or TK3;3, and so is planar by Kuratowski\u2019s theorem.
Let us consider K5 flrst. By Theorem 1.9.6, dim C(K5) = 6; let
B = fC1; : : : ; C6 g be a simple basis, and put C0 := C1 + : : :+C6. As
B is linearly independent, none of the sets C0; : : : ; C6 is empty, and so
each of them contains at least three edges (cf. Proposition 1.9.2). The
simplicity of B therefore implies
18 = 6 ¢ 3 6 jC1j+ : : :+ jC6j
6 2 kK5k¡ jC0j
6 2 ¢ 10¡ 3 = 17 ;
a contradiction; for the middle inequality note that every edge in C0 lies
in just one of the sets C1; : : : ; C6.
ForK3;3, Theorem 1.9.6 gives dim C(K3;3) = 4; let B = fC1; : : : ; C4 g
be a simple basis, and put C0 := C1 + : : :+C4. Since