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

$(1): \quad$ How many times did you shake hands?
$(2): \quad$ How many times did your partner shake hands?