diff --git a/src/algo/mod.rs b/src/algo/mod.rs
index aa54405..ab558a6 100644
--- a/src/algo/mod.rs
+++ b/src/algo/mod.rs
@@ -791,6 +791,60 @@
     Ok((distance, predecessor))
 }
 
+/// Return `true` if the graph is bipartite. A graph is bipartite if it's nodes can be divided into
+/// two disjoint and indepedent sets U and V such that every edge connects U to one in V. This
+/// algorithm implements 2-coloring algorithm based on the BFS algorithm.
+///
+/// Always treats the input graph as if undirected.
+pub fn is_bipartite_undirected<G, N, VM>(g: G, start: N) -> bool
+    where G: GraphRef + Visitable<NodeId=N, Map=VM> + IntoNeighbors<NodeId=N>,
+          N: Copy + PartialEq + std::fmt::Debug,
+          VM: VisitMap<N>
+{
+    let mut red = g.visit_map();
+    red.visit(start);
+    let mut blue = g.visit_map();
+
+    let mut stack = ::std::collections::VecDeque::new();
+    stack.push_front(start);
+
+    while let Some(node) = stack.pop_front() {
+        let is_red = red.is_visited(&node);
+        let is_blue = blue.is_visited(&node);
+
+        assert!(is_red ^ is_blue);
+
+        for neighbour in g.neighbors(node) {
+            let is_neigbour_red = red.is_visited(&neighbour);
+            let is_neigbour_blue = blue.is_visited(&neighbour);
+
+            if (is_red && is_neigbour_red) || (is_blue && is_neigbour_blue) {
+                return false;
+            }
+
+            /*
+            if is_red && is_neigbour_blue || is_blue && is_neigbour_red {
+                //good
+            }
+            */
+
+            if !is_neigbour_red && !is_neigbour_blue {
+                //hasn't been visited yet
+
+                match (is_red, is_blue) {
+                    (true, false) => { blue.visit(neighbour); },
+                    (false, true) => { red.visit(neighbour); },
+                    (_, _) => { panic!("Invariant doesn't hold"); }
+                }
+
+                stack.push_back(neighbour);
+            }
+        }
+    }
+
+    true
+}
+
 use std::fmt::Debug;
 use std::ops::Add;
 
diff --git a/tests/graph.rs b/tests/graph.rs
index a8e4097..a33977a 100644
--- a/tests/graph.rs
+++ b/tests/graph.rs
@@ -9,7 +9,7 @@
 use petgraph as pg;
 
 use petgraph::algo::{
-    dominators, has_path_connecting, is_cyclic_undirected, is_isomorphic_matching,
+    dominators, has_path_connecting, is_cyclic_undirected, is_isomorphic_matching, is_bipartite_undirected,
     min_spanning_tree,
 };
 
@@ -280,6 +280,77 @@
 }
 
 #[test]
+fn bipartite() {
+    {
+        let mut gr = Graph::new_undirected();
+        let a = gr.add_node("A");
+        let b = gr.add_node("B");
+        let c = gr.add_node("C");
+
+        let d = gr.add_node("D");
+        let e = gr.add_node("E");
+        let f = gr.add_node("F");
+
+        gr.add_edge(a, d, 7.);
+        gr.add_edge(b, d, 6.);
+
+        assert!(is_bipartite_undirected(&gr, a));
+
+        let e_index = gr.add_edge(a, b, 6.);
+
+        assert!(!is_bipartite_undirected(&gr, a));
+
+        gr.remove_edge(e_index);
+
+        assert!(is_bipartite_undirected(&gr, a));
+
+        gr.add_edge(b, e, 7.);
+        gr.add_edge(b, f, 6.);
+        gr.add_edge(c, e, 6.);
+
+        assert!(is_bipartite_undirected(&gr, a));
+    }
+    {
+        let mut gr = Graph::new_undirected();
+        let a = gr.add_node("A");
+        let b = gr.add_node("B");
+        let c = gr.add_node("C");
+        let d = gr.add_node("D");
+        let e = gr.add_node("E");
+
+        let f = gr.add_node("F");
+        let g = gr.add_node("G");
+        let h = gr.add_node("H");
+
+        gr.add_edge(a, f, 7.);
+        gr.add_edge(a, g, 7.);
+        gr.add_edge(a, h, 7.);
+
+        gr.add_edge(b, f, 6.);
+        gr.add_edge(b, g, 6.);
+        gr.add_edge(b, h, 6.);
+
+        gr.add_edge(c, f, 6.);
+        gr.add_edge(c, g, 6.);
+        gr.add_edge(c, h, 6.);
+
+        gr.add_edge(d, f, 6.);
+        gr.add_edge(d, g, 6.);
+        gr.add_edge(d, h, 6.);
+
+        gr.add_edge(e, f, 6.);
+        gr.add_edge(e, g, 6.);
+        gr.add_edge(e, h, 6.);
+
+        assert!(is_bipartite_undirected(&gr, a));
+
+        gr.add_edge(a, b, 6.);
+
+        assert!(!is_bipartite_undirected(&gr, a));
+    }
+}
+
+#[test]
 fn multi() {
     let mut gr = Graph::new();
     let a = gr.add_node("a");