Eulerian Path

From WPC unofficial wiki
Jump to navigation Jump to search

Rules[edit]

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 variations[edit]

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

History of the puzzle[edit]

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 WPCs[edit]

References[edit]