1 Take a hexagon and add the three longest diagonals Is the

1. Take a hexagon and add the three longest diagonals. Is the graph obtained
this way planar?

2. Every face of a convex polyhedron has at least 5 vertices, and every
vertex has degree 3. Prove that if the number of vertices is n, then the number
of edges is at most 5(n 2)/3.

Solution

1) We cannot induce a vertex in the middle hence the diagonals of the hexagon will always intersect in the plane . Therefore , the graph is not planar

2) We know by Euler\'s Formula , n + f = e + 2

where e = No of edges

f = No of faces

n = No of vertices

Each face has 5 vertices , this implies each face must have 5 edges and since each edge has contribution to two faces

=> Total No. of edges , (f/2) (e/5)

Plugging f from Euler\'s formula

=> 5( e + 2 - n ) 2e

=> 3e 5(n-2)

=> e 5(n-2)/3