Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Let Undir-Reachability be the following problem: given an undirected graph G and two specified vertices s and t in G, is there a path from s to t in G?
I need to prove that the 2-Colourability is in L, by knowing that Undir-Reachability belongs to the complexity class L.
I don't know how to start.
Hint: a graph is not bipartite if there is a walk of odd length from a vertex to itself.
