# Graphs and Connectivity

You are undoubtedly familiar with graphs of functions from your experience in algebra courses: y = f(x) on the Cartesian Plane. Those graphs all shared one common characteristic: any two graphs which appeared to be different did indeed represent different functions (as long as the units on the coordinate axes were the same). For example, it is clear that a straight line and a parabola represent different functions.

We are concerned in this chapter with a very different kind of graph. For us, a graph is a "topological" object: graphs are distinguished by the way in which their parts are connected, but not necessarily by their appearance. To be specific, we will define a graph as a set of points called "vertices" (singular "vertex") and a set of lines called "edges" which connect the vertices. Since we will not be concerned with graphs containing isolated vertices (with no edges connecting them to the remainder of the graph), we will be able to describe any graph completely as a set of edges, with each edge specified as a set containing the two vertices connected by that edge. For example, the following graph

is completely described by the set of edges
{{A,B},{A,C},{A,D},{B,C},{B,D},{C,D},{D,E},{E,F},{E,G}}
Since the edges are specified as sets, the order of the vertices does not matter: the edge
{A,B}
is the same as the edge
{B,A}.
Now consider the following graph:
It appears to be very different from the first graph: the vertices are in different places and most of the edges are either larger or smaller than before. However, the two graphs are identical! If we write down the set of edges in the second graph:
{{A,B},{A,C},{A,D},{B,C},{B,D},{C,D},{D,E},{E,F},{E,G}}
we see that it is exactly the same set which we wrote down for the first graph. Two graphs are equivalent if they have the same set of edges.

It is instructive to see visually how the second graph is equivalent to the first:

• the vertex B was moved down and to the left;
• the vertex C was move to the left slightly;
• the edge connecting B to D was lifted "above" the graph without breaking the connection between B and D, and was deformed into a circular arc around A;
• the vertex E was moved down and slightly to the left;
• the vertex F was lifted above the graph and placed below B, and
• the vertex G was moved up and to the left.

Click here to view the deformation of the first graph into the second. The most important thing to notice about this process is that none of the edges were disconnected from their vertices or otherwise broken at any time. This observation provides us with an intuitive understanding of topological objects: what matters is how they are connected, not how they appear.

the sum of the degrees of the vertices in a graph is equal to twice the number of edges.
In the example above, which had 9 edges, the sum of the degrees of the vertices is
3 + 3 + 3 + 3 + 4 + 1 + 1 = 18.
This relationship is perhaps the simplest example of a "topological invariant". A topological invariant is a relationship which is true regardless of the appearance or size of the graph.

### Connectivity

We can describe the connectivity of a graph in terms of movement between vertices. We define a "walk" to be an alternating sequence of vertices and edges, beginning and ending with vertices. A walk is completely described by an ordered list of vertices: in the graph above,

• A, B
• A, B, C
• A, B, A
• A, B, C, B, A
• A, C, D, E, G

are all walks (and there are infinitely many more). The length of a walk is defined to be the number of edges in the walk; the five walks listed above have lengths 1, 2, 2, 4 and 4, respectively.

(where the edge connecting the vertex A to itself is the loop). The walk
{A,A}
is then a cycle, but not a path.
Here we have removed the vertex D (and the edges which were connected to it), and thereby disconnected the graph into two disjoint graphs. In this graph, E is also a cut point.
Here we have removed the bridge edge {D,E}. In this graph, {E,F} and {E,G} are also bridge edges. Notice that every bridge edge has a cut point at (at least) one end.
The Internet (or any network) can be represented as a (very complex) graph: the vertices represent the routers (computers responsible for passing data through the network) and the edges represent the communications links (wires, fiber optic cables, satellite links, etc.) over which data travels. The presence of cut points or bridge edges in a network graph indicates a lack of fault tolerance: failure of the router at a cut point or failure of the link over a bridge edge disconnects the network and prevents data from passing through it.
There are two useful ways to measure distance in graphs. We define the distance between two vertices as the length of the shortest path between them. In the graph
the following paths exist between the vertices A and E:

• A, B, C, D, E
• A, B, D, E
• A, C, D, E
• A, D, E

These have lengths of 4, 3, 3 and 2, respectively, and so the distance between A and E is 2. This notion of distance will be important when you learn about routing in networks (where the shortest path is usually the fastest path).

we need in principle find the shortest path for every pair of vertices in the graph; the longest of these will be the diameter of the graph. Even with a graph as relatively small as this one, this can be a time consuming algorithm. Fortunately, we can apply the following heuristic (an intuitive simplification):
the most distant vertices in a graph will be on opposite sides of cut points or bridge edges, if any exist.
Hence in this case, we need only concern ourselves with paths connecting A, B or C with F or G:

• A, B, C, D, E, F
• A, B, C, D, E, G
• A, C, D, E, F
• A, C, D, E, G
• A, D, E, F
• A, D, E, G
• B, A, C, D, E, F
• B, A, C, D, E, G
• B, A, D, E, F
• B, A, D, E, G
• B, C, A, D, E, F
• B, C, A, D, E, G
• B, C, D, E, F
• B, C, D, E, G
• C, A, D, E, F
• C, A, D, E, G
• C, B, A, D, E, F
• C, B, A, D, E, G
• C, D, E, F
• C, D, E, G

The shortest path between A and F (or G) has length 3 (ie., A, D, E, F); the shortest path between B and F (or G) has length 4 (ie., B, C, D, E, G), and the shortest path between C and F (or G) has length 3 (ie., C, D, E, F). The longest of these is 4, and therefore the diameter of this graph is 4. Graph diameters are important when discussing collision domains in Ethernet.

### Types of Graphs

Graphs can be categorized in a number of ways: