I think I am having a hard time understanding the corresponding relation between vertices in two graphs. I need to have some conceptual interpretation about this topic.
From what I know so far, I know in order to prove two graphs are isomorphic, we need to firstly show that:
- they have same number of vertex.
- the degree sequences are equal in both graphs.
What I don't understand is this:
-
Suppose we have a degree sequence like 4 3 3 3 2 2 in two graphs G and H, is it mandatory for the vertex with degree 4 in G always mapped to the vertex with 4 in H? In other words, is it possible for a vertex with degree 4 in G to be mapped to a vertex with degree 3 or 2 in H?
-
Suppose we have vertices like a->b in G, a has degree 4, and b has degree 3, but we can't find such pair of connection in H that satisfies the above connection relation, for example, in G, the connection is a(4)->b(3), but in H, we can only find 4->2->3, like there appears an extra node in the path that was supposed to be 4->3. But they have the same number of vertices, and same degree sequence as well. In this case, can two graphs be isomorphic?
Best Answer
First, 1. and 2. are necessary but not sufficient conditions for the existence of a graph isomorphism. If 1. and 2. hold, we cannot conclude that the graphs are isomorphic, but if 1 or 2 does not hold, we can conclude that they are not isomorphic. For your questions:
Yes, it is mandatory in this case that in any isomorphism between $G$ and $H$ that the (unique) 4 degree vertex be mapped to the (unique) 4 vertex. You can think of graph isomorphisms as preserving all properties of graphs that relate to adjacency (which is a lot). In particular, graph isomorphisms preserve order of vertices.
No they can't be isomorphic. Say there was an isomorphism $f:G\to H$. Then, $f(a)$ and $f(b)$ would be adjacent in $H$, while $f(a)$ and $f(b)$ have degrees 4 and 3 (isomorphisms preserve propreties relating to adjacency). But we assumed such a pair of vertices didn't exist in $H$.