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.