Teaching Kids Programming – Conditions That A Connected Graph Can Be Drawn With One Stroke (Euler Path/Euler Cycle/Circuit)

Teaching Kids Programming: Videos on Data Structures and Algorithms

A connected graph is a graph where there is a path between every pair of vertices.

An Euler path is a path in a graph which visits every edge exactly once. It is named after Leonhard Euler, who first described the concept. An Euler path must start and end at different vertices, and all of the edges of the graph must be used exactly once. An Euler circuit is an Euler path that begins and ends at the same vertex.

A graph can be drawn in one stroke, which can be determined by Euler’s graph theory. Euler was a mathematician of the 18th century who discovered a method to judge whether a graph can be drawn without repeating any edges, known as the “one-stroke” problem aka Euler Theorem.

Here are the two possible situations for the one-stroke problem:

A connected graph (a connected graph means there exists a path between any two nodes in the graph) can be drawn in one stroke if and only if the graph has no odd vertices or exactly two odd vertices. The degree of a vertex is the number of edges connected to it, and an odd vertex is a vertex with an odd degree.

For a disconnected graph, it cannot be drawn in one stroke.

Given the following four shapes:

Euler Cycle/Circuit and Euler Path

The degree: the number of edges that connect to a vertex.

• A: All degrees are even – thus Euler Cycle or Euler Path.
• B: Four Odd Degrees (the middle vertices on four sides) – thus we cann’t draw using one stroke.
• C: Disconnected Graph – we can’t draw using one stroke.
• D: Two Odd Degrees: Euler Path, we can start from the top left and finish at bottom right, or vice versa.

The sum of all degrees is an even number because it equals to the number of edges multipled by two. A edge contributes to 2 degrees (is connected to two vertices).

Euler Path and Euler Cycle or Circuit

We start drawing one one vertex S, and finish at vertex E: all other vertices in the middle require one edge forentering and one edge for leaving, otherwise, we are trapped at those who don’t have edges to leave. So, apart from the S and E, all other vertices have even number of edges hence even degrees. The S and E could be odd, as we don’t need to come back to S and we don’t need to leave once entering E. If all degrees are even, then we can choose any vertex as starting point and return to it, which is Euler Cycle or Euler Circuit.

Euler Path: if there exists a path that we can visit all the vertex and edges exactly once, then it is the Euler path. Thus, if there are exactly two odd degree vertices or all degrees are even, there is a Euler Path.

If it is a Euler cycle/circuit then it is also a Euler Path, but not vice versa.

Proof of One Stroke (Math Induction)

We can prove this conclusion using mathematical induction.

Base step: If there are only two nodes in the graph, they are both even vertices because their degrees are 2. Therefore, the graph can be drawn in one stroke.

Inductive step: Assume that all graphs with n or fewer nodes, if they have no odd vertices or exactly two odd vertices, can be drawn in one stroke. Now consider a graph with n+1 nodes. If this graph has no odd vertices or exactly two odd vertices, then we can start from any vertex and walk along any edge until we can’t go any further. Since all vertices (except the starting and ending vertices) are even vertices, we can leave a vertex whenever we enter it. Therefore, we will not be trapped in a vertex. This gives us a new graph where each vertex’s degree is 2 less than in the original graph, so each vertex in the new graph is still an even vertex. By the inductive assumption, we know that this new graph can be drawn in one stroke. Therefore, the original graph can also be drawn in one stroke. This completes the inductive step.

This is the condition and proof for a graph to be drawn in one stroke.

–EOF (The Ultimate Computing & Technology Blog) —