Return to Answer

A quick check with Mathematica seems to suggest that a (smallest) counterexample is given by a graph with 6 vertices and 13 edges:

(source)

Here the red edges are contained in the most odd cycles (16, 12, 6, 5, 2, 2, 1, 0 respectively) and one possible sequence of edge removals is shown. However, choosing different edges one can end up with a bipartite graph with 7 edges.

Edit: Any sequence of edge removals of the following graph with 8 vertices and 18 edges seems to result in a bipartite graph with at most 8 edges: (source)

Edit: For those interested: here's the Mathematica code to check that the last graph is really a counterexample.

Edit: The first complete graph for which the algorithm fails is the complete graph on 10 vertices. Indeed, it seems that the largest bipartite graph one can obtain from an $n$-vertex ($n>4$) complete graph is the complete bipartite graph on $(n-3)+3$ vertices, which has $3(n-3)$ edges, i.e. smaller than $n(n-1)/4$ for $n\geq 10$.

A quick check with Mathematica seems to suggest that a (smallest) counterexample is given by a graph with 6 vertices and 13 edges:

Here the red edges are contained in the most odd cycles (16, 12, 6, 5, 2, 2, 1, 0 respectively) and one possible sequence of edge removals is shown. However, choosing different edges one can end up with a bipartite graph with 7 edges.

Edit: Any sequence of edge removals of the following graph with 8 vertices and 18 edges seems to result in a bipartite graph with at most 8 edges:

Edit: For those interested: here's the Mathematica code to check that the last graph is really a counterexample.

Edit: The first complete graph for which the algorithm fails is the complete graph on 10 vertices. Indeed, it seems that the largest bipartite graph one can obtain from an $n$-vertex ($n>4$) complete graph is the complete bipartite graph on $(n-3)+3$ vertices, which has $3(n-3)$ edges, i.e. smaller than $n(n-1)/4$ for $n\geq 10$.

A quick check with Mathematica seems to suggest that a (smallest) counterexample is given by a graph with 6 vertices and 13 edges:

a sequence of edge removals http://www.nbi.dk/%7Ebudd/images/graphs2.png

Here the red edges are contained in the most odd cycles (16, 12, 6, 5, 2, 2, 1, 0 respectively) and one possible sequence of edge removals is shown. However, choosing different edges one can end up with a bipartite graph with 7 edges.

Edit: Any sequence of edge removals of the following graph with 8 vertices and 18 edges seems to result in a bipartite graph with at most 8 edges: a sequence of edge removals http://www.nbi.dk/%7Ebudd/images/graphs3.png

Edit: For those interested: here's the Mathematica code to check that the last graph is really a counterexample.

Edit: The first complete graph for which the algorithm fails is the complete graph on 10 vertices. Indeed, it seems that the largest bipartite graph one can obtain from an $n$-vertex ($n>4$) complete graph is the complete bipartite graph on $(n-3)+3$ vertices, which has $3(n-3)$ edges, i.e. smaller than $n(n-1)/4$ for $n\geq 10$.

A quick check with Mathematica seems to suggest that a (smallest) counterexample is given by a graph with 6 vertices and 13 edges:

(source)

Here the red edges are contained in the most odd cycles (16, 12, 6, 5, 2, 2, 1, 0 respectively) and one possible sequence of edge removals is shown. However, choosing different edges one can end up with a bipartite graph with 7 edges.

Edit: Any sequence of edge removals of the following graph with 8 vertices and 18 edges seems to result in a bipartite graph with at most 8 edges: (source)

Edit: For those interested: here's the Mathematica code to check that the last graph is really a counterexample.

Edit: The first complete graph for which the algorithm fails is the complete graph on 10 vertices. Indeed, it seems that the largest bipartite graph one can obtain from an $n$-vertex ($n>4$) complete graph is the complete bipartite graph on $(n-3)+3$ vertices, which has $3(n-3)$ edges, i.e. smaller than $n(n-1)/4$ for $n\geq 10$.

A quick check with Mathematica seems to suggest that a (smallest) counterexample is given by a graph with 6 vertices and 13 edges:

a sequence of edge removals http://www.nbi.dk/%7Ebudd/images/graphs2.png

Here the red edges are contained in the most odd cycles (16, 12, 6, 5, 2, 2, 1, 0 respectively) and one possible sequence of edge removals is shown. However, choosing different edges one can end up with a bipartite graph with 7 edges.

Edit: Any sequence of edge removals of the following graph with 8 vertices and 18 edges seems to result in a bipartite graph with at most 8 edges: a sequence of edge removals http://www.nbi.dk/%7Ebudd/images/graphs3.png

Edit: For those interested: here's the Mathematica code to check that the last graph is really a counterexample.

A quick check with Mathematica seems to suggest that a (smallest) counterexample is given by a graph with 6 vertices and 13 edges:

a sequence of edge removals http://www.nbi.dk/%7Ebudd/images/graphs2.png

Here the red edges are contained in the most odd cycles (16, 12, 6, 5, 2, 2, 1, 0 respectively) and one possible sequence of edge removals is shown. However, choosing different edges one can end up with a bipartite graph with 7 edges.

Edit: Any sequence of edge removals of the following graph with 8 vertices and 18 edges seems to result in a bipartite graph with at most 8 edges: a sequence of edge removals http://www.nbi.dk/%7Ebudd/images/graphs3.png

Edit: For those interested: here's the Mathematica code to check that the last graph is really a counterexample.

Edit: The first complete graph for which the algorithm fails is the complete graph on 10 vertices. Indeed, it seems that the largest bipartite graph one can obtain from an $n$-vertex ($n>4$) complete graph is the complete bipartite graph on $(n-3)+3$ vertices, which has $3(n-3)$ edges, i.e. smaller than $n(n-1)/4$ for $n\geq 10$.