Proving a Tree is a Minimally Connected Graph in Graph Theory

[TheMathNoob]

Homework Statement

Let G be a connected graph. We say that G is minimally connected if the removal of any edge of G (without deleting any vertices) results in a disconnected graph. (a) Show that a connected, minimally connected graph has no cycles. (b) Show that a connected graph with no cycles is minimally connected. Commentary: The exercise shows that the two conditions are equivalent. A graph satisfying either condition is a tree.

Homework Equations

The Attempt at a Solution

I approach this by proving that a tree is a minimally connected graph
Proof
A graph G is a tree if and only if every two vertices of G are connected by one path.
Let G be a tree, delete any edge.
This deleted edge connected a pair of vertices V1V2 which implies that the only path between V1 and V2 was the deleted edge. This shows that there is no path from V1 to V2. Therefore, the graph becomes disconnected hence we can't get from any vertex to any vertex.

The assignment states that G is minimally connected if the removal of any edge of G results in a disconnected graph. Based on the definition of a tree and the stated proof we can say that a tree is a minimally connected graph and therefore it will satisfy the two previous conditions.Is that right?

 

[Dick]

Homework Statement

Let G be a connected graph. We say that G is minimally connected if the removal of any edge of G (without deleting any vertices) results in a disconnected graph. (a) Show that a connected, minimally connected graph has no cycles. (b) Show that a connected graph with no cycles is minimally connected. Commentary: The exercise shows that the two conditions are equivalent. A graph satisfying either condition is a tree.

Homework Equations

The Attempt at a Solution

I approach this by proving that a tree is a minimally connected graph
Proof
A graph G is a tree if and only if every two vertices of G are connected by one path.
Let G be a tree, delete any edge.
This deleted edge connected a pair of vertices V1V2 which implies that the only path between V1 and V2 was the deleted edge. This shows that there is no path from V1 to V2. Therefore, the graph becomes disconnected hence we can't get from any vertex to any vertex.

The assignment states that G is minimally connected if the removal of any edge of G results in a disconnected graph. Based on the definition of a tree and the stated proof we can say that a tree is a minimally connected graph and therefore it will satisfy the two previous conditions.Is that right?

No. The thing you are trying to prove involves cycles. Why doesn't your proof say anything
about cycles?

 

[TheMathNoob]

No. The thing you are trying to prove involves cycles, not trees. Why doesn't your proof involve cycles?

Hello, I thought I could show that by proving that minimally connected graphs are trees hence a tree doesn't have cycles. To show that it doesn't have cycles, I can state that there is just one path between the vertices hence if we take away one edge, it will cause the disconnection of graph. This indicates that this deleted edge is the only path between the vertices that it connects. Hence there is just one path between every pair of vertices, the graph has no cycles because if there is a cycle, then the vertices that the cycle contains may have more than 1 path between them. Does this work?

 

[Dick]

Yes, but for a formal proof you need to state that in the form of a contrapositive.

Hello, I thought I could show that by proving that minimally connected graphs are trees hence a tree doesn't have cycles. To show that it doesn't have cycles, I can state that there is just one path between the vertices hence if we take away one edge, it will cause the disconnection of graph. This indicates that this deleted edge is the only path between the vertices that it connects. Hence there is just one path between every pair of vertices, the graph has no cycles because if there is a cycle, then the vertices that the cycle contains may have more than 1 path between them. Does this work?

 

[TheMathNoob]

Yes, but for a formal proof you need to state that in the form of a contrapositive.

contrapositive how?

 

[Darkstar99]

contrapositive how?

To prove part (a), assume for a contradiction a minimally connected graph has a cycle. Do you see why this is wrong? Just remove an edge from the cycle.

 

[epenguin]

As this is the third question of this kind you have asked, I would like to ask which of the following is true?:

a) the theorem it Is/was to you not a statement of the obvious

b) it was perfectly obvious to you, but you have to, or think you have to go through this somewhat heavy rigmarole because that is what your prof requires, or you think he does?

