
Post by vsiap on Dec 13, 2014 13:01:23 GMT
Suppose f:G_{1}>G_{2} is a graph isomorphism, and G_{1} is bipartite. We need to show that G_{2} is bipartite.
Let V_{1} and V_{2} be the vertex sets of G_{1} and G_{2}. G_{1} is bipartite means we can partition vertex set V_{1} into two disjoint sets X and Y, such that V_{1}=XUY, and such that every edge of G_{1} connects a vertex x of X with a vertex y of Y.
Now consider the subsets f(X) and f(Y) of V_{2}. Since f is a bijection from V_{1} to V_{2}, f(X) and f(Y) are disjoint and f(X)Uf(Y)=V_{2}.
Now consider two vertices w,z of V_{2}. If w and z both lie in f(X), then f^{1}(w) and f^{1}(z) both lie in X. Since G_{1} is bipartite, there is no edge between f^{1}(w) and f^{1}(z), since f preserves adjacencies, there is no edge between w and z in G_{2}. Similarly, if w and z both lie in f(Y), there is no edge between them.
Every edge of G_{2} connects a vertex of f(X) with a vertex of f(Y), so G_{2} is bipartite, with bipartition (f(X),f(Y)).

