Page 699 - Discrete Mathematics and Its Applications

678 10 / Graphs

In Exercises 61–64 determine whether the given pair of di- 65. Show that if G and H are isomorphic directed graphs,
rected graphs are isomorphic. (See Exercise 60.) then the converses of G and H (defined in the preamble
61. u 1 u 2 v 1 v 2 of Exercise 67 of Section 10.2) are also isomorphic.
66. Show that the property that a graph is bipartite is an iso-
morphic invariant.

67. Find a pair of nonisomorphic graphs with the same de-
u 3 u 4 v 3 v 4 gree sequence (defined in the preamble to Exercise 36
in Section 10.2) such that one graph is bipartite, but the
62. u 1 u 2 v 1 v 2 other graph is not bipartite.

∗ 68. How many nonisomorphic directed simple graphs are
there with n vertices, when n is
a) 2? b) 3? c) 4?
u 3 u 4 v 3 v 4
∗ 69. What is the product of the incidence matrix and its trans-
63. u 1 v 1
pose for an undirected graph?
∗ 70. How much storage is needed to represent a simple graph
u 4 v 4 with n vertices and m edges using
a) adjacency lists?
u 2 u 3 v 2 v 3 b) an adjacency matrix?
64. u 1 u 2 u 3 c) an incidence matrix?

A devil’s pair for a purported isomorphism test is a pair of
nonisomorphic graphs that the test fails to show that they are
not isomorphic.

u 4 u 5 u 6 71. Find a devil’s pair for the test that checks the degree se-
quence (defined in the preamble to Exercise 36 in Sec-
v 1 v 2 tion 10.2) in two graphs to make sure they agree.

72. Suppose that the function f from V 1 to V 2 is an isomor-
phism of the graphs G 1 = (V 1 ,E 1 ) and G 2 = (V 2 ,E 2 ).
v 6 v 3
Show that it is possible to verify this fact in time polyno-
mial in terms of the number of vertices of the graph, in
terms of the number of comparisons needed.
v 5 v 4

10.4 Connectivity

Introduction

Many problems can be modeled with paths formed by traveling along the edges of graphs. For
instance, the problem of determining whether a message can be sent between two computers
using intermediate links can be studied with a graph model. Problems of efficiently planning
routes for mail delivery, garbage pickup, diagnostics in computer networks, and so on can be
solved using models that involve paths in graphs.

Paths

Informally, a path is a sequence of edges that begins at a vertex of a graph and travels from
vertex to vertex along edges of the graph.As the path travels along its edges, it visits the vertices
along this path, that is, the endpoints of these edges.