Graph theor 1.6 Isomorphism Two graphs that look the same might actually be different in a formal sense. For example the two graphs below are both cycles with 4 vertices A D But one graph has vertex set (A, B, C, D) while the other has vertex set (1, 2, 3, 4) If so, then the graphs are different mathematical objects, strictly speaking. But this is a frustrating distinction; the graphs look the same! Fortunately, we can neatly capture the idea of looks the same"and use that as our main notion of equivalence between graphs Graphs G1 and G2 are isomorphic if there exists a one-to-one correspondence between vertices in G1 and vertices in G2 such that there is an edge between two vertices in G1 if and only if there is an edge between the two corresponding vertices in G2. For example, take the following correspondence between vertices in the two graphs above A corresponds to 1 B corresponds to 2 D corresponds to 4 C corresponds to 3 Now there is an edge between two vertices in the graph on the left if and only if there is an edge between the two corresponding vertices in the graph on the right. Therefore, the two graphs are isomorphic. The correspondence itself is called an isomorphism Two isomorphic graphs may be drawn to look quite different. For example, here are two different ways of drawing Cs Isomorphic graphs share a great many properties, such as the number of vertices, number of edges, and the pattern of vertex degrees. Thus, two graphs can be provedGraph Theory 7 1.6 Isomorphism Two graphs that look the same might actually be different in a formal sense. For example, the two graphs below are both cycles with 4 vertices: A B D C 1 2 4 3 But one graph has vertex set {A, B, C, D} while the other has vertex set {1, 2, 3, 4}. If so, then the graphs are different mathematical objects, strictly speaking. But this is a frustrating distinction; the graphs look the same! Fortunately, we can neatly capture the idea of “looks the same” and use that as our main notion of equivalence between graphs. Graphs G1 and G2 are isomorphic if there exists a one­to­one correspondence between vertices in G1 and vertices in G2 such that there is an edge between two vertices in G1 if and only if there is an edge between the two corresponding vertices in G2. For example, take the following correspondence between vertices in the two graphs above: A corresponds to 1 B corresponds to 2 D corresponds to 4 C corresponds to 3. Now there is an edge between two vertices in the graph on the left if and only if there is an edge between the two corresponding vertices in the graph on the right. Therefore, the two graphs are isomorphic. The correspondence itself is called an isomorphism. Two isomorphic graphs may be drawn to look quite different. For example, here are two different ways of drawing C5: Isomorphic graphs share a great many properties, such as the number of vertices, number of edges, and the pattern of vertex degrees. Thus, two graphs can be proved