Connected Graph and Cycle

Question

Show that from a simple connected undirected graph on $n$ vertices and having $m$ edges, one can always pick $m-n+1$ edges in such a way that at least one edge is picked from every cycle in the graph.

This question I have faced during my preparation for M.Tech.I have tried a lot but have no idea, how to go further.Please if possible help me to solve this question. I think connected graph results and Pigeon-hole Principle can help me to solve.

My attempt, Since the graph is connected, $m \geq n -1$ as $\omega(G)=1 $. This implies $m-n+1 \geq 0$.

Next how can I move ?

Answer 1

If you remove $m-n+1$ edges, there will be $n-1$ edges left, so the graph, if still connected, will be a tree. So, just remove edges from cycles, one after another. Removing an edge from a cycle doesn't disconnect the graph, so you have a tree at the end. Since a tree is acyclic, you've removed an edge from each cycle. Maybe I should say that a connected graph with more than $n-1$ edges is not a tree, so there's always a cycle available until you get to the end.

Answer 2

Notice that a spanning tree has $n-1$ edges. So the idea is really to consider the complement of a spanning tree, which has $m-(n-1) = m-n+1$ edges.

Consider a subgraph $T$ induced set of $n-1$ edges from the graph $G$. WLOG, we may assume $T$ is connected, and therefore a tree. Let $C$ be a cycle in $G$. Now suppose to the contrary that $E(G) \setminus E(T)$ contains no edge on $C$. Then $C$ is a subgraph of $T$, contradicting the assumption that $G$ is a tree.