Eulerian trails and circuits: existence and identification

Eulerian means every edge

An Eulerian trail uses every edge exactly once. An Eulerian circuit is closed; an open Eulerian trail has distinct endpoints. We consider finite undirected graphs with at least one edge. For an Eulerian route to exist, all vertices incident with an edge must lie in one connected component. Isolated vertices do not matter when the task is to traverse every edge; the generated graphs do not use this isolated-vertex exception

A triangle and one isolated vertex form a graph. Can a closed route use every edge exactly once?

Why the degrees matter

At each intermediate visit, an arrival edge pairs with a departure edge. A closed trail therefore uses an even number of incident edge ends at every vertex. An open Eulerian trail leaves just one unmatched end at each of its two endpoints. Hence zero odd vertices is necessary for a circuit and exactly two for an open trail. This argument alone proves necessity, not sufficiency

A connected graph has degrees 2, 3, 2, 4 and 3. How many odd-degree vertices are there?

The Königsberg bridge model

Represent each land region by a vertex and each bridge by its own edge. One labelling of the historical seven-bridge graph has two NK edges, two SK edges, and one each of KL, NL and SL. Degrees are 3 at N, 3 at S, 5 at K and 3 at L. All four vertices are odd, so no walk crosses each bridge exactly once, whether or not it returns to its start. Distinct parallel bridges remain distinct edges

Why can the seven-bridge graph with degrees 3, 3, 5 and 3 have no Eulerian trail?

Construct a circuit by splicing

For a connected graph with all degrees even, start at a vertex incident with an edge and follow unused edges until stuck. At any other vertex an arrival leaves an unused departure, so the trail can stop only at its start. If unused edges remain, connectedness gives a vertex of the current circuit incident with an unused edge. Start another closed trail there using unused edges, then splice it into the circuit. Each step adds edges and no edge is reused; finiteness makes the process terminate with every edge used

Obtain the two-odd case

When exactly u and v have odd degree, add one temporary edge uv, allowing a parallel edge if necessary. Now all degrees are even. Construct a circuit, then delete the temporary edge from that circuit and start just after it. The remaining sequence is an open Eulerian trail from u to v or v to u

In the two-triangle graph, which are the endpoints of every open Eulerian trail?

Bridges constrain a route

An Eulerian circuit cannot contain a bridge: after crossing into the other component, returning would require repeating that bridge. An open Eulerian trail may contain a bridge, but its endpoints must then lie on opposite sides. Splicing avoids a blind greedy rule; taking a bridge too early can strand unused edges

Construct and justify an Eulerian route, ungraded

For edges AB, BC, CD, DA and AC, construct an Eulerian trail. State its endpoints and justify why no Eulerian circuit exists. Then write the pairing argument for necessity and the splicing argument for sufficiency in your own words. Full route and proof construction are ungraded

Model: an open route and its limit

A-B-C-D-A-C uses AB, BC, CD, DA and AC exactly once. A and C have degree 3, while B and D have degree 2, so the endpoints must be A and C. A circuit is impossible because arrivals and departures would need to pair at A and C. For general sufficiency, form and splice closed trails in the even case; in the two-odd case add a temporary edge, construct a circuit and remove that edge

On the square with diagonal AC, an inspection must traverse every edge once. How many edge traversals does an open Eulerian trail require?

A shortest closed inspection

Give the edges lengths AB = 4, BC = 7, CD = 3, DA = 6 and AC = 5 metres. A closed inspection must cover every edge at least once. The first coverage totals 25 m. To make the two odd vertices even, the repeated edges must include a route joining A and C. The simple A-to-C paths are AC at 5 m, A–B–C at 4 + 7 = 11 m, and A–D–C at 6 + 3 = 9 m; positive lengths mean a repeated detour cannot improve them. Repeat AC for 5 m, giving a lower bound of 30 m that A-B-C-D-A-C-A attains

For the inspection network with lengths AB = 4, BC = 7, CD = 3, DA = 6 and AC = 5 metres, how much longer is the shortest closed inspection than an open edge-exact inspection?