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
«
«
«

Critical nonplanar and edge replacement

Task number: 4060

Let G be a non-planar graph such that G−e is planar for each edge of e of the graph G. Does then G necessarily contain an edge e such that G−e is the maximum planar graph, i.e. by adding any edge f, the graph G−e+f will be non-planar?

  • Hint

    Seek for an counterexample.

  • Solution

    The statement does not hold. A counterexample is e.g. the graph K3,3.

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