public int getMinimalCut(NonDirectedGraph<Integer> graph) {
        history = new LinkedHashMap<Vertex<Integer>, List<Vertex>>();
        while (graph.numVertices() > 2) {
            Edge<Integer> edge = getRandomEdge(graph);


            Vertex<Integer> remainingVertex = graph.getVertex(graph.numVertices() % 2 == 0 ? edge.getVertex2() : edge.getVertex1());
            //vertex to be removed
            Vertex<Integer> mergedVertex = graph.getVertex(graph.numVertices() % 2 == 0 ? edge.getVertex1() : edge.getVertex2());

            putToHistory(remainingVertex, mergedVertex);

            ArrayList<Edge<Integer>> mergedEdges = new ArrayList<Edge<Integer>>(mergedVertex.getEdges());
            for (int i = 0; i < mergedEdges.size(); i++) {
                Edge<Integer> mergedEdge = mergedEdges.get(i);
                while (graph.isEdge(mergedEdge.getVertex1(), mergedEdge.getVertex2())) {
                    //remove old edge
                    graph.removeEdge(mergedEdge.getVertex1(), mergedEdge.getVertex2());

                    Vertex<Integer> newVertex = mergedVertex.equals(mergedEdge.getVertex1()) ?
                            mergedEdge.getVertex2() : mergedEdge.getVertex1();

                    //don't allow self loops
                    if (!remainingVertex.equals(newVertex)) {
                        if (i % 2 != 0) {
                            graph.addEdge(remainingVertex, newVertex);
                        } else {
                            graph.addEdge(newVertex, remainingVertex);
                        }
                    }
                }
            }
            graph.removeVertex(mergedVertex);
        }
        return graph.getVertices().iterator().next().getEdges().size();
    }