《图论GraphTheorych6章节》由会员分享，可在线阅读，更多相关《图论GraphTheorych6章节（46页珍藏版）》请在金锄头文库上搜索。
1、1,Chapter 6 Planar Graphs ,2,6.1. Definition. A graph is planar if it has a drawing without crossings. Such a drawing is a planar embedding of G. A plane graph is a particular planar embedding of a planar graph.,3,4,5,6.1.7. Definition. The dual graph G* of a plane graph G is a plane graph whose ver
2、tices correspond to the faces of G. The edges of G* correspond to the edges of G as follows: if e is an edge of G with face X on one size and face Y on the other side, then the endpoints of the dual edge e* E(G*) are the vertices x, y of G* that represent the faces X, Y of G. The order in the plane
3、of the edges incident to x V(G*) is the order of the edges bounding the face X of G in a walk around its boundary.,6,6.1.11. Definition. The length of a face in a plane graph G is the total length of the closed walk(s) in G bounding the face. 6.1.12. Example. A cut-edge belongs to the boundary of on
4、ly one face, and it contributes twice to its length. Each graph in Example 6.1.10 has three faces. In the embedding on the left the lengths are 3, 6, 7; on the right they are 3, 4, 9. The sum of the lengths is 16 in each case, which is twice the number of edges.,7,6.1.13. Proposition. If t(Fi) denot
5、es the length of face Fi in a plane graph G, then 2e(G) = t(Fi).,8,6.1.14. Theorem. Edges in a plane graph G form a cycle in G if and only if the corresponding dual edges form a bond in G*.,9,6.1.16. Theorem. The following are equivalent for a plane graph G. A) G is bipartite. B) Every face of G has
6、 even length. C) The dual graph G* is Eulerian.,10,6.1.17. Definition. A graph is outerplanar if it has an embedding with every vertex on the boundary of the unbounded face. An outerplane graph is such an embedding of an outerplanar graph. ,11,The graph in Example 6.1.10 is outerplanar, but another
7、embedding is needed to demonstrate this. ,12,6.1.18. Proposition. The boundary of the outer face a 2-connected outerplane graph is a spanning cycle. Proof: This boundary contains all the vertices. If it is not a cycle, then it passes through some vertex more than once. Such a vertex would be a cut-v
8、ertex.,13,6.1.19. Proposition. K4 and K2.3 are planar but not outerplanar.,6.1.20. Proposition. Every simple outerplanar graph has a vertex of degree at most 2.,14,6.1.21. Theorem. (Euler 1758): If a connected plane graph G has exactly n vertices, e edges, and f faces, then n - e + f = 2. Proof: We
9、use induction on n. Basis step (n = 1): G is a “bouquet“ of loops, each a closed curve in the embedding. If e = 0, then I = 1, and the formula holds. Each added loop passes through a face and cuts it into two faces (by the Jordan Curve Theorem). This augments the edge count and the face count each b
10、y 1. Thus the formula holds when n = 1 for any number of edges.,15,Induction step (n 1): Since G is connected, we can find an edge that is not a loop. When we contract such an edge, we obtain a plane graph G with n vertices, e edges, and f faces. The contraction does not change the number of faces (
11、we merely shortened boundaries), but it reduces the number of edges and vertices by 1, so n = n - 1, e = e - 1, and f = f. Applying the induction hypothesis yields n - e + f = n + 1 - (e + 1) + f = n - e + f = 2. ,16,6.1.22. Remark. 1) By Eulers Formula, all planar embeddings of a connected graph G
12、have the same number of faces. Although the dual may depend on the embedding chosen for G, the number of vertices in the dual does not. 2) Eulers Formula as stated fails for disconnected graphs. If a plane graph G has k com ponen ts, then adding k -1 edges to G yields a connected plane graph without
13、 changing the number of faces. Hence Eulers Formula generalizes for plane graphs with k components as n - e + f = k + 1 (for example, consider a graph with n vertices and no edges).,17,6.1.23. Theorem. If G is a simple planar graph with at least three vertices, then e(G) 3n(G) - 6. If also G is tria
14、ngle-free, then e(G) 2n(G) - 4. Proof: It suffices to consider connected graphs; otherwise we could add edges. Eulers Formula will relate n(G) and e(G) if we can dispose of f. Proposition 6.1.13 provides an inequality between e and f. Every face boundary in a simple graph contains at least three edg
15、es (if n(G) 3). Letting fi be the list of face lengths, this yields 2e =fi 3f. Substituting into n - e + f = 2 yields e 3n - 6. When G is triangle-free, the faces have length at least 4. In this case 2e = fi 4f, and we obtain e 2n - 4.,18,6.1.24. Example. Nonplanarity of K5 and K3,3 follows immediat
16、ely from Theorem 6.1.23. For K5, we have e = 10 9 = 3n - 6. Since K3,3 is triangle-free, we have e = 9 8 = 2n - 4. These graphs have too many edges to be planar. 6.1.25. Definition. A maximal planar graph is a simple planar graph that is not a spanning subgraph of another planar graph. A triangulation is a simple plane graph where every face boundary is a 3-cycle.,19,6.1.26. Proposition. For a simple n-vertex plane graph G, the
