EulerianGraphQ

EulerianGraphQ[g]

yields True if the graph g is Eulerian, and False otherwise.

Details

  • A graph is Eulerian if it has a cycle that traverses every edge exactly once.

Examples

open allclose all

Basic Examples  (2)

Test whether an undirected graph is Eulerian:

Not all graphs have an Eulerian cycle:

Scope  (5)

EulerianGraphQ works with undirected graphs:

Directed graphs:

Multigraphs:

EulerianGraphQ gives False for expressions that are not graphs:

EulerianGraphQ works with large graphs:

Applications  (3)

Find if the the seven bridges of the city of Königsberg over the river Pregel can all be traversed in a single trip without doubling back, with the additional requirement that the trip end in the same place it began:

No:

Test whether the figure of an envelope can be traced without lifting the pen and without going over the same line twice:

A scheduling of a conference room and the corresponding graph of participants with edges between attendees of the same meeting:

Test whether two consecutive meetings can share a participant:

Properties & Relations  (7)

An Eulerian cycle can be found using FindEulerianCycle:

A connected undirected graph is Eulerian iff every graph vertex has an even degree:

A connected undirected graph is Eulerian if it can be decomposed into edge disjoint cycles:

The graphs are cycles if they are connected and have an equal number of edges and vertices:

For connected directed graphs:

The line graph of an undirected Eulerian graph is Eulerian:

The line graph of an Eulerian graph is Hamiltonian:

A connected directed graph is Eulerian iff every vertex has equal in-degree and out-degree:

Cycle graphs are Eulerian:

Introduced in 2010
 (8.0)