Degree Parity Along an Undirected Trail

Degree Parity Records the Trail’s Endpoints

A trail can revisit vertices, but it does not repeat edges. That restriction makes the set of edges used by a trail a subgraph whose vertex degrees have a precise parity pattern: every internal passage through a vertex contributes two incidences, while the trail’s endpoints contribute one each. Consequently, the used edges have odd-degree vertices only at the endpoints—and when the trail is closed, those endpoint contributions cancel modulo two.

All graphs in this tutorial are finite, simple, and undirected. A trail of length $k$ is a sequence $v_0,e_1,v_1,\ldots,e_k,v_k$ in which each $e_i$ joins $v_{i-1}$ to $v_i$, and no edge is repeated. Vertices may repeat. The trail is open if $v_0\ne v_k$ and closed if $v_0=v_k$. We allow the length-zero trail at a vertex: it has no edges and its initial and final vertices coincide.

Definition: For a trail $T$, let $F_T=\{e_1,\ldots,e_k\}$ be its set of edges, and let $H_T=(V,F_T)$ be the subgraph consisting of those edges and all vertices of $G$. The degree $\deg_{H_T}(v)$ counts the edges of $T$ incident with $v$. A vertex has odd degree in $H_T$ if this number is odd.

We count degree in the subgraph of used edges, not the number of times the trail’s written vertex sequence contains a vertex. An internal visit uses one edge to arrive and another to depart. This two-incidence contribution is even, even if the same vertex is visited several times.

The Parity Formula

Theorem: Let $T=v_0,e_1,v_1,\ldots,e_k,v_k$ be a trail in a finite simple undirected graph. For every vertex $v$, $$ \deg_{H_T}(v)\equiv \mathbf{1}_{v=v_0}+\mathbf{1}_{v=v_k}\pmod 2. $$ Thus, if $T$ is open, the vertices of odd degree in $H_T$ are exactly $v_0$ and $v_k$. If $T$ is closed, every vertex has even degree in $H_T$. The same conclusion for a length-zero trail is that every vertex has degree zero in $H_T$.

Proof. First suppose $k\ge1$. Count incidences of edges of $T$ with a fixed vertex $v$ by looking at the positions $v_0,\ldots,v_k$ in the trail sequence. Each internal position $v_i$, where $0<i<k$, contributes two incidences: one from $e_i$ and one from $e_{i+1}$. These contributions are even. A position at the start contributes one incidence if $v_0=v$, and a position at the end contributes one if $v_k=v$. Since no edge is repeated, counting the trail’s edge incidences counts each edge of $H_T$ exactly once. Therefore the parity of $\deg_{H_T}(v)$ is the sum, modulo two, of the start and end contributions, as claimed. If the trail is open, its distinct endpoints each receive one contribution, and every other vertex receives zero modulo two. If it is closed, the start and end are the same vertex, which receives $1+1=2\equiv0\pmod2$; every other vertex also receives zero modulo two. Finally, if $k=0$, then $F_T=\varnothing$, so every degree in $H_T$ is zero, and the right-hand side is $2\equiv0\pmod2$ at the single endpoint and zero elsewhere. $\square$

The formula allows repeated vertices without requiring a separate case for each kind of repetition: every internal position contributes an even amount. In particular, the initial vertex might appear again internally, and the final vertex might have other internal visits. Those visits still add pairs of incidences and do not change the parity conclusion.

Worked Examples

Worked Example: An Open Trail and the Remaining Edges

Let $G=(V,E)$ have $V=\{a,b,c,d,e\}$ and $E=\{ab,bc,ca,ad,de,bd\}$. Consider the trail $T=a,b,c,a,d,e$, using edges $ab,bc,ca,ad,de$ in that order. The unused edge is $bd$.

Count the used-edge degrees one vertex at a time. At $a$, the used edges are $ab,ca,ad$, so $\deg_{H_T}(a)=3$. At $b$, they are $ab,bc$, so the degree is $2$. At $c$, they are $bc,ca$, so the degree is $2$. At $d$, they are $ad,de$, so the degree is $2$. At $e$, the only used edge is $de$, so the degree is $1$. Thus the used-edge degree list in the order $a,b,c,d,e$ is $3,2,2,2,1$. Its odd-degree vertices are precisely $a$ and $e$, the distinct endpoints of the trail.

Now compare with the degrees in $G$. The edge list gives $\deg_G(a)=3$, $\deg_G(b)=3$, $\deg_G(c)=2$, $\deg_G(d)=3$, and $\deg_G(e)=1$. In the remaining graph, only $bd$ remains, so its degrees in the same order are $0,1,0,1,0$. The endpoint parities have toggled: $a$ changes from odd in $G$ to even in the remaining graph, and $e$ changes from odd to even. The parities at $b,c,d$ do not change.

Check: At each vertex, the original degree is the used-edge degree plus the remaining degree: $3=3+0$, $3=2+1$, $2=2+0$, $3=2+1$, and $1=1+0$. Each equality confirms the edge counts and the stated parity comparison.

Worked Example: A Closed Trail That Revisits Its Start

Let $G=(V,E)$ have $V=\{a,b,c,d,e\}$ and $E=\{ab,bc,ca,ad,de,ea\}$. These edges form two triangles sharing the vertex $a$. Take the closed trail $T=a,b,c,a,d,e,a$, which uses all six edges once.

