The Four-color Problem: Assaults and Conquest |
From inside the book
Results 1-3 of 12
Page 17
... Euler's condition is easy to derive and happens to serve our needs . Before proving Euler's formula , however , we shall need to develop two other concepts : trees and bridges . A tree is a connected graph with no circuits ( see Fig . 1 ...
... Euler's condition is easy to derive and happens to serve our needs . Before proving Euler's formula , however , we shall need to develop two other concepts : trees and bridges . A tree is a connected graph with no circuits ( see Fig . 1 ...
Page 18
... Euler's formula . Theorem 1-4 Let M be a map whose underlying graph G has n vertices and m edges and suppose that M has r regions . Then nm + r = 2 . = PROOF Use induction on m . If m O , the formula holds since then n = 1 and r = 1 ...
... Euler's formula . Theorem 1-4 Let M be a map whose underlying graph G has n vertices and m edges and suppose that M has r regions . Then nm + r = 2 . = PROOF Use induction on m . If m O , the formula holds since then n = 1 and r = 1 ...
Page 43
... formula e ( S ) 22k - j = where k > 0 is the number of handles and j = 0 , 1 , or 2 is the number of crosscaps . Thus , e ( So ) 2 , e ( U1 ) = 1 , and e ( S1 ) = 0 = e ( S1 ) . = We can now state Euler's formula for an arbitrary ...
... formula e ( S ) 22k - j = where k > 0 is the number of handles and j = 0 , 1 , or 2 is the number of crosscaps . Thus , e ( So ) 2 , e ( U1 ) = 1 , and e ( S1 ) = 0 = e ( S1 ) . = We can now state Euler's formula for an arbitrary ...
Contents
Historical Setting | 3 |
Problems and Methods | 21 |
Solution of the FourColor Problem | 52 |
Copyright | |
7 other sections not shown
Other editions - View all
The Four-color Problem: Assaults and Conquest Thomas L. Saaty,Paul C. Kainen No preview available - 1986 |
Common terms and phrases
adjacent algorithm Applications argument assigned assume bound boundary bridgeless C₁ called chain charge choose circuit colors Combinatorial complete components configurations Conjecture connected consider consists constructed contains contraction Corollary corresponding cubic define denote determined directed discharging distinct dual easy edges elements embedded endpoints equivalent exactly example exist extend fact Figure finite five four four-coloring give given graph G Graph Theory hamiltonian Hence holds implies induced integer joined Kempe least Lemma length Let G Math Mathematics minimal neighbors Note obtained pair partition planar graph plane points polynomial possible problem produce proof properties prove reducible regions removing respectively result reverse separating shown simple solution subgraph subset Suppose surface Theorem three-colored tree triangulation Tutte University v₁ values vertex vertices Whitney York