Graph theory proof

  • #1
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:

Answers and Replies

  • #2
Samy_A
Science Advisor
Homework Helper
1,242
510

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
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
36,748
7,086
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
Samy_A
Science Advisor
Homework Helper
1,242
510
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
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
36,748
7,086
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 Threads on Graph theory proof

  • Last Post
Replies
22
Views
2K
  • Last Post
Replies
11
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
12
Views
2K
Replies
3
Views
1K
Replies
1
Views
7K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
1
Views
508
  • Last Post
Replies
7
Views
829
  • Last Post
Replies
2
Views
1K
Top