what is the largest number of edges that a planar graph G on v vertices can have?
We can deduce the answer from Eulers formula. Each region defined by a drawing of G in the plane is bounded by a cycle of the G. If that cycle is not a triangle, we can add an edge between two opposite vertices and increase the number of edges. We conclude then that a graph G on v vertices with the most edges will have triangles for all its faces. Then each face has three edges on its boundary, and the number of edge-face pairs with the edge bounding the face will be 3f. But each edge bounds 2 faces, so that the number of edge-face pairs with the edge bounding the face will also be 2e. We deduce then that f=2e/3, so that in this case we can write Eulers formula as v e + 2e/3 = 2 or 3v = e + 6. We notice also that the number of edge-vertex pairs with the vertex in the edge, is 2e and is also the sum of the degrees of all the vertices. This tells us that the sum of the degrees of the vertices of any edge maximal planar graph on v vertices obeys: The sum of the degrees of the vertices of
