Another tree-related graph theory proof

In summary: Oh, I'm sorry. I wasn't aware of the LaTeX requirement. Thank you for letting me know. I'll make sure to use it next time. In summary, the conversation discusses two proofs and whether they are correct. The first proof shows that a graph is a tree if and only if it has no cycles, but joining any two nonadjacent vertices creates exactly one cycle. The second proof shows that a connected graph is a tree if and only if every vertex of degree greater than 1 is a cutpoint. The conversation also includes some questions and clarifications about the proofs.
  • #1
annie122
51
0
Please check if my two following proofs are correct.
I didn't know whether it was better to post them in a separate thread or not.
I posted them together since they are both questions related to graph theory.
Let me know if I should have separated them.

Prove that a graph G is a tree iff it has no cycles, but joining any two nonadjacent vertices of the graph creates exactly one cycle.

Necessary condition:
Let x and y be two nonadjacent vertices.

I claim that there is exactly one path between x and y.
Since G is connected by the definition of a tree, there is at least one path between x and y.
Suppose there are two paths between x and y: xAy and xBy, where A and B are strings of vertices. Then we can create a cycle xAyBx. Therefore, there is at most one path between x and y.

So let xAy be a path from x to y. If we join x to y, we have a cycle xAyx.
Suppose there are more than two cycles: xAyx and xByx. If we remove edge xy from the cycles, we obtain two distinct paths xAy and xBy.
Hence, there can be at most one cycle.

Sufficient condition:
If G is not a tree, G is not connected, contains a cycle, or both.
If G is not connected, it is possible to join two nonadjacent vertices and not get a cycle. (*I am unsure about this. How can I prove that there are always two such vertices? For example, joining two nonadjacent vertices in a graph creates a cycle. Why can I be sure that there are always some vertices that do not lie on a cycle? I need help proving this claim)
If G contains a cycle, it is not true that G contains no cycle.
So if G contains no cycles and joining any two nonadjacent makes a cycle, then G is a tree.Prove that a connected graph is a tree if and only if every vertex of degree greater than 1 is a cutpoint.

NECESSARY CONDITION:
Let x be a vertex in G. x is adjacent to at least two vertices, say y and z.

Then (yxz) is the only path from y to z. Suppose x is not a cutpoint, and

that deleting x does not make the graph disconnected. Then there must be

another path from y to z, say yAz, where A is a string of vertices. But then

(yAzxy) is a cycle in the original graph. Therefore, x must be a cutpoint.

SUFFICIENT CONDITION:
Suppose G is not a tree. Since G is connected, G must have at least one cycle. Delete one vertex xi from such a cycle (x1,...,xi-1,xi,xi+1,...,x1) then xi is not a cutpoint because there is a path from xi-1 to xi+1 by way of (xi-1,...,x1,...,xi+1)
 
Last edited:
Physics news on Phys.org
  • #2
Yuuki said:
Prove that a graph G is a tree iff it has no cycles, but joining any two nonadjacent vertices of the graph creates exactly one cycle.

Necessary condition:
Let x and y be two nonadjacent vertices.

I claim that there is exactly one path between x and y.
Since G is connected by the definition of a tree, there is at least one path between x and y.
Suppose there are two paths between x and y: xAy and xBy, where A and B are strings of vertices. Then we can create a cycle xAyBx. Its not necessary that xAyBx is a cycle. Although, a little more fiddling around will prove that you can indeed form a cycle out of the vertices found in xAyBx, not necessarily using all the vertices. Therefore, there is at most one path between x and y.

So let xAy be a path from x to y. If we join x to y, we have a cycle xAyx.
Suppose there are more than two cycles: xAyx and xByx. If we remove edge xy from the cycles, we obtain two distinct paths xAy and xBy.
Hence, there can be at most one cycle.

Sufficient condition:
If G is not a tree then G is not connected or it contains a cycle, or both.
If G is not connected, it is possible to join two nonadjacent vertices and not get a cycle. (*I am unsure about this. How can I prove that there are always two such vertices? For example, joining two nonadjacent vertices in a graph creates a cycle. Why can I be sure that there are always some vertices that do not lie on a cycle? I need help proving this claim. Its easy. If G is not connected then there are at least two different components in G. Take a vertex in one component and another in another component. Joining these two vertices doesn't create an extra cycle.)
If G contains a cycle, it is not true that G contains no cycle.
So if G contains no cycles and joining any two nonadjacent makes a cycle, then G is a tree.

I have marked the errors with red and my comments with blue.
Your post remained unanswered for so long probably because you didn't use LaTeX. See the LaTeX subforum on the home page to get yourself started with LaTeX. I will look into the next part of your post in some time.
 

FAQ: Another tree-related graph theory proof

1. What is "Another tree-related graph theory proof"?

"Another tree-related graph theory proof" refers to a mathematical proof that involves the study of graphs and trees, which are structures composed of vertices and edges. In this proof, the relationship between trees and other graph structures is examined.

2. How is this proof different from other tree-related graph theory proofs?

This proof may have a different approach or focus compared to other proofs in the same field. It may also introduce new concepts or provide a different perspective on existing theories.

3. What is the significance of this proof in the field of graph theory?

This proof may contribute to the understanding of the relationship between trees and other graph structures, and may have applications in various fields such as computer science, engineering, and biology.

4. What are the key components of this proof?

The key components of this proof may include definitions of graph theory concepts, theorems, and their proofs, as well as examples and applications to illustrate the theory.

5. Is this proof applicable to real-world problems?

Yes, this proof has real-world applications in fields such as computer networking, transportation networks, and social networks. The concepts and theories presented in the proof can be used to model and analyze real-world problems.

Similar threads

Replies
1
Views
1K
Replies
1
Views
2K
Replies
2
Views
2K
Replies
2
Views
2K
Replies
3
Views
2K
Replies
2
Views
2K
Replies
1
Views
1K
Replies
4
Views
1K
Back
Top