- Thread starter
- #1

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.

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.

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)

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: