Task list filter?

Choose required ranks and required tasks. The table of contents will list only tasks having one of the required ranks in corresponding rankings and at least one of the required tags (overall). If you wish to filter only according to some rankings or tags, leave the other groups empty.

Task rankings

Difficulty level

Task tags

Task type
«
«
«

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 k6 in the graph, it can be split by a chord into a face of size 4 and a face of size k2.

    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.

Difficulty level: Easy task (using definitions and simple reasoning)
Routine calculation training
Cs translation
Send comment on task by email