[Math] Confusion about euler path,trail,circuit

discrete mathematicsgraph theory

What's the difference between a euler trail, path,circuit,cycle and a regular trail,path,circuit,cycle since edges cannot repeat for all of them anyway?
And can vertices be repeated in a euler path?
Clarification will be much appreciated.Thanks.

Best Answer

Definitions taken according to Diestel's text Graph Theory:

  • A path is a nonempty graph $P=(V,E)$ with $V=\{x_0,x_1,x_2,\dots,x_k\}$, $E=\{x_0x_1,x_1x_2,x_2x_3,\dots,x_{k-1}x_k\}$ where all $x_i$ are distinct. The path's length is the number of edges, $k$.

  • A cycle is a path of length $k\geq 2$ along with an additional edge included between $x_0$ and $x_k$. The cycle's length is the number of edges (including this new one).

  • A circuit is essentially a cycle with the slightly different nuance that we are specifically referring to the edge-set as an element of the edge space when viewing this through the lens of linear algebra, not the graph itself.

  • A walk (also called a trail) is a nonempty alternating sequence of vertices and edges $v_0e_0v_1e_2v_2e_2\dots e_{k-1}v_k$ where $e_i$ is an edge between $v_i$ and $v_{i+1}$ for all $i<k$. A walk is closed if $v_0=v_k$.

Note that a walk/trail may repeat vertices and edges while a path may not repeat vertices (and hence cannot repeat edges either) and neither can a cycle (not counting starting and ending vertices). Also note that circuits often refer to the same thing as cycles in common practice as not everyone follows strict naming conventions.

  • A graph is called Eulerian if it there exists an Eulerian Tour, a closed walk which visits every edge exactly once.

  • A graph is called semi-eulerian if it has an Eulerian Walk, a walk which visits every edge exactly once, but not such a closed walk.

You will often see people refer to Eulerian cycles, Eulerian circuits, Eulerian paths, and Eulerian trials. Often times, either they have defined these terms differently, or they simply mean Eulerian Tours and Eulerian Walks respectively while using an incorrect word. (That is to say, an "Eulerian Cycle" is not necessarily a "cycle" in that we allow vertices to repeat)

In recap: Euler <insert object here> are like regular <insert object here> except they must use every available edge in the entire graph (and could possibly repeat vertices which is otherwise not allowed depending on strictness of naming conventions followed by that person). It is not strong enough to simply not repeat edges, but rather all edges in the graph must be used.

Related Question