Page 685 - Discrete Mathematics and Its Applications

664 10 / Graphs

a b c a b c
a b c

d e d f d e f
G
G 1 2 G 1 G 2
(a) (b)
FIGURE 16 (a) The Simple Graphs G 1 and G 2 ; (b) Their Union G 1 ∪ G 2 .

We can also add an edge e to a graph to produce a new larger graph when this edge connects
two vertices already in G. We denote by G + e the new graph produced by adding a new edge e,
connecting two previously nonincident vertices, to the graph G Hence,

G + e = (V, E ∪{e}).

The vertex set of G + e is the same as the vertex set of G and the edge set is the union of the
edge set of G and the set {e}.

EDGE CONTRACTIONS Sometimes when we remove an edge from a graph, we do not
want to retain the endpoints of this edge as separate vertices in the resulting subgraph. In such
a case we perform an edge contraction which removes an edge e with endpoints u and v and
merges u and w into a new single vertex w, and for each edge with u or v as an endpoint replaces
the edge with one with w as endpoint in place of u or v and with the same second endpoint.
Hence, the contraction of the edge e with endpoints u and v in the graph G = (V, E) produces a

new graph G = (V ,E ) (which is not a subgraph of G), where V = V −{u, v}∪{w} and E
contains the edges in E which do not have either u or v as endpoints and an edge connecting w
to every neighbor of either u or v in V . For example, the contraction of the edge connecting the

vertices e and c in the graph G 1 in Figure 16 produces a new graph G with vertices a, b, d,
1

and w.As in G 1 , there is an edge in G connecting a and b and an edge connecting a and d.
1

There also is an edge in G that connects b and w that replaces the edges connecting b and c and
1

connecting b and e in G 1 and an edge in G that connects d and w replacing the edge connecting
1
d and e in G 1 .
REMOVING VERTICES FROM A GRAPH When we remove a vertex v and all edges
incident to it from G = (V, E), we produce a subgraph, denoted by G − v. Observe that

G − v = (V − v,E ), where E is the set of edges of G not incident to v. Similarly, if V

is a subset of V , then the graph G − V is the subgraph (V − V ,E ), where E is the set of
edges of G not incident to a vertex in V .

GRAPH UNIONS Two or more graphs can be combined in various ways. The new graph that
contains all the vertices and edges of these graphs is called the union of the graphs. We will
give a more formal definition for the union of two simple graphs.
DEFINITION 9 The union of two simple graphs G 1 = (V 1 ,E 1 ) and G 2 = (V 2 ,E 2 ) is the simple graph with
vertex set V 1 ∪ V 2 and edge set E 1 ∪ E 2 . The union of G 1 and G 2 is denoted by G 1 ∪ G 2 .
EXAMPLE 19 Find the union of the graphs G 1 and G 2 shown in Figure 16(a). ▲