## 2012年11月1日 星期四

### [離散] Planar Graph and Coloring Theorem

Problem 1: Show that the graph is not planar, and find a subgraph homeomorphic to K3,3.

NOTE 1 : Although there is no  Δ (Triangle), we should not only check e  ≤ 2 v - 4, but also check e ≤ [ k / (k-2) ] * (v - 2).

Proof :
|V| = 10, |E| = 13
No Δ, 13 ≤ 2*10 - 4 = 16 OK
Exist cycle, ≥ 6, 13  (6 / 6-2) * (10 - 2) = 12
Hence, G is not planar.

NOTE 2 : To be homeomorphic to K3,3, select 3 vertices put at ceiling, select another 3 vertices put at floor.
The selecting key is that the other (n-6) vertices are laid on the midst of the 6 vertices, such that satisfies being homeomorphic to K3,3 (doing elementary subdivisions). [vertices which deg(v) = 2 be the midst]

Redrawing :
V1 = {e, c, i}, V2 = {b, h, f}, elementary edges = {a, g, d, j}

-----------------------------------------------------------------------------------------------------------------------
Problem 2 : Prove that if a simple graph G has 11 or more vertices, then either G or its complement Gc is not planar.

Proof :
If G is planar, e ≤ 3 * 11 - 6 = 27, so 27 is the maximum number of G's edges.
The maximum edges of 11 vertices is C(11,2) = 55.
So Gc has 55 - 27 = 28 (Gc's minimum edges) > 27 => e > 3 v -6
Hence, Gc is not planar, vice versa.

-----------------------------------------------------------------------------------------------------------------------
Problem 3 : Let G = (V, E) be a loop-free undirected graph where Δ = max v∈V {deg(v)}.
Prove that X(G) ≤ Δ + 1

Proof :
Since greatest case to the degree of each v in G occurs when G is complete graph Kn, that is any deg(v) = n -1.
Since any 2 vertices have connected with an edge, if arbitrarily choose a vertex v and color it with a color, then all the other n - 1 vertices connecting to v are also connecting pairwise. So that each of them are colored with various colors.
Then the chromatic number of G is X(G) =  n = (n-1) + 1(the chosen vertex v) = Δ + 1.
Recall that this is the greatest case, so X(G) ≤ Δ + 1.