Let G be a connected planar K3free graph of order n 3 Prove

Let G be a connected, planar, K₃-free graph of order n 3. Prove that G
has no more than 2n 4 edges.

Solution

Let G be a planar connected graph and let f denote the number of faces in G. Recall that every edge appears in at most two faces and every face is bounded by at least 3 edges (since m 3). Thus 3 f 2m. By Euler’s formula, we have m = n + f 2 n + 2m/3 2. So m/3 n 2 and hence n 3m 6. If G is K3-free graph, then every face is bounded by at least 4 edges (since m 4), and we have 4 f 2m. This yields m = n + f 2 n + m/2 2 and thus m/2 n 2.

This implies m 2n 4.

QED.