[離散] 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, K ≥ 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.