Mathematics Course: Planar Graph Analysis Assignment Solution

This document presents a solution to a planar graph assignment, exploring concepts such as the Four Color Theorem and Euler's Formula. The solution is structured with two distinct approaches. The first solution leverages the Four Color Theorem and related inequalities to analyze the properties of a planar graph. The second solution utilizes Euler's Formula and investigates the relationships between vertices, edges, and faces in a connected planar graph with a minimum degree of 3. References include relevant research papers. The assignment showcases the application of fundamental graph theory principles to analyze and solve problems related to planar graphs. The solution helps students understand and apply these concepts to similar problems.

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

F≤ 4
6 V
Consequently
2
3 V≥ F
We note that the planar graph has at least 3 edges bounding.
Finding the sum, the sum of all edges in each face, we get twice the number
of edges
4 ≥∑
f E G
facedeg (f ) ≥∑
f E G
3= 3 F
And therefore
4
3 ≥ F
We proceed by use of Euler’s Formula (Mandl, 2014) which is given by;
| V | - | E| + | F |=2
Where | F | is the number of faces in the planar that is embedding
V-E+F≤ 2
3 -E+ 4
3 =0
V+F≤ 2
3 V- 4
3 =0
a(G) ≤ 2
3 V- 4
3 =0
= a(G) ≤ 2
3 V- 4
3
References
Mandl, P., Navarro-Compán, V., Terslev, L., Aegerter, P., van der Heijde, D.,
D'Agostino, M. A., ... & Schueller-Weidekamm, C. (2014). FRI0127 Eular

Recommendations for the Use of Imaging in Spondyloarthritis in
Clinical Practice. Annals of the Rheumatic Diseases, 73(Suppl 2), 427-
428.
Calude, C. S., & Calude, E. (2010). The complexity of the four colour
theorem. LMS Journal of Computation and Mathematics, 13, 414-425.