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 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:

Wolfram Research (2010), EulerianGraphQ, Wolfram Language function, https://reference.wolfram.com/language/ref/EulerianGraphQ.html.

Text

Wolfram Research (2010), EulerianGraphQ, Wolfram Language function, https://reference.wolfram.com/language/ref/EulerianGraphQ.html.

CMS

Wolfram Language. 2010. "EulerianGraphQ." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/EulerianGraphQ.html.

APA

Wolfram Language. (2010). EulerianGraphQ. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/EulerianGraphQ.html

BibTeX

@misc{reference.wolfram_2023_euleriangraphq, author="Wolfram Research", title="{EulerianGraphQ}", year="2010", howpublished="\url{https://reference.wolfram.com/language/ref/EulerianGraphQ.html}", note=[Accessed: 18-March-2024 ]}

BibLaTeX

@online{reference.wolfram_2023_euleriangraphq, organization={Wolfram Research}, title={EulerianGraphQ}, year={2010}, url={https://reference.wolfram.com/language/ref/EulerianGraphQ.html}, note=[Accessed: 18-March-2024 ]}