Why Connectivity Must Be Checked Alongside Degrees
Degree conditions give important information about Euler trails, but they do not by themselves tell us whether one route can reach every edge. If a graph has two separate components containing edges, a walk that uses an edge in one component cannot continue to an edge in the other. Isolated vertices raise a different issue: they may make the whole graph disconnected even though all its edges lie in one connected part and can be covered by a single Euler route.
Throughout, graphs are finite and simple. A trail is a walk that does not repeat an edge. An Euler trail is a trail that uses every edge of the graph exactly once; its first and last vertices may differ. An Euler circuit is a closed Euler trail. We use the convention that a length-zero trail at a vertex uses every edge when the graph has no edges and at least one vertex. The empty graph, with no vertices and no edges, has no trail under this definition.
If \(G\) has at least one edge, every edge has both endpoints in \(G^+\), so \(G^+\) contains all the edges of \(G\). Its components are exactly the edge-bearing components of \(G\). Thus, checking whether the non-isolated part is connected asks whether all edges belong to one component, without requiring isolated vertices to be connected to anything.
The Component-and-Degree Test
The earlier material on Euler trails establishes the connected-graph results we need: a connected graph with at least one edge has an Euler circuit exactly when every vertex has even degree; and it has an open Euler trail exactly when precisely two vertices have odd degree. Here, “connected” in those results can be applied to \(G^+\): its vertices are precisely the vertices incident with edges, and it contains every edge of \(G\).
Proof. First suppose \(G\) has an Euler trail. Every vertex of positive degree is incident with an edge, and that edge is used by the trail, so every vertex of \(G^+\) occurs on the trail. The part of the trail between any two occurrences gives a walk between those vertices using edges of \(G^+\). Therefore \(G^+\) is connected. By the degree-parity result for undirected trails, a closed Euler trail has no odd-degree vertices, while an open Euler trail has exactly two odd-degree vertices, its distinct endpoints.
Conversely, suppose \(G^+\) is connected and has at least one edge. If every vertex has even degree, the connected Euler-circuit result gives an Euler circuit in \(G^+\), which uses every edge of \(G\) because \(G^+\) contains all of them. If exactly two vertices have odd degree, the connected open-Euler-trail result gives an open Euler trail in \(G^+\), again using every edge of \(G\). These are trails in \(G\) as well: adding isolated vertices adds no edges that need to be traversed. The two cases also give the stated combined criterion for an Euler trail. \(\square\)
The theorem has two separate tests. The parity test checks the degrees; the component test checks whether one route can reach all edges. Isolated vertices are omitted from the component test, but their degree-zero status already satisfies the even-degree condition. For a graph with no edges, handle the convention separately: if it has at least one vertex, its length-zero trail is an Euler circuit; if it has no vertices, no trail can be started.
Worked Examples
Worked Example: An Isolated Vertex Does Not Block an Euler Circuit
Let \(G\) have vertex set \(V=\{1,2,3,4\}\) and edge set \(E=\{12,23,31\}\). Decide whether \(G\) has an Euler circuit.
The degrees are \(\deg(1)=2\), since the incident edges are \(12\) and \(31\); \(\deg(2)=2\), from \(12\) and \(23\); \(\deg(3)=2\), from \(23\) and \(31\); and \(\deg(4)=0\), since no edge is incident with \(4\). Thus every degree is even. The non-isolated part has vertices \(\{1,2,3\}\) and edges \(\{12,23,31\}\), so it is connected.
The theorem gives an Euler circuit. One is \(1,2,3,1\): it uses \(12\), then \(23\), then \(31\), each exactly once, and returns to \(1\).
Check: the route contains all three edges of \(G\), and its final vertex equals its first. Vertex \(4\) is not visited, but it contributes no edge to the route. Therefore it does not prevent the graph from having an Euler circuit.
Worked Example: Even Degrees in Two Edge-Bearing Components Are Not Enough
Let \(G\) have vertex set \(V=\{1,2,3,4,5,6,7\}\) and edge set \(E=\{12,23,31,45,56,64\}\). Is there an Euler circuit?
Vertices \(1,2,3\) each have degree \(2\), because they form the triangle with edges \(12,23,31\). Vertices \(4,5,6\) each have degree \(2\), because they form the triangle with edges \(45,56,64\). Vertex \(7\) has degree \(0\). Hence all seven degrees are even. But \(G^+\) has two components: one on \(\{1,2,3\}\) and one on \(\{4,5,6\}\). In particular, \(G^+\) is not connected.
There is no Euler circuit, and indeed there is no Euler trail covering all edges. Any walk using an edge of the first triangle stays among vertices \(1,2,3\); there is no edge from those vertices to \(4,5,6\). It cannot then use an edge of the second triangle.
Check: the edge set contains three edges in the first component and three in the second. A single trail cannot cover both groups because no step of the trail can cross between the components. Even though every degree is even, the required component condition fails.
Worked Example: Two Odd Vertices but No Global Open Euler Trail
Let \(G\) have vertex set \(V=\{1,2,3,4,5,6,7\}\) and edge set \(E=\{12,23,34,56,67,75\}\). Does \(G\) have an open Euler trail?
The edges \(12,23,34\) form a path on \(\{1,2,3,4\}\), so the degrees there are \(1,2,2,1\), respectively. The edges \(56,67,75\) form a triangle on \(\{5,6,7\}\), so each of those three vertices has degree \(2\). There are exactly two odd-degree vertices, \(1\) and \(4\), as required for an open Euler trail in a connected graph.
However, \(G^+\) has two components: the path component on \(\{1,2,3,4\}\) and the triangle component on \(\{5,6,7\}\). The component test fails, so there is no open Euler trail using every edge. The path edges and triangle edges cannot be joined into one trail because the edge set contains no edge between the two components.
Check: the degree calculation gives two odd vertices, but the theorem requires both that condition and connectedness of \(G^+\). The path alone has an open Euler trail \(1,2,3,4\), and the triangle alone has an Euler circuit, but neither route covers the other component's edges.
A Reliable Diagnostic Procedure
For a graph with at least one edge, apply the tests in this order. The table records the decision for the graph in the second example. “Odd vertices” means vertices whose degree is odd; isolated vertices are not counted because their degree is zero.
| Step | Test | Result for the example | Decision |
|---|---|---|---|
| 1 | Find the vertices of positive degree and the components they form. | \(\{1,2,3\}\) and \(\{4,5,6\}\) | Two edge-bearing components |
| 2 | Count the odd-degree vertices. | Each degree is \(2\); vertex \(7\) has degree \(0\) | Zero odd-degree vertices |
| 3 | Require one edge-bearing component as well as the appropriate parity. | \(G^+\) is disconnected | No Euler circuit or Euler trail |
The order matters as a way to avoid a common false conclusion: parity is quick to check, but it cannot repair a failure of connectivity. If there is only one edge-bearing component, the parity count then distinguishes a circuit from an open trail. Zero odd-degree vertices gives a circuit; exactly two gives an open trail; any other count gives neither.
Common Mistakes and Why the Distinction Matters
Mistake: “Every degree is even, so the graph has an Euler circuit.” In the two-triangle example, the incorrect calculation stops after observing \(\deg(v)=2\) for \(v\in\{1,2,3,4,5,6\}\) and \(\deg(7)=0\). The correction is to check that the vertices incident with edges belong to one component. Here they belong to two, so no single circuit can use all six edges.
Mistake: “A disconnected graph cannot have an Euler circuit.” This is false if disconnectedness comes only from isolated vertices. In the first example, the whole graph is disconnected because vertex \(4\) has no path to the triangle, but the triangle is one connected edge-bearing component and supplies an Euler circuit using every edge. The precise condition is connectivity of \(G^+\), not connectivity of the full vertex set.
This distinction is useful whenever the task is to cover edges by one continuous route. The route can ignore vertices that have no edges, but it cannot jump between separate sets of edges. It also clarifies terminology: some discussions call a graph Eulerian when it admits an Euler circuit, even if isolated vertices are present; other contexts reserve “connected Eulerian graph” for a graph whose entire vertex set is connected. Stating whether isolated vertices are ignored removes the ambiguity. The edge-coverage question itself is settled by the component-and-degree test.
Check Your Understanding
In each question with at least one edge, check both the number of odd-degree vertices and the connectivity of the non-isolated part.
- Let \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,ca\}\). Does the graph have an Euler circuit? What role does \(d\) play?
- Suppose a graph has two edge-bearing components, each of which is a cycle. Explain why every vertex can have even degree while the whole graph has no Euler circuit.
- Give the degree and component conditions for an open Euler trail in a graph with at least one edge.
- A graph has exactly two odd-degree vertices and one isolated vertex. What additional condition is needed before the degree count guarantees an open Euler trail?
- Under the length-zero convention in this tutorial, does a graph with three isolated vertices have an Euler circuit? What about the empty graph?