The minimum size of an edge set that contains an edge of every cycle

Question

The question is like this:

There is a connected graph $G=(V,E)$ with $n$ vertices and $m$ edges such that $m \ge n$. Let's say that the graph has a spanning tree, meaning there is a tree $T$ such that $T = (V, E_t)$ and $E_t$ contained in $E$. Find the minimum size $k$ such that a set $F$ exists such that $F \subseteq E$ and these two conditions hold:

• $|F| = k$
• Every cycle in $G$ contains an edge in $F$.

My solution is like:

I know that $G$ has a spanning tree $T$. A tree has $n-1$ edges so for going from $G$ to $T$ i need to erase a set of edges (call it $F$) that their size is $m - (n - 1)$ so after i erase them i have a subgraph of $G$ that has $n-1$ edges as needed for it to be a tree.

Let's say that there is a cycle in $G$ that doesn't contain an edge in $F$ so after I erase $F$ from $G$ this cycle will remain as it was and that is a contradiction to the assumption that $T$ is a tree. So, as a result of the contradiction it means that $F$ has to be a set of edges that $|F| = k$ and also every cycle in $G$ contain a set in $F$, now we need to prove that $k$ is the minimum size of a set like this. (Comment: $k = m - (n-1)$)

Let's say $m - (n-1)$ is not the minimum size, so we have $k < m - (n - 1)$ such that $k$ is the size of a set $F$ that every cycle in $G$ contains a set in $F$. If we erase $F$ from $G$ we will get a subgraph $G_t$ which has $m - k$ edges so we can say that the number of edges in $G_t$ is bigger than $n-1$ and we know that the number of vertices is $n$.

Because $G$ is a connected graph and every edge that we erase is contained in a cycle in $G$, we can infer that $G_t$ is a connected graph. Because $G_t$ has more than $n-1$ edges and only $n$ vertices we can infer that $G_t$ is a connected graph that is not a tree and therefore $G_t$ has at least one cycle. If $G_t$ has a cycle, its obvious that there is a cycle in $G$ that does not contain an edge in $F$. Therefore every group of edges that has more than $m - (n-1)$ edges does not satisfy the conditions.

The question is about the last step, if I am erasing an edge of a cycle, couldn't it stay a cycle without the edge? (Maybe if its stays a cycle it means that there is a subcycle in $G$ that doesn't contain an edge in $F$ and a subcycle is a cycle and there is the answer).

Just want to make sure, and I already wrote all of this so I will post it maybe it will help other people who faced this question.

Answer 1

Your argument is solid. To summarize: a spanning tree $T$ of $G$ has $n-1$ edges, and this is the most edges that a graph without cycles can have.

• We can delete the $m-n+1$ edges of $G$ which are not in $T$, and that is a valid solution (there are no surviving cycles, so we must have deleted at least one edge from every cycle).
• If $F$ is a set of fewer than $m-n+1$ edges, then $G-F$ has at least $n$ edges left, so it has at least one cycle: a cycle disjoint from $F$. So no such set can be a valid solution.

Now, on to your concern: if we are erasing an edge of a cycle, could it stay a cycle without that edge?

Well, not the cycle of those exact vertices in that exact order. If you have a cycle with vertices $a,b,c,d,e$ and edges $ab,bc,cd,de,ea$, and you delete one of those edges, that's not a cycle anymore. You might, in general, have some related cycles:

• A cycle like $a,c,e,b,d$ with edges $ac, ce, eb, bd, da$ which has those vertices in a different order, so it uses different edges.
• A cycle like $a,b,c,e$ with edges $ab, bc, ce, ea$ which has most of the same vertices in the same order, but skips some, so some edges are different. (If you delete edge $cd$ or $de$ from the first cycle, this cycle survives.)

We don't have to care about that in this proof, because we make sure to delete an edge from every cycle. When we consider cycle $a,b,c,d,e$, we conclude that we've deleted an edge from that cycle. When we consider cycle $a,b,c,e$, we conclude that we've deleted an edge from that cycle, too. It might be the same edge, or a different one; we don't particularly care.