2. Basic terminology

Basic terminology: undirected graphs

If there an edge $e$ between vertices $u$ and $v$, we say that:

• $u$ and $v$ are adjacent
• $e$ is incident with $u$ and $v$

Degree (Graphs)

The degree of a vertex is the number of edges incident with it.

Link to original

• Isolated vertex

  An isolated vertex is ==a vertex of degree zero. So an isolated vertex is not adjacent to any vertex==.

  Link to original

• Pendant vertex

  A pendant vertex is ==a vertex of degree one. A pendant vertex is adjacent to exactly one other vertex==.

  Link to original

Handshaking Theorem

Handshaking theorem states that $\text{number of edges}=\frac{\text{sum of the degrees of vertices}}{2}$.

Link to original

title: Example 1
 
$$
	\begin{aligned}
		\text{degree}(a) &= 2 \\
		\text{degree}(b) &= \text{degree}(c) = \text{degree}(f) = 4 \\
		\text{degree}(e) &= 3 \\
		\text{degree}(d) &= 1, \text{so } d \text{ is pendant} \\
		\text{degree}(g) &= 0, \text{so } g \text{ is isolated} \\
	\end{aligned}
$$
 
```graphviz
graph A {
	f,e--b,c
	f--e
	b--c
	a--b,f
	d--c
	g
}

Basic terminology: directed graphs

If there is an edge $e$ going from vertex $u$ to $v$, we say that:

• $u$ is adjacent to $v$
• $u$ is the initial or start vertex of $e$
• $v$ is the terminal or end vertex of $e$

The in-degree of a vertex $v$ is the number of edges with $v$ as their terminal vertex. The out-degree of a vertex $v$ is the number of edges with $v$ as their initial vertex.

Note: A loop at a vertex contributes to both the in and out degrees.

$$\begin{array}{rl}\text{number of edges}& =\text{sum of the in-degrees of vertices}\\ & =\text{sum of the out-degrees of vertices}\end{array}$$

title: Example 2
 
$$
	\begin{aligned}
		\text{in-degree}(a) &= \text{in-degree}(a) = \text{in-degree}(d) = 2 \\
		\text{in-degree}(c) &= \text{in-degree}(e) = 3 \\
		\text{in-degree}(f) &= 0 \\
		\text{out-degree}(a) &= 4 \\
		\text{out-degree}(b) &= 1 \\
		\text{out-degree}(c) &= \text{out-degree}(d) = 2 \\
		\text{out-degree}(e) &= 3 \\
		\text{out-degree}(f) &= 0
	\end{aligned}
$$
 
```graphviz
digraph A {
	a->a,b,c,e
	b->d
	c->c
	d->e,c
	e->a,d,e
	f
}