We’ve seen that functions allow us to bound the size of a set in relation to another set. However, we can also use functions to relate their structure as well.
An isomorphism between two graphs $G_1 = (V_1,E_1)$ and $G_2 = (V_2,E_2)$ is a bijection $f:V_1 \to V_2$ which preserves adjacency. That is, for all vertices $u,v \in V_1$, $(u,v) \in E_1$ if and only if $(f(u),f(v) \in E_2$. Two graphs $G_1$ and $G_2$ are isomorphic if there exists an isomorphism between them, denoted $G_1 \cong G_2$.
In other words, we consider two graphs to be the “same” or equivalent if we can map every vertex to the other graph such that the adjacency relationship is preserved. Isomorphisms are a special subclass of functions called homomorphisms that preserve structure. Isomorphisms are bijective homomorphisms.
In practice, what an isomorphism does amounts to a “renaming” of the vertices, and this is what we typically mean when we say that two objects are isomorphic. You will also hear the phrase same/equal “up to isomorphism”. For graphs, this really means that the edge relationships are preserved.
Consider the following graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$.
We will show that these two graphs are isomorphic by defining a bijective function $\varphi:V_1 \to V_2$ which preserves adjacency: \begin{align*} \varphi(0) &= h & \varphi(1) &= d & \varphi(2) &= b & \varphi(3) &= f \\ \varphi(4) &= c & \varphi(5) &= g & \varphi(6) &= e & \varphi(7) &= a \end{align*} This is a bijection, since every vertex in $V_1$ is paired with a vertex in $V_2$. We then verify that this bijection preserves adjacency by checking each edge under the bijection: \begin{align*} (\varphi(4),\varphi(1)) &= (c,d) & (\varphi(4),\varphi(2)) &= (c,b) & (\varphi(4),\varphi(3)) &= (c,f) \\ (\varphi(5),\varphi(0)) &= (g,h) & (\varphi(5),\varphi(2)) &= (g,b) & (\varphi(5),\varphi(3)) &= (g,f) \\ (\varphi(6),\varphi(0)) &= (e,h) & (\varphi(6),\varphi(1)) &= (e,d) & (\varphi(6),\varphi(3)) &= (e,f) \\ (\varphi(7),\varphi(0)) &= (a,h) & (\varphi(7),\varphi(1)) &= (a,d) & (\varphi(7),\varphi(2)) &= (a,b) \end{align*}
So an obvious and fundamental problem that arises from this definition is: Given two graphs $G_1$ and $G_2$, are they isomorphic? The obvious answer is that we just need to come up with an isomorphism or show that one doesn’t exist. Unfortunately, there are $n!$ possible such mappings we would need to check.
There are a few ways we can rule out that graphs aren’t the same, via properties that we call isomorphism invariants. There are properties of the graph that can’t change via an isomorphism, like the number of vertices or edges in a graph.
One invariant that is not as obvious is the degree list of a graph. This is a list of all the degrees of the vertices. Clearly, if this list is different (say, one graph contains a vertex of degree 5 and the other doesn’t), then the graphs are not isomorphic.
Consider the following two graphs, $G_1$ on the left and $G_2$ on the right.
First, we observe that both graphs have 6 vertices and and 9 edges and all vertices in both graphs have degree exactly 3. However, observe that the vertex set of $G_1$ can be divided into two sets in such a way that edges are adjacent to exactly one vertex from each set. However, $G_2$ contains two triangles. The existence of a triangle is enough to prevent us from partitioning the vertices into two in the same way as in the first graph.
The property that the vertex set can be partitioned so that edges travel only between vertices in different partitions can be defined formally.
A graph $G = (V,E)$ is bipartite if $V$ is the disjoint union of two sets $V_1$ and $V_2$ such that all edges in $E$ connect a vertex in $V_1$ with a vertex in $V_2$. We say that $(V_1, V_2)$ is a bipartition of $V$.
Taking $G_1$ from the last example and labelling the vertices, we have
A bipartition for this graph is $(\{0,1,2\}, \{3,4,5\})$.
The graph isomorphism problem is the problem of determining whether two given graphs $G_1$ and $G_2$ are isomorphic.
A natural impulse when presented with a bunch of circles joined by lines is to see if we can get from one circle to another by following the lines. More formally, when we do this, what we’re doing is checking if an object is connected to another object. It’s not surprising to learn that this is a fundamental property of graphs that we’d like to work with.
A walk of length $k$ is a sequence of $k+1$ vertices $v_0, v_1, \cdots, v_k$ such that $v_{i-1}$ and $v_i$ are adjacent for $1 \leq i \leq k$—in other words, $(v_{i-1},v_i) \in E$. This walk has length $k$ because it contains $k$ edges. A path is a walk without repeated vertices and edges—that is, if $i \neq j$, then $v_i \neq v_j$.
We say a closed walk is a walk that begins and ends at the same vertex. A cycle is a closed walk with distinct vertices and edges except for the beginning and end vertices.
Some notes on edge cases.
Consider the following graph.
We can see:
Here is a simple theorem about walks and paths and how the fastest way between point $a$ and $b$ is a straight line.
Let $G$ be a graph and $u,v \in V$ be vertices. If there is a walk from $u$ to $v$, then there is a path from $u$ to $v$.
Consider the minimum length walk $u = v_0 v_1 \cdots v_k = v$ from $u$ to $v$. Suppose that this walk contains a vertex that is repeated. In other words, there exist $i, j$ with $i \lt j$ such that $v_i = v_j$. Then we can create a shorter walk $$u = v_0 v_1 \cdots v_{i-1} v_i v_{j+1} v_{j+2} \cdots v_k = v,$$ since $(v_i,v_{j+1}) = (v_j,v_{j+1})$. This contradicts the minimality of the length of our original walk. So there are no repeated vertices in our walk and therefore, it is a path by definition.
One question we can ask is what counts as a distinct cycle. For instance, in our example above, $4, 2, 5, 10, 4$ is a cycle and $1, 4, 2, 5, 1$ is a different cycle, but is $2, 4, 10, 5, 2$ a different cycle from the first one we described? Though our description (the sequence of vertices) is not the same, intuitively, it seems like we’ve described the same cycle.
To try to capture this notion, we’ll give an alternative definition for cycles via the notion of subgraphs.
A graph $G' = (V',E')$ is a subgraph of a graph $G = (V,E)$ if $V' \subseteq V$ and $E' \subseteq E$.
Consider again the following graphs.
We observed before that these two graphs are not isomorphic because the graph on the left is bipartite and the graph on the right is not bipartite because of the triangles it contains. Now, using the language of subgraphs and isomorphism, we can say this more formally: the graph contains a subgraph ismorphic to $C_3$ (or $K_3$).
The subgraph isomorphism problem asks whether given graphs $G$ and $H$ whether there is a subgraph of $G$ that is isomorphic to $H$. This problem is known to be hard to solve: it’s NP-complete, which means that if we have a solution for the problem, we can check it efficiently, but we have no efficient algorithms for solving it. It’s not hard to see that graph isomorphism is a special case of subgraph isomorphism.
The notions of isomorphism and subgraph give us an alternative definition for a cycle in a graph.
A cycle of a graph $G$ is a subgraph of $G$ that is isomorphic to the cycle graph $C_n$ for some $n \geq 3$.
Recall the graph from Example 19.8. It’s clear that the cycles $0, 4, 1, 5, 0$ and $1, 4, 0, 5, 1$ form the same subgraph. However, the cycle $5, 0, 1, 4, 5$, while defined on the same vertex, forms a different subgraph because we take different edges, so this would be considered a different cycle.
What does it mean if there’s a walk between two vertices? Practically speaking, it means that we can reach one from the other. This idea leads to the following definition.
A graph $G$ is connected if there is a walk between every pair of vertices.
The graphs that we’ve seen so far have mostly been connected. However, we’re not guaranteed to work with connected graphs, especially in real-world applications. In fact, we may want to test the connectedness of a graph. For that, we’ll need to talk about the parts of a graph that are connected.
A connected component of a graph $G = (V,E)$ is a connected subgraph $G'$ of $G$ that is not a proper subgraph of another connected subgraph of $G$.
Here, we use “proper” in the same way as “proper subset”—since a graph can be a subgraph of itself, a proper subgraph is a subgraph that is not the graph itself.
Consider the following graph.
This graph has two connected components, the subgraphs induced by $\{0,\dots, 5\}$ and $\{6,\dots,9\}$. No other can be considered a connected component since they would either be not connected or a proper subgraph of one of the two connected components we identified.