Chapter 2
Basic Concepts of Graph Theory
In this chapter we introduce some fundamental concepts of graph theory that are
essential for structure analysis and structure synthesis of mechanisms. Readers are
encouraged to refer to Gibsons [1] and Harary [2] for more detailed descriptions of
the theory.
2.1 Definitions
A graph consists of a set of vertices (points) together with a set of edges or lines.
The set of vertices is connected by the set of edges. Let the graph be denoted by
the symbolG, the vertex by setV , and the edge by setE. We call a graph withv
vertices and e edges a (v, e) graph. Edges and vertices in a graph should be labeled
or colored, otherwise they are indistinguishable.
Each edge of a graph connects two vertices called the end points. We specify an
edge by its end points; that is, e
ij
denotes the edge connecting vertices i and j .An
edge is said to be incident with a vertex, if the vertex is an end point of that edge.
The two end points of an edge are said to be adjacent. Two edges are adjacent if they
are incident to a common vertex. For the (11, 10) graph shown in Figure 2.1a,e
23
is
incident at vertices 2 and 3. Edges e
12
, e
23
, and e
25
are adjacent.
2.1.1 Degree of a Vertex
The degree of a vertex is defined as the number of edges incident with that vertex.
A vertex of zero degree is called an isolated vertex. We call a vertex of degree two

Two vertices are said to be connected, if there exists a path from one vertex to the
other. Note that two connected vertices are not necessarily adjacent. A graph G is
said to be connected if every vertex in G is connected to every other vertex by at least
one path. The minimum degree of any vertex in a connected graph is equal to one.
© 2001 by CRC Press LLC
For example, the graph shown in Figure 2.1b is connected, whereas the one shown in
Figure 2.1a is not.
A subgraph of G is a graph having all the vertices and edges contained in G.In
other words, a subgraph of G is a graph obtained by removing a number of edges
and/or vertices from G. The removal of a vertex from G implies the removal of all
the edges incident at that vertex, whereas the removal of an edge does not necessarily
imply the removal of its end points although it may result in one or two isolated
vertices.
A graph G may contain several pieces, called components, each being a connected
subgraph of G. By definition, a connected graph has only one component, otherwise it
is disconnected. For example, the graph shown in Figure 2.1a has three components;
the graph shown in Figure 2.1b is a subgraph, but not a component of Figure 2.1a;
whereas the graphs shown in Figures 2.1c and d are components of Figure 2.1a.
2.1.4 Articulation Points, Bridges, and Blocks
An articulation point or cut point of a graph is a vertex whose removal results in an
increase of the number of components. Similarly, a bridge is an edge whose removal
results in an increase of the number of components. A graph is called a block, if it is
connected and has no cut points. The minimal degree of a vertex in a block is equal
to two. For the graph shown in Figure 2.1a, vertices 7 and 9 are cut points, whereas
e
67
,e
78
,e
79

A graph G is said to be a bipartite if its vertices can be partitioned into two subsets,
V
1
and V
2
, such that every edge of G connects a vertex in V
1
to a vertex in V
2
.
Furthermore, the graph G is said to be a complete bipartite if every vertex of V
1
is
connected to every vertex of V
2
by one edge. A complete bipartite is denoted by K
i,j
,
where i is the number of vertices in V
1
andj the number of vertices inV
2
. Figure 2.4b
shows a K
3,3
complete bipartite.
© 2001 by CRC Press LLC
FIGURE 2.4
K
5

. Then, that section of P
from j

to k

and that section of Q from j

to k

form a circuit. This leads to a
contradiction since T contains no circuit. Therefore, there exists one and only
one path between any two vertices of T .
2. T contains (v − 1) edges.
Proof: We prove this property induction. Clearly v = e + 1 holds for a
connected graph of one or two vertices. Assume that v = e + 1 holds for
a tree of fewer than v vertices. If T has v vertices, the removal of any edge
disconnects T in exactly two components because of the first property. By
the induction hypothesis, each component contains one more vertex than edge.
Therefore, the total number of edges in T must be equal to v − 1.
3. Connecting any two nonadjacent vertices of a tree with an edge leads to a graph
with one and only circuit.
Proof: Since every two nonadjacent vertices are connected by a path, walking
from the first vertex to the second along the existing path and returning to the
first vertex by the added edge completes a circuit.
Figure 2.6 shows a family of trees with six vertices.
2.3 Planar Graph
A graph is said to be embedded in a plane when it is drawn on a plane surface such
that all edges are drawn as straight lines and no two edges intersect each other. A
graph is planar if it can be embedded in a plane. Specifically, if G is a planar graph,
there exists an isomorphic graph G

said to homeomorphic if one can be made isomorphic to the other by applying this
process. The following theorem, known as Kuratowski’s theorem, can be applied for
identification of planar graphs [3].
THEOREM 2.2
A graph is planar, if and only if it contains no subgraph homeomorphic to the K
5
or
K
3,3
graph.
2.4 Spanning Trees and Fundamental Circuits
A spanning tree, T , is a tree containing all the vertices of a connected graph G.
Clearly, T is a subgraph of G. Corresponding to a spanning tree, the edge set E of G
can be decomposed into two disjoint subsets, called the arcs and chords. The arcs of
G consist of all the elements of E that form the spanning tree T , whereas the chords
consist of all the elements of E that are not in T . The union of the arcs and chords
constitutes the edge set E.
In general, the spanning tree of a connected graph is not unique. The addition
of a chord to a spanning tree forms one and precisely one circuit. A collection
of all the circuits with respect to a spanning tree forms a set of independent loops
or fundamental circuits. The fundamental circuits constitute a basis for the circuit
© 2001 by CRC Press LLC
space. Any arbitrary circuit of the graph can be expressed as a linear combination of
the fundamental circuits using the operation of modulo 2, i.e., 1 + 1 = 0.
Figure 2.9a shows a (5, 7) graphG, Figure 2.9b shows a spanning treeT , and
Figure 2.9c shows a set of fundamental circuits with respect to the spanning treeT .
The arcs of G consist of edges e
15
,e
25

In this section, we explore some fundamental properties of planar connected graphs
that are essential for structure analysis and structure synthesis of mechanisms.
Let d
i
denote the degree of a vertex i, and e denote the number of edges in a graph
G. Since each edge is incident with two end vertices, it contributes 2 to the sum of
the degrees of the vertices. Therefore, the sum of the degrees of all vertices in a graph
is equal to twice the number of edges:

i
d
i
= 2e. (2.4)
For the (8, 10) graph shown in Figure 2.8, we haved
1
= d
2
= d
3
= d
4
= 3, and
d
5
= d
6
= d
7
= d
8