Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to show that all graphs with 5 vertices, each of degree 2, are isomorphic to each other. Is there a more clever way than simply listing them all out?

share|improve this question

2 Answers 2

up vote 6 down vote accepted

I'm assuming you do not allow multi-edges, as otherwise there is a trivial counterexample (the cycle of length $5$, versus a disconnected graph consisting of a triangle and two vertices joined by two edges).

Pick one vertex $v_0$; it must be joined to two other distinct vertices, which we may call $v_{-1}$ and $v_1$. Each of those must be joined to another vertex; can they be joined to each other? Can they both be joined to the same vertex that is not yet listed? Consider the possibilities. Then see where each of them leads you.

share|improve this answer

Consider this simple, powerful theorem: all vertices of a graph have even degree if and only if the set of its edges can be partitioned in cycles.

The number of edges of your graph $G$ is $e(G) = \frac 1 2 \sum_{x\in V(G)} d(x) = 5$. Observe that there are not isolated vertices and that every cycle has at least three edges. Therefore the only possible partition in cycles is $E(G)$ itself, i.e. all the graphs with the required property are 5-cycles and thus they are isomorphic.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.