3 平面的グラフ (Planar graphs)

(1)

グラフ理論特論 (Graph Theory) No. 4

担当：松田晴英

(Haruhide Matsuda)

3 平面的グラフ (Planar graphs)

地図において，境界線で隣接する異なる国や都道府県を異なる色で塗り分けたいとします。このとき，最低限何色あれば，どんな地図でも塗り分けることができるでしょうか。この問題は四色問題といい，グラフ理論において，とてもとても有名な問題です。ここでは，これを扱うための準備をします。

On any maps with several regions (countries, cities, and so on), we may ask how many colors are needed to color them so that no two regions with a common boundary line share the same color. This is closely related to famous problem, which is so-called “the four-color theorem.” In this lesson, we learn some topics for it.

3.1

平面的グラフ

(Planar graphs)

定義

1.

平面的グラフ

(planar graph)

とは

,

平面上にグラフの点と辺を

,

どの辺もその端点以外では交差しないように描くことのできるグラフのことである。また

,

平面的でないグラフのことを非平面的グラフ

(non-planar graph)

という。実際に

,

平面的グラフを平面上にどの辺も交差しないように描いたグラフを平面グラフ

(plane graph)

^という。

Definition 1. A planar graph is a graph that CAN BE drawn in the plane without crossings, that is, so that no two edges intersect geometrically except at a vertex with which both are incident. A non-planar graph is a graph which is not planar. A plane graph is a graph that IS drawn in the plane without crossings.

例

1.

^例えば

,

^{次のグラフ}

K

4は平面的グラフであり

, 2

^番目と

3

番目のグラフは平面グラフである。

Example 1. For example, the following figure shows three drawings of the planar graph K

₄

, but only the second and third drawings are plane graphs.

問題

1.

次の各グラフ

G

_iが平面的グラフなら，それを平面グラフとして描け。平面的グラフでないなら，

その理由を考えよ。

Quiz 1. Draw a plane graph if each graph G

_i

is a planar graph; otherwise consider the reason why it is not a planar one.

1

(2)

上の図において，一番右のグラフはすべての辺が直線分で描かれたグラフである。ループや多重辺を直線分で描くことはできないが，

1936

年に

Wagner

，

1948

年に

Fary

が独立に次のことを証明している。

すべての単純平面的グラフは直線分で描くことができる。

The right-hand drawing in the above figures leads us to ask whether every planar graph can be drawn in the plane so that each edge is represented by a straight line. Although loops or multiple edges cannot be drawn as straight lines, it was proved independently by K. Wagner in 1936 and I. Fary in 1948 that:

Every simple planar graph can be drawn with straight lines.

定義

2.

^{平面グラフ}

G

^は

, G

を描いた平面をいくつかの領域に分割する。これらの領域を面という。

Definition 2. Any plane graph G divides the plane G is drawn into some regions. Each region is called a face.

例えば

,

次の平面グラフには

, 5

つの面

f

₁

, f

₂

, . . . , f

₅がある。特に，

f

₅は非有界な面であり，このような面を無限面という。

For example, a graph in the following figure has five faces f

1

, f

2

, . . . , f

5

. In particular, the face f

5

is unbounded. Such a face is called a infinite face.

問題

2.

次のグラフにおいて，点の個数

n

，辺の個数

m

，面の個数

f

をそれぞれ求めよ。

Quiz 2. Calculate the number of vertices n, edges m, and faces f for the following graphs.

次に，オイラーの公式を扱う。これは，点の個数

n

，辺の個数

m

，面の個数

f

に関する公式である。

We now state the Euler’s formula that tells us that whatever a plane graph we take, the relationship the number of vertices n, edges m, and faces f is always the same and given by a simple formula.

定理

1.

平面グラフにおいて，点の個数を

n,

辺の個数を

m,

面の個数を

f

とすると

,

次式が成り立つ。

n

−

m + f = 2

Theorem 1. The following equation holds for a planar graph with the number of vertices n, edges m, and faces f .

n

−

m + f = 2.

2

(3)

問題

3.

つの正多面体に対応するグラフに対して，オイラーの公式が成り立つことを確かめよ。

Quiz 3. Verify Euler’s formula for five graphs corresponding to regular polyhedrons.

平面的グラフ

G

において

, G

のどの隣接していない

2

点を結んでも非平面的になるグラフ

G

のことを極大平面的グラフという。また

,

この極大平面的グラフは各面がすべて三角形になることから，極大平面的グラフは三角化グラフともいう。例えば

