Proving a Cycle Exists in Finite Graphs with Degree 2+ Vertices

In summary: However, the rest of the proof still stands as a valid explanation for why a graph with vertices of degree two or greater cannot be a tree. So in summary, if all vertices in a finite graph have degree two or greater, then there must be a cycle present in the graph, making it impossible for the graph to be a tree.
  • #1
TheMathNoob
189
4

Homework Statement


Exercise 0.1. Suppose that G is a finite graph all of whose vertices has degree two or greater. Prove that a cycle passes through each vertex. Conclude that G cannot be a tree.

Homework Equations

The Attempt at a Solution


If every vertex in a graph G has degree two or greater, then there is always a way to get in and out without using the same edge. If we start at any vertex and try to traverse the graph by using the rule of getting in and out and not using the same edge, eventually we will realize that we can't stop, so this implies that there is a cycle. Therefore G can't be a tree.

I am new to this types of proofs, so I need feedback.
 
Last edited:
Physics news on Phys.org
  • #2
TheMathNoob said:

Homework Statement


Exercise 0.1. Suppose that G is a finite graph all of whose vertices has degree two or greater. Prove that a cycle passes through each vertex. Conclude that G cannot be a tree.

Homework Equations

The Attempt at a Solution


If every vertex in a graph G has degree two or greater, then there is always a way to get in and out without using the same edge. If we start at any vertex and try to traverse the graph by using the rule of getting in and out and not using the same edge, eventually we will realize that we can't stop, so this implies that there is a cycle. Therefore G can't be a tree.

I am new to this types of proofs, so I need feedback.
Consider the following graph:
gaph.jpg

Apply your proof to vertex 1. Does it show that there is a cycle through vertex 1?
 
  • #3
Samy_A said:
Consider the following graph:
View attachment 94303
Apply your proof to vertex 1. Does it show that there is a cycle through vertex 1?
That's not just a counterexample to the proof, it's a counterexample to the given claim.
 
  • #4
haruspex said:
That's not just a counterexample to the proof, it's a counterexample to the given claim.
I know, it was a not too subtle hint. :oldsmile:
The "each vertex" in the statement of the exercise must be an error, and the exercise was probably something like: "prove that the graph contains a cycle".
 
  • #5
Samy_A said:
I know, it was a not too subtle hint. :oldsmile:
The "each vertex" in the statement of the exercise must be an error, and the exercise was probably something like: "prove that the graph contains a cycle".
Yes, that makes sense for the last part.
 

Related to Proving a Cycle Exists in Finite Graphs with Degree 2+ Vertices

1. How do you define a cycle in a finite graph?

A cycle in a finite graph is a path that starts and ends at the same vertex, without repeating any other vertices or edges along the way.

2. What is the significance of having degree 2+ vertices in a graph when proving a cycle exists?

Degree 2+ vertices, also known as endpoints, are crucial in proving the existence of a cycle in a finite graph because they ensure that the graph has enough connections to form a closed path.

3. Can a cycle exist in a finite graph with only degree 2 vertices?

No, a cycle cannot exist in a finite graph with only degree 2 vertices. This is because each vertex in a cycle must have at least 2 adjacent vertices, and if all vertices have a degree of 2, there will not be enough connections to form a cycle.

4. How do you prove the existence of a cycle in a finite graph with degree 2+ vertices?

To prove the existence of a cycle in a finite graph with degree 2+ vertices, one method is to use the concept of a closed walk. A closed walk is a path that starts and ends at the same vertex, but may repeat other vertices or edges along the way. By finding a closed walk in the graph, we can then eliminate any repeated vertices or edges to obtain a cycle.

5. Are there any other methods for proving the existence of a cycle in a finite graph with degree 2+ vertices?

Yes, there are other methods for proving the existence of a cycle in a finite graph with degree 2+ vertices. Some other common approaches include using the concept of a spanning tree or using induction to show that the graph must contain a cycle. The most suitable method will depend on the specific graph and the problem at hand.

Similar threads

Proving a Tree is a Minimally Connected Graph in Graph Theory
    • Precalculus Mathematics Homework Help
Replies
22
Views
3K
Proof about isomorphism (Graph Theory)
    • Precalculus Mathematics Homework Help
Replies
3
Views
2K
I Prove that a given graph contains a cycle using induction (Graph Theory)
    • General Math
Replies
7
Views
2K
Proving a graph not simple and planar after adding edges
    • Precalculus Mathematics Homework Help
Replies
4
Views
1K
Does Induction Work for Proving Graph Theory Statements?
    • Precalculus Mathematics Homework Help
Replies
11
Views
2K
I Question regarding degrees of a graph and its biconnected components
    • General Math
Replies
34
Views
4K
MHB Minimum Degree of a Random Graph (Probabilistic Method)
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
I Understanding a Graph Theory Proof
    • General Math
Replies
3
Views
683
Graph theory proof (Unlabeled trees)
    • Precalculus Mathematics Homework Help
Replies
12
Views
3K
I Finding the chromatic number of a graph with biconnected components
    • General Math
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top