# Definition:Degree (Vertex)

## Contents

## 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**.

## Examples

### Arbitrary Order $5$ Graph

The degrees of the vertices of the above graph are:

\(\displaystyle \map \deg {v_1}\) | \(=\) | \(\displaystyle 2\) | |||||||||||

\(\displaystyle \map \deg {v_2}\) | \(=\) | \(\displaystyle 2\) | |||||||||||

\(\displaystyle \map \deg {v_3}\) | \(=\) | \(\displaystyle 3\) | |||||||||||

\(\displaystyle \map \deg {v_4}\) | \(=\) | \(\displaystyle 1\) | |||||||||||

\(\displaystyle \map \deg {v_5}\) | \(=\) | \(\displaystyle 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 - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next): Entry:**degree**(of a vertex of a graph)