Let $G$ be a connected graph with $e$ edges and $v$ vertices. I need to show that the maximal number of edges that can be removed so that the graph is still connected is $e-v+1$.
First attempt: Tried to do it by induction. In the case where $v=2$ we obviously can remove $e-1$ edges, and hence it is true that $e-v+1=e-1$ (replacing $v=2$ shows it is true). So then I supposed it was true for $n$ and tried to finish the proof but I am failing to see how can we use the inductive hypothesis.
Other attempt: Let us have $k$ vertices and begin with the first one, say $k_1$. Then if it is connected to say, other $m$ vertices, remove each edge that connects to some vertex more than once. Then move to any other vertex that is connected to the previous one and do the same thing again. Now for the next one, repeat and also remove any edge that connects you to the first vertex. For the fourth one the same, and so on until you go through all the vertices. Just did plenty of examples and it worked for all of them, but of course I would need some formal proof on this procedure.
How would you prove it? Thanks in advance!
Best Answer
The following is a hint for formalizing your second method:
HINT: If $G$ is connected, the minimal connected subgraph (in terms of number of edges) of $G$ is its spanning tree. And a simple graph is a tree iff $e = v-1$.
Note also that trees have a property that removal of any edge makes them disconnected. This is what I meant by "minimal connected subgraph" above.