Euler Cycle

   
Recent changes
Table of contents
Links to this page
FRONT PAGE / INDEX

Informally ...

Given a network, or graph, an Euler Cycle is a tour from vertex to vertex, finishing where it started, and traversing every edge exactly once.

In contrast:

  • An Euler Path traverses every edge but need not finish where it started;
  • A Hamilton Cycle visits every vertex exactly once and finishes where it started
    • ... so the start/end vertex is, in some sense, visited twice
      • ... except that starting at a vertex is not regarded as "a visit"; and
  • A Hamilton Path includes every vertex exactly once,
    • ... and need not finish where it started.

More formally ...

Given a graph $G=(V,E)$ where $|E|=m,$ an Euler Cycle is a list $L=[v_0,v_1,...,v_m]$ of vertices such that:

  • $v_0=v_m$
    • That is, the cycle ends where it started

  • For every $i\in{1,2,...,m},$ $(v_{i-1},v_i)\in{E}$
    • That is, going from vertex to vertex is along an edge

  • For all $e=(u,v)\in{E},$ there exists exactly one $i$ such that either $u=v_i$ and $v=v_{i+1}$ or vice versa.
    • That is, every edge is traversed exactly once.

A graph with an Euler Cycle is said to be "Eulerian."


Observations

This definition does not require the graph to be connected, but in the case of a graph with more than one component, all but at most one component must contain exactly one vertex and no edges.

The "degree" of a vertex is the number of edges incident to it, and it is a well-known theorem that a connected graph is Eulerian if and only if every vertex has even degree. A graph has an Eulerian Path that is not a cycle if and only if every vertex has even degree except for two.

The well-known Bridges of Koenigsberg problem asks if the road network of a particular town is Eulerian. Some versions require an Euler Cycle, but many ask only for an Euler Path. Neither is possible, as proven by Leonhard Euler in 1736. The Doodle Theorem says that a planar Eulerian graph can be two-coloured, and hence is bi-partite.

Contents

 

Links on this page

 
Site hosted by Colin and Rachel Wright:
  • Maths, Design, Juggling, Computing,
  • Embroidery, Proof-reading,
  • and other clever stuff.

Suggest a change ( <-- What does this mean?) / Send me email
Front Page / All pages by date / Site overview / Top of page

Universally Browser Friendly     Quotation from
Tim Berners-Lee
    Valid HTML 3.2!