Eulerian Path

RulesEdit

 
An example puzzle from WPC 2017 IB: which of the shapes has an Eulerian path?

Construct a method to draw the given shape without lifting the pen/pencil or folding the paper, without tracing the same line more than once.

Rule variationsEdit

  • Identify the shape that can be drawn without lifting the pen/pencil or folding the paper. (From WPC 2017)

History of the puzzleEdit

The first problem of this type is the Seven Bridges of Königsberg problem resoluted negatively by Leonhard Euler (Switzerland) in 1736. His solution is often said to be the first result in the field of graph theory. Necessary condition for such path (now known as Eulerian paths) to exist is very simple; at least all but two vertices in the graph should have an even degree.

Construction of such path is a more complicated problem. Fleury's algorithm, published 1883, is an algorithm that solves this problem.[1]

Appearances in the past WPCsEdit

ReferencesEdit