Task number: 3845

Consider only those drawings of planar graphs in which each face is bounded by a cycle and where different faces may have at most one edge in common. We do not consider graphs without edges.

In each such graph \( G \) we look for a suitable vertex \( u \) so that by removing it the number of faces will decrease as much as possible. What decrease can we always guarantee? If more than one option applies, select the highest one.

  • 2
  • 4
  • 6
  • Solution

    The smallest degree in the \( G \) graph is 3 – if it was smaller, some face is not bounded by a cycle (degree 1) or some faces have more edges in common (degree 2).

    By removing the vertex of degree \( k \), the \( k \) faces are merged into one, ie the number of faces decreases by \( k-1 \).

    In general, the existence of a vertex of higher degree cannot be guaranteed, see e.g. a drawing of \( K_4 \).

  • Answer

    The correct answer is a.

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