Single stroke drawing

Task number: 4247

Prove that any connected Eulerian planar graph can be drawn into a plane by one closed non-selfintersecting stroke (parts of the stroke may only ’touch’ at vertices).

  • Solution

    Consider a stroke \( T \), and in it two consecutive visits to the same vertex \( in \), where the stroke ’intersects’ itself.

    We divide the stroke into sections \( T_0, v, T_1, v, T_2 \). If we pass the section \( T_1 \) in the opposite direction, we eliminate one intersection.

    selfintersection

    In this way, we incrementally eliminate all crossings.

Difficulty level: Easy task (using definitions and simple reasoning)
Solution require uncommon idea
Cs translation
Send comment on task by email