158 GRAPH THEORY [CHAP. 8
Finite Graphs, Trivial Graph
A multigraph is said to befiniteif it has a finite number of vertices and a finite number of edges. Observe that
a graph with a finite number of vertices must automatically have a finite number of edges and so must be finite.
The finite graph with one vertex and no edges, i.e., a single point, is called thetrivial graph. Unless otherwise
specified, the multigraphs in this book shall be finite.
8.3Subgraphs, Isomorphic and Homeomorphic Graphs
This section will discuss important relationships between graphs.Subgraphs
Consider a graphG=G(V , E). A graphH=H(V′,E′)is called asubgraphofGif the vertices and edges
ofHare contained in the vertices and edges ofG, that is, ifV′⊆VandE′⊆E. In particular:
(i) A subgraphH(V′,E′)ofG(V , E)is called the subgraphinducedby its verticesV′if its edge setE′
contains all edges inGwhose endpoints belong to vertices inH.
(ii) Ifvis a vertex inG, thenG−vis the subgraph ofGobtained by deletingvfromGand deleting all
edges inGwhich containv.
(iii) Ifeis an edge inG, thenG−eis the subgraph ofGobtained by simply deleting the edgeefromG.Isomorphic Graphs
GraphsG(V , E)andG(V∗,E∗)are said to beisomorphicif there exists a one-to-one correspondence
f:V→V∗such that{u, v}is an edge ofGif and only if{f (u), f (v)}is an edge ofG∗. Normally, we do not
distinguish between isomorphic graphs (even though their diagrams may “look different”). Figure 8-6 gives ten
graphs pictured as letters. We note thatAandRare isomorphic graphs. Also,FandTare isomorphic graphs,K
andXare isomorphic graphs andM,S,V, andZare isomorphic graphs.
Fig. 8-6Homeomorphic Graphs
Given any graphG, we can obtain a new graph by dividing an edge ofGwith additional vertices. Two graphs
GandG∗are said tohomeomorphicif they can be obtained from the same graph or isomorphic graphs by this
method. The graphs(a)and(b)in Fig. 8-7 are not isomorphic, but they are homeomorphic since they can be
obtained from the graph(c)by adding appropriate vertices.