Four Color Theorem Assignment Report

SOLUTION 1
We proof by contradiction as follows
According to Four Color Theorem, every planar graph is four-colorable
and it satisfies the inequality 1≤ n ≤ 4 where n is vertices (Calude,
2010).
Given that G (E, V) is a planar graph and a(G) is the size of the largest
independent set in G.
Edges m=2n-2
The sum of vertex degrees is 2m=4n-4 where n=1
4 ≥∑
f E G
facedeg (f ) ≥∑
f E G
(2 N−2) =|v|
4 ≥∑
f E G
facedeg (f ) ≥∑
f E G
( 2−2 )=¿V ∨¿ ¿
Since it has 3 degrees;
4 ∑
f E G
facedeg (f )≥∑
f E G
(4 n−4 ¿) ¿=|V|
4a(G) ≥|V|
a(G) ≥ 1
4 |V|
SOLUTION 2
Given that G (V, E)
Where G is our connected planar graph with minimum degree 3, then
∑
V E G
deg ( v) ≥ ∑
V E G
6= 6 v
4 ∑
V E G
deg ( v) ≥ ∑
V E G
6= 6 v