MHB Another tree-related graph theory proof

[annie122]

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)

 

[caffeinemachine]

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.