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?

  • 1
    $\begingroup$ 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. $\endgroup$ – JiK Dec 17 '14 at 7:50

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.