1.1.2 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
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.
Figure 2.4. Isomorphic graphs
Consider the following mapping
which shows that G1 = G2.