I reckon that the graphs that can be colored using only two colors are bi-partite. Now, if we talk about a graph:
- suppose it is not a bi-partite graph...and we wanna see it through dfs..
if it's not bi-partite then the following image condition will be available in the graph atleast once:
so as we reach any vertex amongst those and mark it with a color, and reach any other vertex and then other vertex then there surely will be a color contradiction (two adjacent vertices with the same color)
hence this will give the result as false.
- since if the graph is not bipartite then it would cause a color contradiction and vice versa...hence if there's no color contradiction it is going to be a bipartite graph.
Am I thinking it the right way? or Am I missing out on something?
Indeed, a graph is bipartite if and only if it is 2-colorable (there's more ways to characterize it: here ).
Note that your condition (a triangle in the graph) is not the only possible failure case, as any cycle of odd length makes the graph non bipartite. Nonetheless, a dfs that assigns colors to nodes and fails if it sees a conflict will detect if a graph is bipartite or not when "walking" on such a cycle.
@dp_1 How about this way:
Suppose if every edge in the graph has its vertices of different color...then it's a bipartite graph cause we can look at it by keeping ones of the same color at one side and another...
Now since we are checking for every single edge present in the graph through dfs...we will get to know if there's actually a color conflict or not....if there is, implies non partite else it is bi partite.
Yep, that works!