Lagmental Vicfred

Euler Trails Are Controlled by Vertex Parity by Vicfred

tags: mathematics, paths, network flows, matchings

A connected undirected graph has an Euler circuit exactly when every degree is even. I will separate the object being defined from the consequence being claimed.

Definitions first

Weighted paths minimize \(\sum_{e\in P}w(e)\), flows use values \(f:E\to\mathbf R_{\ge0}\) with conservation, and matchings enforce degree at most one. Each problem has a dual obstruction.

$$ \deg(v)\equiv0\pmod2\quad\forall v $$

The formulas should not be merged too early. The datum \(\mathsf D\), the conclusion \(\mathsf C\), and the bridge \(\Longrightarrow\) have three different logical jobs.

$$ G\ \text{has an Euler circuit}\Longleftrightarrow G\ \text{is connected after deleting isolated vertices and every degree is even} $$

A small case in full

An explicit case prevents the notation from becoming ceremonial. Every subscript and superscript in the display contributes to the value.

$$ \#\{v:\deg(v)\text{ odd}\}=\begin{cases}0,&\text{Euler circuit},\\2,&\text{open Euler trail},\\\text{otherwise},&\text{neither}.\end{cases} $$

The reusable statement

A good test for understanding is to change the presentation while keeping the invariant fixed. The aligned form makes that comparison unusually easy.

$$ \begin{aligned} \mathsf{D}\;&:\quad \deg(v)\equiv0\pmod2\quad\forall v,\\[5pt] \mathsf{C}\;&:\quad G\ \text{has an Euler circuit}\Longleftrightarrow G\ \text{is connected after deleting isolated vertices and every degree is even}. \end{aligned} $$

A nearby false statement

Dijkstra requires nonnegative edge weights, while flow capacities must be interpreted on a directed residual network even when the original graph is undirected.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] G\ \text{has an Euler circuit}\Longleftrightarrow G\ \text{is connected after deleting isolated vertices and every degree is even} \end{gathered}} $$

With the dependency made explicit, the same pattern can be recognised safely in nearby problems. A changed hypothesis should now be easy to spot.

This article was posted on Fri 06 May 2022. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.