Degree (Graph Theory)

Definition

Degree

Let $G=(V,E)$ be a graph and $v\in V$ a vertex.

Undirected graph

The degree of $v$ is the number of edge-ends at $v$:

$${\mathrm{deg}}_G(v)=\sum _{e\in E}{m}_e(v),$$

where $m_e(v)$ is the number of times $v$ occurs as an endpoint of $e$. Thus, a loop at $v$ contributes two.

Directed graph

The in-degree and out-degree of $v$ count the edges entering and leaving it:

$${\mathrm{deg}}_G^{-}(v)=\left|\{(u,v)\in E:u\in V\}\right|,{\mathrm{deg}}_G^{+}(v)=\left|\{(v,w)\in E:w\in V\}\right|.$$