educative.io

All Directed Acyclic Graphs need not be bipartite

Courses
,
#1

This page seems to have 2 errors
“All the cycle graphs, i.e graphs that consist of a single cycle, or some number of vertices (at least 3) connected in a closed chain, are bipartite”
This is only possible in case of even nodes.

DAGs have been mentioned as type of bipartite graph
Seems incorrect on the basis of question “795923” on math.stackexchange (not allowed to add link)

Course: https://www.educative.io/collection/5642554087309312/5724822843686912
Lesson: https://www.educative.io/collection/page/5642554087309312/5724822843686912/5714270310367232

#2

Agree. How can a connected triangle be bipartite?

#3

Hi @Peeyush, Welcome to the Discuss community!

Yes, you are right. All cyclic graphs are not bipartite. Only the even nodes of a cyclic graph can be formed into a bipartite graph. The note has been removed.

However, for the second point, All the undirected acyclic graphs are bipartite. The example of an acyclic graph given in the lesson was not bipartite. The example has been changed, and the content has been updated.

Thanks for identifying.