2.1.3. Vertex-degree

The degree of a vertex v in a graph G is the number of edges of G incident with v. It is denoted by or . The set of adjacent vertices to v is denoted by , . The vertex is called even or odd according to whether its degree is even or odd. A vertex is isolated if its degree is 0, while a vertex is end-vertex if its degree is 1.

  • is the minimum degree of G.
  • is the maximum degree of G.

Figure 2.3. Vertex-degrees in a graph

Theorem 2.1.  Let G be a graph of order n and size m where .

Then

This theorem is known as the „Handshaking Lemma" since it does in any party the total number of handshakes.

Proof.  The statement of the theorem follows immediately from the fact that every edge is incident with two vertices.

Corollary 2.2.  In any graph, there is an even number of odd vertices.

Proof. Let W and U denote the set of odd and even vertices, respectively. Then

The second sum is even, therefore the first sum must be also even. Each members in this sum is even, so the number of the members must be even.

A graph G1 is isomorphic to a graph G2 if there exists a one-to-one mapping φ, called isomorphism, from onto such that φ preserves adjacency and non-adjacency; that is, iff . The isomorphism will be denoted by G1 = G2.

 

Statement 2.3. If G1 = G2 then G1 and G2 have the same order, G1 and G2 have the same size and every vertex v in G1 and its image vertex φv in G2 have the same degree in their respective graph.

Figure 2.4. Isomorphic graphs

Consider the following mapping

which shows that G1 = G2.