Definition:Degree of Vertex

From ProofWiki
Jump to navigation Jump to search

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

SimpleGraphDisconnected.png

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

  • Results about degrees of vertices can be found here.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Degree_of_Vertex&oldid=683976"