At $a$, the four used edges $ab,ca,ad,ea$ give degree $4$. At each of $b,c,d,e$, the two incident edges in the trail give degree $2$. Thus the used-edge degrees are $4,2,2,2,2$, all even. The trail begins and ends at $a$, so the formula counts two endpoint contributions there, not one: $1+1=2$, which is even. Its repeated appearance inside the sequence adds only two incidences at a time.

Check: The first triangle contributes two incident edges at $a$, namely $ab,ca$, and the second contributes two more, namely $ad,ea$, giving $2+2=4$. Each of $b,c,d,e$ belongs to one triangle and has degree $2$. This independently verifies every degree in the used-edge subgraph.

Worked Example: A Trail Using Only Some Edges

Let $G=(V,E)$ have $V=\{1,2,3,4,5\}$ and $E=\{12,23,34,41,24,45\}$. Consider the trail $T=1,2,3,4,5$, which uses $12,23,34,45$, each once. The unused edges are $41$ and $24$.

The used-edge degrees are $1,2,2,2,1$: vertex $1$ is incident with $12$; vertex $2$ with $12,23$; vertex $3$ with $23,34$; vertex $4$ with $34,45$; and vertex $5$ with $45$. Therefore the odd-degree vertices are exactly $1$ and $5$.

For an additional check, the degrees in the original graph are $2,3,2,4,1$, while the degrees using only the remaining edges $41,24$ are $1,1,0,2,0$, in vertex order $1,2,3,4,5$. The original degree is the sum of the used and remaining degrees at each vertex: $2=1+1$, $3=2+1$, $2=2+0$, $4=2+2$, and $1=1+0$. Comparing original and remaining parities, only the trail endpoints $1$ and $5$ have changed parity.

How Removing the Trail Changes Parity

The used-edge formula has a direct consequence for the rest of the graph. Write $G-F_T$ for the graph obtained by deleting the edges of $T$ while retaining its vertices. Deleting those edges subtracts the used-edge degree from the original degree at each vertex.

Corollary: For any trail $T$ in $G$, and every $v\in V(G)$, $$ \deg_{G-F_T}(v)\equiv \deg_G(v)-\mathbf{1}_{v=v_0}-\mathbf{1}_{v=v_k}\pmod2. $$ Consequently, deleting the edges of an open trail toggles degree parity at its two endpoints and leaves the parity at every other vertex unchanged. Deleting the edges of a closed trail leaves every vertex’s degree parity unchanged.

Proof. The edges of $G$ are partitioned into the edges of $H_T$ and the edges of $G-F_T$. These edge sets are disjoint, so for every vertex $v$, $\deg_G(v)=\deg_{H_T}(v)+\deg_{G-F_T}(v)$. Rearranging gives $\deg_{G-F_T}(v)=\deg_G(v)-\deg_{H_T}(v)$. Substitute the theorem’s formula for $\deg_{H_T}(v)$ and reduce modulo two. For an open trail, the two indicator terms are one exactly at its distinct endpoints, so subtracting them toggles parity there and nowhere else. For a closed trail, the two terms cancel modulo two at the common endpoint, so no vertex parity changes. $\square$

This statement concerns the parity change caused by removing the trail’s edges from a graph. It does not say that the degrees in the original graph must equal the degrees in the used-edge subgraph: unused edges can contribute to the original degrees, as the first and third examples show.

Common Pitfall: A Walk Can Repeat an Edge

Do not apply the used-edge subgraph formula to a walk that repeats an edge. For example, take the triangle $G=(V,E)$ with $V=\{a,b,c\}$ and $E=\{ab,bc,ca\}$. The sequence $a,b,c,a,b$ is a walk from $a$ to $b$, but it is not a trail because it uses $ab$ twice.

A mistaken calculation treats the set of distinct edges used as $F=\{ab,bc,ca\}$. In that subgraph, every vertex has degree $2$, so this calculation would claim that the endpoints $a,b$ are not odd. The error is using the distinct-edge subgraph for a sequence that repeats an edge. If incidences are instead counted with traversal multiplicity, the two traversals of $ab$ contribute two incidences at $a$ and two at $b$; the traversals of $ca$ and $bc$ each contribute one more at their respective endpoints. The resulting multiplicity counts are $3$ at $a$, $3$ at $b$, and $2$ at $c$. They are odd exactly at the walk’s distinct endpoints. For trails, each edge is used once, so the multiplicity count agrees with the degree in the used-edge subgraph.

The endpoint parity rule is useful because it turns a traversal into a local degree statement. It identifies exactly what parity information the used edges carry, and it keeps the open and closed cases distinct: an open trail has two distinct odd-degree endpoints in its used-edge subgraph, whereas a closed trail has none. Parity alone, however, does not specify which edges to traverse or guarantee that a desired trail exists.

Check Your Understanding

Use the degree-parity formula and, where relevant, compare degrees before and after deleting the trail edges.

A trail has length $4$, begins at $p$, and ends at a distinct vertex $q$. Which vertices have odd degree in its used-edge subgraph?
Can a closed trail have a vertex of odd degree in its used-edge subgraph? Explain how the endpoint terms in the formula apply.
Suppose a trail starts and ends at $r$, and has positive length. How many endpoint contributions does $r$ receive modulo two?
For the graph with $V=\{1,2,3,4\}$ and $E=\{12,23,34,41,13\}$, consider the trail $1,2,3,4$. Find every used-edge degree and identify the odd-degree vertices.
Explain why the distinct-edge subgraph cannot be used to count degrees for the repeated-edge walk $a,b,c,a,b$ in a triangle.