proc(G : Graph)
  name Graph::bipartite;
  local visitedSet, partOne, partTwo, bipart, _color, vertex, v, _adjacentEdges\
, output, _vertices, toSearch, setToDo, setOne, setTwo;
begin
  output := hold(Bool);
  if 1 < args(0) then
    case args(2)
      of hold(Bool) do
        break
      of hold(Lists) do
        output := hold(Lists);
        break
      otherwise
        error(message("symbolic:graph:InvalidArgumentDefinition"))
    end_case
  end_if;
  bipart := TRUE;
  _vertices := Graph::getVertices(G);
  if nops(_vertices) = 0 then
    error(message("symbolic:graph:GraphHasNoVertices"))
  end_if;
  vertex := op(_vertices[1]);
  toSearch := {op(_vertices)} minus {vertex};
  visitedSet := {vertex};
  _color[vertex] := 1;
  setOne := 1;
  setTwo := 0;
  setToDo := {};
  while not nops(visitedSet) = 0 do
    visitedSet := visitedSet minus {vertex};
    _adjacentEdges := {op(Graph::getAdjacentEdgesLeaving(G, [vertex]))};
    if nops(_adjacentEdges) = 0 then
      if contains(_color, vertex) = FALSE then
        setToDo := setToDo union {vertex}
      end_if
    else
      if contains(_color, vertex) = FALSE then
        if setOne < setTwo then
          _color[vertex] := 1;
          setOne := setOne + 1
        else
          _color[vertex] := 2;
          setTwo := setTwo + 1
        end_if
      end_if
    end_if;
    for v in _adjacentEdges do
      if contains(_color, v) = FALSE then
        _color[v] := _color[vertex] + 1;
        if _color[v] mod 2 = 1 then
          setOne := setOne + 1
        else
          setTwo := setTwo + 1
        end_if;
        visitedSet := visitedSet union {v};
        toSearch := toSearch minus {v}
      else
        if _color[v] = _color[vertex] then
          bipart := FALSE
        end_if
      end_if
    end_for;
    if nops(visitedSet) = 0 then
      if 0 < nops(toSearch) then
        vertex := op(toSearch, 1);
        visitedSet := {vertex};
        toSearch := toSearch minus {vertex}
      end_if
    else
      vertex := op(visitedSet, 1)
    end_if
  end_while;
  for v in setToDo do
    if contains(_color, v) = FALSE then
      if setOne < setTwo then
        _color[op(v)] := 1;
        setOne := setOne + 1
      else
        _color[op(v)] := 2;
        setTwo := setTwo + 1
      end_if
    end_if
  end_for;
  if output = hold(Bool) then
    bipart
  else
    if bipart = TRUE then
      partOne := {};
      for v in _vertices do
        if _color[v] mod 2 = 0 then
          partOne := partOne union {v}
        end_if
      end_for;
      partTwo := {op(_vertices)} minus partOne;
      [sort([op(partOne)]), sort([op(partTwo)])]
    else
      FAIL
    end_if
  end_if
end_proc