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


發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s