Vertex Degree

Topics: Graph Theory - Vertex

---

In graph theory, the degree of a vertex is defined as the amount of edges that incide on it. The degree of a vertex $v$ is denoted $d(v)$.

Loops

Note that loops have two degrees, since one same edge incides twice on the same vertex.

We denote the minimum vertex degree in a graph with ${\delta }_{min}$ or $\delta$, and the maximum with ${\delta }_{max}$ or $\Delta$.

Even Vertices, Odd Degrees §

(corollary, from handshaking lemma)

In a graph, when the sum of the even degrees is even, then it must hold that the amount of vertices with odd degrees is even.

Odd Degree §

(theorem)

In a graph with no loops, the number of vertices with an odd degree is even.

Internal and External Degrees of a Vertex