From my lecture notes, “two graphs G and G′ are isomorphic if there is a one-to-one mapping φ: V (G) → V (G′) that preserves
edge relationships i.e. uv ∈ E(G) ↔ φ(u)φ(v) ∈ E(G′)”. What does this mean by when two graphs are isomorphic? Does it mean that two such graphs are the same but the orientation is different?
The lectures notes also state that isomorphic graphs can be shown by the following:
1. By labeling vertices and checking neighbors.
2. By explicitly constructing isomorphism φ.
3. By using adjacency matrices.
I somewhat understand the first method, but I still find it confusing. How can I use these methods to show whether two graphs are isomorphic or not isomorphic?
In: 7
>What does this mean by when two graphs are isomorphic? Does it mean that two such graphs are the same but the orientation is different?
It means the graphs have the same structure – not just orientation – you can move the vertices around and have the edges trace different routes to the vertices they join, and the graphs are still isomorphic.
A graph is often thought of as a bunch of edges joining a bunch of vertices, but it’s really just the abstract structure: There’s a bunch of “things”, and they “connect” pairs of other “things”. The first things we call edges, and the other things we call vertices.
If you have two graphs, and you somehow find a way to label them, and then note: “look, in this graph, vertex A is connected to B, C, F and W; and in the other graph, it’s the same! And the two graphs have the same connections, no matter what label we focus on!” then you’ve proved isomorphism. Technically, you’ve explicitly constructed an isomorphism from each to a third graph, whose vertices *are* the labels, and whose edges are pairs of vertices deemed to be “connected”.
You can cut out the middle man, so to speak. Imagine these two graphs:
* “The vertices are {0,1,2,3}, and two vertices are connected only if their sum is odd.”
* “The vertices are the corners of a square ABCD, and the edges are the sides.”
Then you could construct the map φ with φ(1) = A, φ(2)=B, φ(3)=C and φ(4)=D, and then go to the trouble of proving somehow that for any numbers x and y in {0,1,2,3}, x+y is odd if and only if φ(x)φ(y) is an edge of the square.
Latest Answers