(Though, that said, it is useful to have realized the connection between minimally connected graphs and trees - in fact minimal connection is part of one of the several alternative definitions of a tree. So I guess that realisation is an advantage and a virtue. But you don't need to mention trees to simply prove the theorem.)

 

[TheMathNoob]

To prove part (a), assume for a contradiction a minimally connected graph has a cycle. Do you see why this is wrong? Just remove an edge from the cycle.

so this is so far what I got

proof by contradiction
Assume a minimally connected graph G has a cycle. If we take away one edge from the cycle, the graph doesn't become disconnected because in a cycle, the vertices may have more than 1 path between them. This contradicts the definition of minimally connected graphs which states that if the graph is minimally connected, the removal of any edge of G results in a disconnected graph. Therefore, G has no cycles.

 

[TheMathNoob]

As this is the third question of this kind you have asked, I would like to ask which of the following is true?:

a) the theorem it Is/was to you not a statement of the obvious

b) it was perfectly obvious to you, but you have to, or think you have to go through this somewhat heavy rigmarole because that is what your prof requires, or you think he does?

(Though, that said, it is useful to have realized the connection between minimally connected graphs and trees - in fact minimal connection is part of one of the several alternative definitions of a tree. So I guess that realisation is an advantage and a virtue. But you don't need to mention trees to simply prove the theorem.)

so this is so far what I got

proof by contradiction
Assume a minimally connected graph G has a cycle. If we take away one edge from the cycle, the graph doesn't become disconnected because in a cycle, the vertices may have more than 1 path between them. This contradicts the definition of minimally connected graphs which states that if the graph is minimally connected, the removal of any edge of G results in a disconnected graph. Therefore, G has no cycles.

 

[haruspex]

so this is so far what I got

proof by contradiction
Assume a minimally connected graph G has a cycle. If we take away one edge from the cycle, the graph doesn't become disconnected because in a cycle, the vertices may have more than 1 path between them.

that fails for a couple of reasons.
1. You only say 'may' have more than 1 path. So the vertices might not have more than one path between them?
2. You need to consider connectivity of all vertices in the graph, not just those in the cycle.
Having removed one edge from the cycle, you need to show that any two given vertices are still connected.

 

[bogo]

Homework Statement

Let G be a connected graph. We say that G is minimally connected if the removal of any edge of G (without deleting any vertices) results in a disconnected graph. (a) Show that a connected, minimally connected graph has no cycles. (b) Show that a connected graph with no cycles is minimally connected. Commentary: The exercise shows that the two conditions are equivalent. A graph satisfying either condition is a tree.

Homework Equations

The Attempt at a Solution

I approach this by proving that a tree is a minimally connected graph
Proof
A graph G is a tree if and only if every two vertices of G are connected by one path.
Let G be a tree, delete any edge.
This deleted edge connected a pair of vertices V1V2 which implies that the only path between V1 and V2 was the deleted edge. This shows that there is no path from V1 to V2. Therefore, the graph becomes disconnected hence we can't get from any vertex to any vertex.

The assignment states that G is minimally connected if the removal of any edge of G results in a disconnected graph. Based on the definition of a tree and the stated proof we can say that a tree is a minimally connected graph and therefore it will satisfy the two previous conditions.Is that right?

I just joined a few minutes ago. I like this.

 

[TheMathNoob]

that fails for a couple of reasons.
1. You only say 'may' have more than 1 path. So the vertices might not have more than one path between them?
2. You need to consider connectivity of all vertices in the graph, not just those in the cycle.
Having removed one edge from the cycle, you need to show that any two given vertices are still connected.

hello haruspex, I am just wondering if the first issue can be fixed by deleting the word may and say it has more than...
I still need to work on the second issue. I am also wondering if I am abusing too much the physics forums.

 

[epenguin]

IMHO your proof is now more direct and to the point than previously.

I think you could meet haruspex' quibble objection quite easily with an appeal to definition, which you might even be able to work into word-tweaking of your existing sentences, otherwise just add one.

 

[haruspex]

IMHO your proof is now more direct and to the point than previously.

I think you could meet haruspex' quibble objection quite easily with an appeal to definition, which you might even be able to work into word-tweaking of your existing sentences, otherwise just add one.

Yes, my first point is easily fixed by deletion of a word, but I cannot accept that my second point was trivial.
The part

If we take away one edge from the cycle, the graph doesn't become disconnected because in a cycle, the vertices ... have more than 1 path between them.

is arguing this chain:
Removing one edge from a cycle in a graph leaves the cycle connected, therefore a graph with a cycle is connected.
That is clearly a wrong step since it makes no use of the fact that the graph was connected before removal of the edge. It's not hard to plug the hole, but it needs to be done.

 

[TheMathNoob]

Assume a minimally connected graph G has a cycle. If we take away one edge from the cycle, the graph doesn't become disconnected because in a cycle, the vertices have more than 1 path between them and the vertices which don't belong to any cycle are still linked to some vertex in a cycle because by definition, the graph is connected. This contradicts the definition of minimally connected graphs which states that if the graph is minimally connected, the removal of any edge of G results in a disconnected graph. Therefore, G has no cycles.

 

[TheMathNoob]

Yes, my first point is easily fixed by deletion of a word, but I cannot accept that my second point was trivial.
The part

is arguing this chain:
Removing one edge from a cycle in a graph leaves the cycle connected, therefore a graph with a cycle is connected.
That is clearly a wrong step since it makes no use of the fact that the graph was connected before removal of the edge. It's not hard to plug the hole, but it needs to be done.

A moment ago#15

Assume a minimally connected graph G has a cycle. If we take away one edge from the cycle, the graph doesn't become disconnected because in a cycle, the vertices have more than 1 path between them and the vertices which don't belong to any cycle are still linked to some vertex in a cycle because by definition, the graph is connected. This contradicts the definition of minimally connected graphs which states that if the graph is minimally connected, the removal of any edge of G results in a disconnected graph. Therefore, G has no cycles.

 

[haruspex]

A moment ago#15

Assume a minimally connected graph G has a cycle. If we take away one edge from the cycle, the graph doesn't become disconnected because in a cycle, the vertices have more than 1 path between them and the vertices which don't belong to any cycle are still linked to some vertex in a cycle because by definition, the graph is connected.

Better, but still a bit handwaving. You only know the graph was connected before removal of the edge, so how do you know a vertex outside the cycle is still connected to a vertex in (what was) the cycle?
It would be much more convincing along these lines:
Let u, v be any two vertices in G. Since G is connected, there is a path P from u to v. If the edge removed from the cycle is not in P they are still connected. If it is in P ...
Can you construct a new path that connects them?

 

[TheMathNoob]

Better, but still a bit handwaving. You only know the graph was connected before removal of the edge, so how do you know a vertex outside the cycle is still connected to a vertex in (what was) the cycle?
It would be much more convincing along these lines:
Let u, v be any two vertices in G. Since G is connected, there is a path P from u to v. If the edge removed from the cycle is not in P they are still connected. If it is in P ...
Can you construct a new path that connects them?

if it is in P they are still connected because in a cycle there are 2 paths between every vertex?. How do I arrange that in my proof??. I still don't get how this leads to a contradiction. Two vertices remain connected, but how does this show that the whole graph remains connected?............ Sorry I think I got you. This shows that any two vertices whether in or outside the cycle remain connected after the deletion of an edge in the cycle. Now I have the next issue, I now think that in a cycle there are just 2 paths between the vertices that it contains.

 

[haruspex]

Now I have the next issue, I now think that in a cycle there are just 2 paths between the vertices that it contains.

Within the cycle, yes. Why is that a problem?

 

[TheMathNoob]

Within the cycle, yes. Why is that a problem?

I previously stated that in a cycle there are more than 1 path between every vertex.

 

[haruspex]

I previously stated that in a cycle there are more than 1 path between every vertex.

Yes, and two is more than one. I still don't see the problem.

 

[TheMathNoob]

Yes, and two is more than one. I still don't see the problem.

There may be 3 which can't be possible,If we consider just one cycle. I am going to have to bother you one more time with a problem that the professor said to be challenging.

 

[haruspex]

There may be 3 which can't be possible,If we consider just one cycle. I am going to have to bother you one more time with a problem that the professor said to be challenging.

There may be three or more paths altogether, but only two that stay within the cycle. For the purposes of the proof, you just need the two in the cycle.
Please start a new thread for your other question. Feel free to tag me in it.