Vertex Degree¶

Definition¶

The degree of a vertex in the undirected networks considered in the course is the number of edges incident to it. Parallel edges are counted separately. A vertex has even or odd degree according to the parity of that count.

Interpretation¶

The degree counts how many edge ends meet at a vertex, that is, how many ways there are to enter or leave it. Its parity, even or odd, decides whether a closed route can use every edge at that vertex exactly once.

A network of six vertices A to F with each vertex labelled by its degree; B and E have odd degree 3.

Each vertex in the figure is labelled with its degree: $A$ and $F$ have degree 2, $C$ and $D$ degree 4, and $B$ and $E$ degree 3. The degrees add up to $18$ , twice the number of edges, because every edge has two ends.

Parallel edges are counted separately because each one is a separate way in or out: in the Königsberg network, two bridges between the same pair of land areas add $2$ to the degree of each. Parity matters because of pairing: each time a closed route passes through a vertex it uses two of its edges, one to arrive and one to leave, so at a vertex of odd degree one edge is always left over.

Since the degrees sum to twice the number of edges, the number of odd-degree vertices is always even. This is what makes the Chinese postman construction work: the odd vertices can always be split into pairs, and a minimum-weight perfect matching chooses the cheapest pairing. In a connected network, whether an Euler tour exists is settled by degrees alone, see the Euler network characterization.

Key Results¶

At a vertex on an Euler tour, arrivals and departures pair the incident edges.
Duplicating a path reverses degree parity at its endpoints and preserves it at internal vertices.
Odd-degree vertices are the vertices matched in the Chinese postman construction.

Examples¶

In the figure, the degrees sum to $\displaystyle \sum_v\deg v=2|E|=18$ $18$ , since each of the nine edges contributes two ends. Thus the number of odd-degree vertices is even; the illustrated odd vertices are $B$ and $E$ .

In the course introduction network (not shown here), $A$ has degree 3 and $C$ has degree 5.
In the five-vertex Chinese postman example, A, B, D, and E are odd-degree vertices.

Prerequisites¶

Undirected Network

Sources¶

OR Modelling · Week 4

Aliases: degree of a vertex, valency, node degree Symbols: sum

Last updated: 20 October 2026 03:02