Proof about isomorphism (Graph Theory)

  • #1
189
4

Homework Statement


1. Prove or disprove up to isomorphism, there is only one 2-regular graph on 5 vertices.

Homework Equations




The Attempt at a Solution


I am making this thread again hence I think I will get more help in this section
old thread https://www.physicsforums.com/threads/proof-about-isomorphism-graph-theory.850945/#post-5337080

Proof

Let Z be a set of 5 vertices v1,v2,v3,v4,v5. A 2-regular graph on 5 vertices is a graph in which the degree of every vertex is 2.
If we start linking every vertex with every other vertex in the set in a way that the degree of the vertices can be 2, we will realize that the graph is always equivalent to a pentagon.

Pick V1
In this case we can just link V1 to any vertex hence there is currently just one vertex in the graph. Let’s do V1V2.

Pick V2
In this case we can just link V2 to remaining vertices because V2 is already linked to V1. Let’s do V2V3.

Pick V3
In this case we can’t link V3 to V1 because the remaining vertices would have to have a degree of just 1. And we can’t like V3 to V2 because they are already linked, so the best option for V3 is any remaining vertex. Let’s do V3V4

Pick V4
In this we can’t link V4 to V1 and V2 because the remaining vertex would have to have a degree of 0 and V3 because they are already linked. The best option for V4 would be V5. Let’s do V4V5.

Pick V5
This is the last vertex and the only way to make this graph 2 regular would be by linking V5 to V1.

We can just do the same process in any order you want and the outcome will always be a pentagon. Permuting vertices in a pentagon just creates isomorphic relations among themselves therefore there is just one 2-regular graph on 5 vertices.
 

Answers and Replies

  • #2
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
36,796
7,126

Homework Statement


1. Prove or disprove up to isomorphism, there is only one 2-regular graph on 5 vertices.

Homework Equations




The Attempt at a Solution


I am making this thread again hence I think I will get more help in this section
old thread https://www.physicsforums.com/threads/proof-about-isomorphism-graph-theory.850945/#post-5337080

Proof

Let Z be a set of 5 vertices v1,v2,v3,v4,v5. A 2-regular graph on 5 vertices is a graph in which the degree of every vertex is 2.
If we start linking every vertex with every other vertex in the set in a way that the degree of the vertices can be 2, we will realize that the graph is always equivalent to a pentagon.

Pick V1
In this case we can just link V1 to any vertex hence there is currently just one vertex in the graph. Let’s do V1V2.

Pick V2
In this case we can just link V2 to remaining vertices because V2 is already linked to V1. Let’s do V2V3.

Pick V3
In this case we can’t link V3 to V1 because the remaining vertices would have to have a degree of just 1. And we can’t like V3 to V2 because they are already linked, so the best option for V3 is any remaining vertex. Let’s do V3V4

Pick V4
In this we can’t link V4 to V1 and V2 because the remaining vertex would have to have a degree of 0 and V3 because they are already linked. The best option for V4 would be V5. Let’s do V4V5.

Pick V5
This is the last vertex and the only way to make this graph 2 regular would be by linking V5 to V1.

We can just do the same process in any order you want and the outcome will always be a pentagon. Permuting vertices in a pentagon just creates isomorphic relations among themselves therefore there is just one 2-regular graph on 5 vertices.
Your proof looks ok to me. Is that all you are asking?
 
  • #3
189
4
Your proof looks ok to me. Is that all you are asking?
Thank you!. I finally made sense. How can I improve my notation?
 
  • #4
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
36,796
7,126
Thank you!. I finally made sense. How can I improve my notation?
I would probably have expressed it differently. Rather than saying, 'pick' another vertex, I would take the graph as given and say that v2 must be adjacent to a unique vertex other than v1, call it v3, etc. In this way you build up all the adjacencies deterministically.
 

Related Threads on Proof about isomorphism (Graph Theory)

  • Last Post
Replies
11
Views
1K
  • Last Post
Replies
4
Views
809
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
22
Views
2K
  • Last Post
Replies
12
Views
2K
Replies
1
Views
7K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
510
  • Last Post
Replies
7
Views
833
Top