Faces in a planar drawing
Task number: 4271
Show that in the maximum (in terms of number of edges) 2-connnected planar graph without triangles, each face is bounded by either a fourcycle or by a fivecycle.
Solution
If there is a face of size \(k\ge 6\) in the graph, it can be split by a chord into a face of size 4 and a face of size \(k-2\).
Care must be taken that this chord does not form a loop or multiple edge. When should such a case occur, just move along the face to adjacent vertices (for an articulation), or so that the ends of the chord are outside the bridge.
