0
$\begingroup$

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 ?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.