Definition:Degree of Vertex
Definition
Let $G = \struct {V, E}$ be an undirected graph.
Let $v \in V$ be a vertex of $G$.
The degree of $v$ in $G$ is the number of edges to which it is incident.
It is denoted $\map {\deg_G} v$, or just $\map \deg v$ if it is clear from the context which graph is being referred to.
That is:
- $\map {\deg_G} v = \card {\set {u \in V : \set {u, v} \in E} }$
Even Vertex
If the degree of $v$ is even, then $v$ is called an even vertex.
Odd Vertex
If the degree of $v$ is odd, then $v$ is an odd vertex.
Isolated Vertex
If the degree of $v$ is zero, then $v$ is an isolated vertex.
Also known as
The degree of a vertex is also known as its valency.
Examples
Arbitrary Order $5$ Graph
The degrees of the vertices of the above graph are:
\(\ds \map \deg {v_1}\) | \(=\) | \(\ds 2\) | ||||||||||||
\(\ds \map \deg {v_2}\) | \(=\) | \(\ds 2\) | ||||||||||||
\(\ds \map \deg {v_3}\) | \(=\) | \(\ds 3\) | ||||||||||||
\(\ds \map \deg {v_4}\) | \(=\) | \(\ds 1\) | ||||||||||||
\(\ds \map \deg {v_5}\) | \(=\) | \(\ds 0\) |
Impossible Order $4$ Graph
There exists no simple graph whose vertices have degrees $1, 3, 3, 3$.
Party Puzzle
You arrive at a small party with your partner, which $3$ other couples are also attending.
Several handshakes took place.
Nobody shook hands with themselves or their partners.
Nobody shook hands with anyone else more than once.
After all the handshaking had taken place, you asked each person, including your partner, how many times they had shaken hands.
Every person replied with a different answer.
- $(1): \quad$ How many times did you shake hands?
- $(2): \quad$ How many times did your partner shake hands?
Also see
- Out-Degree and In-Degree in the context of directed graphs.
- Results about degrees of vertices can be found here.
Sources
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $2$: Elementary Concepts of Graph Theory: $\S 2.1$: The Degree of a Vertex
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): degree: 5. (of a vertex of a ${}^*$graph)
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): graph: 2.
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): degree: 5. (of a vertex of a ${}^*$graph)
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): graph: 2.
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): degree (of a vertex of a graph)