Preliminaries for Analysis

For a graph $G=(V,E)$ with vertex set $V$ and edge set $E$:

  • $N = \left | V \right |$ denotes the number of vertices.
  • $M = \left | E \right |$ denotes the number of edges.

What can we say about $N$ and $M$?

  • Theoretically, $N \in \mathbb{Z}^{+}$. (A graph with an infinite vertex set is called an infinite graph!) In practice, $N$ is a positive finite integer.
  • If a graph is not connected, $M$ could be as small as $0$.
  • If a graph is not simple, we may have parallel edges, so $M$ could be (theoretically) as large as $+\infty$.

For a simple, connected graph, the minimum number of edges is $N-1$ (as in a Tree). On the other hand, the maximum number of edges is in a Complete graph, where there is an edge between every pair of vertices.

$$ n \space \text{choose} \space 2 = \binom{N}{2}=\frac{N(N-1)}{2} $$

Therefore, in a simple connected graph, $M \in \Omega(N)$ and $M \in O(N^2)$.

Degree of a vertex

The degree of a vertex $v$ is the number of edges incident with $v$. (A loop counts as two edges.)

The degree of the vertex $v$ is denoted by $\deg(v)$.

Degree sum formula:

$$ \sum_{v \in V}\deg(v) = 2M $$

Why?

Each edge contributes twice to the degree count of all vertices. Hence, both the left-hand and right-hand sides of this equation equal twice the number of edges.

This is also known as the Handshaking lemma.