Important Properties of a Graph

Last updated Jan 23, 2022 Edit Source

• Cs data structures

Let $G$ be a graph with $m$ edges in its edge set $E$ and $n$ vertices in its vertex set $V$:

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

If G is directed:

$$ \sum_{v in V}outdeg(v) = \sum_{v in V}indeg(v) = m $$

• If G is connected, $m \geq n-1$
• If G is a tree, $m = n-1$
• If G is a forest, $m \leq n-1$

If G is a simple graph with $n$ vertices, the number of edges is $O(n^2)$.