public static boolean checkBipartite(Graph graph) throws Exception {
		// get all vertices
		ArrayList<Vertex> vertices = graph.getVertices();
		// pick an initial color
		Color initialColor = Color.BLACK;
		// get initial vertex
		Vertex initialVertex = vertices.get(0);
		// paint initial vertex with initial color
		initialVertex.setColor(initialColor);
		// paint initial vertex neighbors
		for (Vertex neighbour : initialVertex.getNeighbours()) {
			neighbour.setColor(Color.RED);
		}
		// get first unpainted neighbor which has a painted neighbor
		Pair pair = graph.getUnpaintedNeighbour();
		while (pair != null) {
			Vertex vertexToPaint = (Vertex) pair.getLeft();
			Color colorToPaintVertex = (Color) pair.getRight();
			GraphLogger.getLogger().info(
					"Current pair :" + vertexToPaint.getLabel() + ","
							+ colorToPaintVertex.toString());

			vertexToPaint.setColor((Color) pair.getRight());

			for (Vertex neighbour : vertexToPaint.getNeighbours()) {
				if (neighbour.getColor() == null) {
					neighbour.setColor((Color) pair.getRight());
				}
			}
			pair = graph.getUnpaintedNeighbour();
		}

		for (Vertex item : graph.getVertices()) {
			for (Vertex neighbour : item.getNeighbours()) {
				System.out.println(item.getLabel() + " " + item.getColor()
						+ "------" + neighbour.getLabel() + " "
						+ neighbour.getColor());
				if (item.getColor().equals(neighbour.getColor())) {
					return false;
				}
			}
		}

		return true;
	}