Comparing Graphs

After completing this section, you should be able to:

1. Identify the characteristics used to compare graphs.
2. Determine when two graphs represent the same relationships
3. Explore real-world examples of graph isomorphisms
4. Find the complement of a graph

In arithmetic, when two numbers have the same value, we say they are equal, like ½ = 0.5. Although ½ and 0.5 look different, they have the same value, because they are assigned the same position on the real number line. When do we say that two graphs are equal?

shows Graphs A and F, which are identical except for the labels. Graphs are visual representations of connections. As long as two graphs indicate the same pattern of connections, like Graph A and Graph F, they are considered to be equal, or in graph theory terms, isomorphic.

Two graphs are isomorphic if either one of these conditions holds:

1. One graph can be transformed into the other without breaking existing connections or adding new ones.
2. There is a correspondence between their vertices in such a way that any adjacent pair in one graph corresponds to an adjacent pair in the other graph.

It is important to note that if either one of the isomorphic conditions holds, then both of them do. When we need to decide if two graphs are isomorphic, we will need to make sure that one of them holds. For example, shows how Graph T can be bent and flipped to look like Graph Z, which means that Graphs T and Z satisfy condition 1 and are isomorphic.

Also, notice that the vertices that were adjacent in the first graph are still adjacent in the transformed graph as shown in . For example, vertex 3 is still adjacent to vertex 4, which means they are still neighboring vertices joined by a single edge.

Verifying that two graphs are isomorphic can be a challenging process, especially for larger graphs. It makes sense to check for any obvious ways in which the graphs might differ so that we don’t spend time trying to verify that graphs are isomorphic when they are not. If two graphs have any of the differences shown in , then they cannot be isomorphic.

Isomorphic graphs that represent the same pattern of connections can look very different despite having the same underlying structure. The edges can be stretched and twisted. The graph can be rotated or flipped. For example, in , each of the diagrams represents the same pattern of connections.

Looking at , how can we know that these graphs are isomorphic? We will start by checking for any obvious differences. Each of the graphs in has four vertices and five edges; so, there are no differences there. Next, we will focus on the degrees of the vertices, which have been labeled in .

As shown in , each graph has two vertices of degree 2 and two vertices of degree 3; so, there are no differences there. Now, let’s check for cyclic subgraphs. These are highlighted in .

As shown in , each graph has two triangles and one quadrilateral; so, no differences there either. It is beginning to look likely that these graphs are isomorphic, but we will have to look further to be sure.

To know with certainty that these graphs are isomorphic, we need to confirm one of the two conditions from the definition of isomorphic graphs. With smaller graphs, you may be able to visualize how to stretch and twist one graph to get the other to see if condition 1 holds. Imagine the edges are stretchy and picture how to pull and twist one graph to form the other. If you can do this without breaking or adding any connections, then the graphs are really the same. demonstrates how to change graph A₄ to get A₃, graph A₃ to get A₂, and graph A₂ to get A₁.

Now that we have used visual analysis to see that condition 1 holds for graphs A₁, A₂, A₃, and A₄ in , we know that they are isomorphic. In , one of the edges of graph A₄ crossed another edge of the graph. By transforming it into graph A₃, we have “untangled” it. Graphs that can be untangled are called planar graphs. The complete graph with five vertices is an example of a nonplanar graph-that means that, no matter how hard you try, you can’t untangle it. But, when you try to figure out if two graphs are the same, it can be helpful to untangle them as much as possible to make the similarities and differences more obvious.

Condensed — the full section is in OpenStax Contemporary Mathematics.

When two graphs are isomorphic, meaning they have the same structure, there is a correspondence between their vertices, which can be named by listing corresponding pairs of vertices. This list of corresponding pairs of vertices in such a way that any adjacent pair in one graph corresponds to an adjacent pair in the other graph is called an isomorphism. Consider the isomorphic graphs in . In , we could replace the labels Graph F with the labels from Graph A and have an identical graph, as in .

So, we can identify an isomorphism between Graph A and Graph F by listing the corresponding pairs of vertices: b-g, c-h, d-i, and e-j. Notice that b is adjacent to c and g is adjacent to h. This must be the case since b corresponds to g and c corresponds to h. The same is true for other pairs of adjacent vertices.

An isomorphism between graphs is not necessarily unique. There can be more than one isomorphism between two graphs. We can see how to form a different isomorphism between Graph A and Graph F from by rotating Graph F clockwise and comparing the rotated version of F to Graph A as in YOUR TURN 12.13. Now, we can see that a second isomorphism exists, which has the correspondence: b-j, d-h, c-i, and e-g as shown in .

Condensed — the full section is in OpenStax Contemporary Mathematics.

Suppose that you are a camp counselor at Camp Woebegone and you are holding a camp Olympics with four events. The campers have signed up for the events. You drew a graph in to help you visualize which events have campers in common.

Graph E in shows that some of the same campers will be in events a and b, as well as b and d, c and d, and a and c. What do you think the graph would look like that represented the events that do not have campers in common? It would have the same vertices, but any pair of adjacent edges in Graph E, would not be adjacent in the new graph, and vice versa. This is called a complementary graph, as shown in . Two graphs are complementary if they have the same set of vertices, but any vertices that are adjacent in one, are not adjacent in the other. In this case, we can say that one graph is the complement of the other.

One way to find the complement of a graph is to draw the complete graph with the same number of vertices and remove all the edges that were in the original graph. Let’s say you wanted to find the complement of Graph E from , and you didn’t already know it was Graph F. You could start with the complete graph with four vertices and remove the edges that are in Graph E as shown in .

Condensed — the full section is in OpenStax Contemporary Mathematics.

• Two graphs are isomorphic if they have the same structure.
• When graphs are relatively small, we can use visual inspection to identify an isomorphism by transforming one graph into another without breaking connections or adding new ones.
• An isomorphism between two graphs preserves adjacency.
• If two graphs differ in number of vertices, number of edges, degrees of vertices, or types of subgraphs, they cannot be isomorphic.
• When the complements of two graphs are isomorphic, so are the graphs themselves.