The adjacency list structure

are communication connections between pairs of computers on the Internet. The computers and the connections between them in a single domain, like wiley.com, form a subgraph of the Internet. If this subgraph is connected, then two users on computers in this domain can send e-mail to one another without having their information packets ever leave their domain. Suppose the edges of this subgraph form a spanning tree. This implies that, if even a single connection goes down (for
example, because someone pulls a communication cable out of the back of a
computer in this domain), then this subgraph will no longer be connected.

There are a number of simple properties of trees, forests, and connected graphs.

We leave the justification of this proposition as an exercise (C-13.2).

13.1.1 The Graph ADT

edges():

Return an iterable collection of all the edges of the graph.

797

endVertices(e):
Return an array storing the end vertices of edge e.

insertEdge(v, w,x):
Insert and return a new undirected edge with end vertices v and w and storing element x.

removeVertex(v):
Remove vertex v and all its incident edges and return the element stored at v.

798