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.




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.