I was going through Modern Graph Theory by Bollobas and this example on bipartite graph which states on the last line of page 6 that Figure I.1 is a bipartite graph.

Fig I.1

Fig I.1 has triangles as subgraph and triangle is not bipartite. Given the subgraphs of Fig I.1 is not bipartite, then Fig I.1 itself cannot be bipartite. Am I missing something/misunderstand the example?

  • 1
    $\begingroup$ The graph is tripartite (or $3$-partite), with vertex classes $\{1,3,5\}$, $\{2,4,6\}$, and $\{7,8,9\}$, so that's probably what Bollobas intended to write. $\endgroup$ – Andreas Blass Dec 5 '16 at 3:33

Yeah, it appears to be a typo.

enter image description here


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.