Route Inspection Problem - Eulerian Paths and Circuits

Eulerian Paths and Circuits

In order for a graph to have an Eulerian circuit, it will certainly have to be connected.

Suppose we have a connected graph G = (V, E), The following statements are equivalent:

  1. All vertices in G have even degree.
  2. G consists of the edges from a disjoint union of some cycles, and the vertices from these cycles.
  3. G has an Eulerian circuit.
  • 1 → 2 can be shown by induction on the number of cycles.
  • 2 → 3 can also be shown by induction on the number of cycles, and
  • 3 → 1 should be immediate.

An Eulerian path (a walk which is not closed but uses all edges of G just once) exists if and only if G is connected and exactly two vertices have odd valence.

Read more about this topic:  Route Inspection Problem

Famous quotes containing the words paths and/or circuits:

    Fair is my Love, and cruel as she’s fair
    Her brow shades frowns, although her eyes are sunny;
    Her smiles are lightning, though her pride despair;
    And her disdains are gall, her favours honey.
    A modest maid, decked with a blush of honour,
    Whose feet do tread green paths of youth and love,
    Samuel Daniel (1562–1619)

    The Buddha, the Godhead, resides quite as comfortably in the circuits of a digital computer or the gears of a cycle transmission as he does at the top of a mountain or in the petals of a flower.
    Robert M. Pirsig (b. 1928)