336 CHAPTER 6 Graph Theory
6.1.2 Subgraphs
In the Job Assignment Problem, the graph theory answer consists in identifying a graph
that is formed by some of the vertices and some of the edges of the graph that models
the problem. This idea of looking at part of a graph is made precise by the notion of a
subgraph.
Definition 4. A graph H = (V 1 , El) is a subgraph of G = (V, E) provided that V 1 _-
V, E 1 C E, and for each e E E 1 , both ends of e are in V 1. H is a spanning subgraph of G
if H is a subgraph of G and V 1 = V. H is an induced subgraph of G if H is a subgraph
of G such that E 1 consists of all the edges of G with both ends in V 1.
An induced subgraph is found by choosing a subset of the vertex set of a graph and
then defining the edge set to be all the edges of the original graph with both ends in the
chosen subset of vertices. An induced subgraph with vertex set V is often denoted as < V>.
Examples of the different kinds of subgraphs are shown in Figure 6.7.(^1 16)
5 2
5 2 2
4 3 4 3
G Subgraph
(^1 1 6)
2 5 1 2
4 3 4 3
<{ 1,2,3,41> Spanning
Induced Subgraph Subgraph
Figure 6.7 Subgraph, induced subgraph, and spanning subgraph.
The notation E(G) (respectively, V(G)) denotes the edges (respectively, vertices) of
the graph G. When more than a single graph is being discussed, this notation makes it clear
which edges and vertices are being considered. Normally, we use the letters alone, as in
G = (V, E).
Two useful operations for combining graphs include the union and the intersection of
two graphs. Let G 1 = (V 1 , Ej) and G 2 = (V 2 , E 2 ) be graphs.
The union of G 1 and G 2 , denoted by G 1 U G 2 , is the graph G 3 defined as G3=
(V 1 U V 2 , E 1 U E 2 ). The intersection of G 1 and G 2 , denoted by G 1 nl G 2 , is the graph G 4
defined as G 4 = (V 1 n V 2 , EI n E 2 ).
Another operation that is used with a single graph is complementation. For this defini-
tion, we need an analogue of a universal set. In this case, we use the complete graph on the
vertex set of the graph for which we would like to find the complement. Let G = (V, E)
be a subgraph of K 1 v I, the complete graph on I V I vertices. The complement of G in KI v,
denoted as G = (V 1 , El), is the subgraph of KiVI with V 1 = V and E 1 = KivI (E) - E.