# 4-regular Graph

• Dec 9th 2009, 01:42 AM
AwesomeDesiKid
4-regular Graph
Prove there is precisely one 4 regular graph on 6 vertices.
• Dec 9th 2009, 02:00 AM
guildmage
I don't know if this will work but have you tried showing that any two 4-regular graph on 6 vertices are isomorphic?
• Dec 9th 2009, 03:30 AM
AwesomeDesiKid
Quote:

Originally Posted by guildmage
I don't know if this will work but have you tried showing that any two 4-regular graph on 6 vertices are isomorphic?

well i tried to get 4,4,4,4,4,4 down to C4 and show that its unique subgraph and build my way up
i not sure if that will work either...but i m not so good with isomorphic
i usually make a mistake going there
• Dec 19th 2009, 05:47 PM
kumarstays
4 regular graph on 6 vertices.
Quote:

Originally Posted by AwesomeDesiKid
Prove there is precisely one 4 regular graph on 6 vertices.

That will be a graph obtained by removing 3 edges from complete graph on 5 vertices .

proof .
consider 5-regular graph with 6 vertices it is nothing but complete graph on 5 vertices .Now you need to reduce one degree for each of six vertices that is you need to remove 3 edges.
• Dec 19th 2009, 05:49 PM
kumarstays
4-regular graph with 6 vertices
That will be a graph obtained by removing 3 edges from complete graph on 5 vertices .

proof .
consider 5-regular graph with 6 vertices it is nothing but complete graph on 5 vertices .Now you need to reduce one degree for each of six vertices that is you need to remove 3 edges.