I am trying to solve the Lemma provided in the title. So far I have the following:
To prove that contracting an edge e from a connected graph G results in a connected graph, I have to show that there exists a path in the obtained graph that touches every vertex.
Derived from a Theorem, we know that every connected graph contains a spanning tree. Hence, we only need to prove that this lemma holds for spanning trees.
Let e be an edge incident with vertices u and v in G so that uev1…v is a path. If e is not on the path between the vertices u and v, then e is not on the path between vertices u and v in G'. Hence contracting the edge e would not end in a disconnected graph.
Let e be on the path. Then, by contracting e from G, the vertices incident with e, namely u and v, will merge together and create a new vertex, w. Since a new vertex was created, there exists a new path including the new vertex w. Hence, G is connected. (In fact, this process can be repeated until only one vertex and no edges exist since edge never ends in loss of connectivity).
Did I miss anything or is something not clear?
Any feedbacks or suggestions for improvement are very much appreciated. Thank youuu
Best Answer
The proof overall has the right ideas but the presentation can be improved.
How are you defining a path? If you require all the vertices in a path to be distinct, then this is not what you have to prove. It is even false. There is no path that touches every vertex in the tree with the edge-set 12, 23, 24.
What you want to prove is that there is a path between any two vertices in the contraction.
You continue with
We the readers of your proof do not know which Theorem you are referring to. A month, or a year from now if you re-read your proof, you might not know either!
Continuing with the same paragraph,
You are not making use of any special property of spanning trees in your proof. That entire paragraph is unnecessary because your proof is equally valid on all connected graphs.
you could say "Let $e = uv$".
When you say
it's not clear what this path is. You are using $u$, $e$ and $v$ in your path, so it's a mix of symbols that represent different things. You could say "Let $p$ be a path between $u$ and $v$. If $e\notin p$ then (...) and if $e\in p$ then (...).
When you say
we do not know what $G'$ is. You might have defined somewhere (e.g. in class) what $G'$ stands for, but we the readers do not know that. The standard notation is $G/e$.
The entire statement
has nothing to do with $e$ not being on a certain path between $u$ and $v$. By the definition of contraction $e$ doesn't exist in $G/e$ so it can never be in any path in $G/e$. What you wanted to say is that if there is a path $p$ between $u$ and $v$ in $G$ such that $e$ is not on it, then $p$ remains a path between $u$ and $v$ in $G/e$.
Why is this new path relevant?
That is our initial assumption, we know that. You meant $G/e$ is connected. How does that follow from the existence of this new path introduced above?
This observation is correct but is not relevant for the proof, so it shouldn't be included in the proof, but after it.