Preliminaries for Analysis

  • Count the degree of a vertex.
  • Describe the Handshaking lemma.
  • Describe the lower and upper bounds on the number of edges in a simple and connected graph.

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

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

What can we say about NN and MM?

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

For a simple, connected graph, the minimum number of edges is N−1N-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 choose 2=(N2)=N(N−1)2 n \space \text{choose} \space 2 = \binom{N}{2}=\frac{N(N-1)}{2}

Therefore, in a simple connected graph, M∈Ω(N)M \in \Omega(N) and M∈O(N2)M \in \Omicron(N^2).

Degree of a vertex

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

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

Degree sum formula:

∑v∈Vdeg⁡(v)=2M \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.