,

^{次のグラフ}

G

は極大平面的グラフであるが，

H

^{は極大平面的グラフ} でない。

A planar graph G is said to be maximal if joining any two nonadjacent vertices in G results in a non- planar graph. Since all faces of a maximal planar graph are surrounded by three edges, a maximal planar graph is also called a triangulated planar graph. For example, the following graph G is a maxinal planar one, but the graph H is not maximal.

グラフ

G

を単純平面的グラフとするとき，次が成り立つ。

We now restrict ourselves to simple planar graphs. Then we obtain the following theorem.

定理

2. (i)

連結単純平面的グラフが

n(

≥

3)

^個の点と

m

個の辺があるとき，次が成り立つ。

m

≤

3n

−

6 (ii)

極大平面的グラフにおいて

,

次の式が成り立つ。

m = 3n

−

6 (iii)

連結単純平面的グラフが三角形を含まないとき，次の式が成り立つ。

m

≤

2n

−

4 Theorem 2. (i) A connected simple planar graph with n(≥ 3) vertices and m edges satisfies:

m

≤

3n

−

6 (ii) If a connected simple planar graph with n(

≥

3) vertices and m edges is maximal, then m = 3n

−

6 (iii) If, in addition, G has no triangle, then

m

≤

2n

−

4

証明

(i)

連結単純平面的グラフのどの面も，少なくとも，

3

つの辺に囲まれているので，連結単純平面的グラフにおいて，各面を囲む辺の個数を数えると，その合計は少なくとも，

3f

である。一方で，各面を囲む辺の個数を数えると，各辺は

2

回ずつ数えられるので，その合計は

2m

^{である。よって，}

3f

≤

2m

^が成り立つ。これを定理

1

^の

n

−

m + f = 2

^{に代入して，}

f

^{を消去すれば，}

m

≤

3n

−

6

^{が得られる。}

(ii)

^{極大平面的グラフ}

G

の各面は三角形であるから，

(i)

の証明において，等号が成り立つ。

3

(4)

(iii)

連結単純平面的グラフ

G

が三角形を含まないとき，

G

の各面は，少なくとも，

4

個の辺に囲まれる。したがって，各面を囲む辺の個数を数えると，その合計は少なくとも，

4f

である。一方で，各面を囲む辺の個数を数えると，各辺は

2

回ずつ数えられるので，その合計は

2m

^{である。よって，}

4f

≤

2m

^{が成り立つ。}

(i)

^{と同様に，これを定理}

1

^の

n

−

m + f = 2

^{に代入して，}

f

^{を消去すれば，}

m

≤

2n

−

4

^{が得られる。}

Proof. (i) Since each face is bounded by at least three edges, it follows on count up the edges around each face that 3f

≤

2m; the factor 2 appears since each bounds two faces (or the same face twice) and is therefore counted twice. We obtain the required result by combining this inequality with Euler’s formula.

(ii) Deduce as (i). Delete “at least” and replace 3f

≤

2m by 3f = 2m in the proof of (i).

(iii) This part follows in a similar way to (i), except the above inequality 3f

≤

2m is replaced by 4f

≤

2m.

この定理からすぐに導かれる重要な結果がある。

Above theorem leads us to the next important result.

定理

3. K

₅も

K

_3,3も平面的でない。

Theorem 3. Neither K

₅

and K

_3,3

are planar.

問題

4.

上の定理を証明せよ。

Quiz 4. Prove the above theorem.

四色問題では，次の定理が重要となる。

The next result plays an important role on the four-color theorem.

定理

4.

どの単純平面的グラフにも次数

5

以下の点がある。

Theorem 4. Every simple planar graph G contains a vertex of degree at most five.

証明

G

^が

2

点以下のグラフならば，この定理は明らかに成り立つので，

G

^は

3

点以上の連結グラフとする。

もし，

G

の各点の次数が

6

以上なら，

G

の次数和は少なくとも，

6n

である。一方，補題

1

より，

G

の次数和は

2m

である。よって，

6n

≤

2m

，すなわち，

3n

≤

m

が成り立つ。これを，定理

2(i)

の不等式に代入すると，

3n

≤

3n

−

6

を得る。これは矛盾であるから，どの単純平面的グラフにも次数

5

以下の点がある。

Proof. Without loss of generality, we can assume that G is connected and has at least three vertices. If each vertex has at least six, then we have 6n

≤

2m, i.e., 3n

≤

m. It follows immediately from Euler’s formula that 3n

≤

3n

−