# How can a bipartite simple graph be non isomorphic

From my understanding the bipartite graph is a graph that follows the red blue color scheme. If the graph fails the red blue color, then the graph is not bipartite.

But the question how do you test a bipartite graph that is non isomorphic?

Don't you need two graph to test for non-isomorphism?

• The question "how do you test a bipartite graph that is non isomorphic" does not seem to make sense. Why are you asking it, is this an exercise problem? If it is, then you probably have interpreted the it wrong. – JiK Dec 17 '14 at 7:50

## 1 Answer

It doesn't make sense to talk about an individual graph being non-isomorphic. Informally, two graphs are non-isomorphic if they are structurally different.

If we have two graphs $G_1$ and $G_2$, then if $G_1$ is bipartite and $G_2$ is not bipartite, then they are non-isomorphic. (I'm guessing this is the link between the two topics you've encountered.)

If they instead both happen to be bipartite, they may or may not be isomorphic. E.g. $C_8$ and $C_4 \cup C_4$ are two non-isomorphic bipartite graphs.

Graph isomorphism testing is a non-trivial problem, and is often practically solved computationally.