Question:
Suppose I have a graph with $n$ edges and the number of vertices is unknown, what is the minimum number of edges I need to remove in order to make sure any graph with $n$ edges will no longer contain any odd-length cycles?
For instance, if $n=3$, then the minimum number of edges I will have to remove is $1$. This is because for $n=3$, the only graph that will have an odd-length cycles is a triangle, in which case I can just remove one of the edges to make such graph odd-length-cycles free.
I hope my questions make sense so far.
My thoughts and 'reasoning':
I had some thoughts regarding this problem and I tempted to say the minimum edges I need to remove is $\frac{n}{3}$ in order for any graph with $n$ edges odd-length-cycles free.
This is because I think the most odd-length cycles a graph with $n$ vertices can make is $n \choose 3$ and if there are two odd-length cycles that share an edge, we can just delete that edge to remove these two cycles at once. So I think the problem just reduces to the fact that a graph with $n$ edges can make at most $\frac{n}{3}$ disjoint triangles? Hence if I can remove an edge from each disjoint triangle then I will be done?
I know that my argument is very likely to be incorrect but how should one approach this problem?
I do not have a very deep background in graph theory. Many thanks in advance!
Best Answer
A graph with no odd cycles is called a bipartite graph because the vertex set of such a graph can be partitioned into two sets $V_1$ and $V_2$ so that every edge has one endpoint in $V_1$ and the other in $V_2$.
Proposition. Any graph $G=(V,E)$ has a bipartite subgraph which contains at least half the edges of $G$. (In other words, if $G$ has $n$ edges, then $G$ can be made bipartite by removing at most $n/2$ edges.)
[P.S. A comment by user Paralyzed_by_Time provided references for this observation: Paul Erdős, Ralph Faudree, János Pach, and Joel Spencer, How to make a graph bipartite, J. Combin. Theory Ser. B 45 (1988), 86–98 and (apparently the original reference) P. Erdős, On some extremal problems in graph theory, Israel J. Math. 3 (1965), 113–116.]
Proof. Partition $V$ into two sets $V_1,V_2$ in a way that maximizes the number of edges that cross between $V_1$ and $V_2$. Note that each vertex has at least as many neighbors on the other side of the partition as on its own side; otherwise moving $v$ to the other side would increase the number of cross-edges, contradicting the assumed maximality of the partition. From this it easily follows that at least half the edges of $G$ cross between $V_1$ and $V_2$, i.e., the bipartite graph with those edges contains at least half the edges of $G$.
In general we can't do too much better than delete half the edges, because of the following example. The complete graph $K_t$ has $n=\binom t2=\frac{t^2-t}2$ edges, and its largest bipartite subgraph has $\lceil\frac t2\rceil\cdot\lfloor\frac t2\rfloor=\lfloor\frac{t^2}4\rfloor$ edges, so we have to delete almost half the edges of $K_t$ to get a bipartite graph.