Original And Sub Graphs
Introduction: When edges and vertices are removed from a graph, without removing endpoints of any remaining edges, a smaller graph is obtained. Such a graph is called a subgraph of the original graph.
DEFINITION A subgraph of a graph G = (V ,E) is a graph H = (W, F), where W ⊆ V and F ⊆ E. A subgraph H of G is a proper subgraph of G if H = G. Given a set of vertices of a graph, we can form a subgraph of this graph with these vertices and the edges of the graph that connect them.
DEFINITION Let G = (V ,E) be a simple graph. The subgraph induced by a subsetW of the vertex set V is the graph (W, F), where the edge set F contains an edge in E if and only if both endpoints of this edge are in W.
EXAMPLE 1 The graph G shown in Figure 15 is a subgraph of K5. If we add the edge connecting c and e to G, we obtain the subgraph induced by W = {a, b, c, e}.
REMOVING OR ADDING EDGES OF A GRAPH Given a graph G = (V ,E) and an edge e ∈ E,we can produce a subgraph ofGby removing the edge e. The resulting subgraph, denoted by G − e, has the same vertex set V as G. Its edge set is E − e. Hence,
G − e = (V ,E − {e}).
Similarly, if E' is a subset of E, we can produce a subgraph of G by removing the edges in E' from the graph. The resulting subgraph has the same vertex set V as G. Its edge set is E − E'.
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 G1 in Figure 16 produces a new graph G'1 with vertices a, b, d, and w. As in G1, there is an edge in G'1 connecting a and b and an edge connecting a and d. There also is an edge in G'1 that connects b and w that replaces the edges connecting b and c and connecting b and e inG1 and an edge in G'1 that connects d and w replacing the edge connecting d and e in G1.
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 The union of two simple graphs G1 = (V1,E1) and G2 = (V2,E2) is the simple graph with vertex set V1 ∪ V2 and edge set E1 ∪ E2. The union of G1 and G2 is denoted by G1 ∪ G2.
EXAMPLE Find the union of the graphs G1 and G2 shown in Figure 16(a).
Solution: The vertex set of the union G1 ∪ G2 is the union of the two vertex sets, namely, {a, b, c, d, e, f }. The edge set of the union is the union of the two edge sets. The union is displayed in Figure 16(b).