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 have tried to prove this but I'm not sure if I'm right.

Prove that a cycle graph $C_n$ with $n\ge 3$ vertices is unique up to isomorphism $f$.

We know each vertex of $C_n$ has degree $2$. So if a graph $G$ has $n$ vertices of degree $2$ then $f$ exists where, $f:V(C_n)\rightarrow V(G)$ such that any two adjacent vertices in $C_n$ map to any two adjacent vertices in $G$ (which is the basic isomorphism).

share|improve this question
add comment

2 Answers 2

The actual proof will depend heavily on the definition of $C_n$ that you’re using. If, for instance, you’ve defined $C_n$ to be the graph whose vertex set is $\{1,\dots,n\}$ and whose edges are $\{1,n\}$ and the sets $\{k,k+1\}$ for $k=1,\dots,n-1$, and then defined a cycle graph on $n$ vertices to be any graph isomorphic to $C_n$, then there’s nothing to prove, since isomorphism is an equivalence relation.

If, on the other hand, you define a cycle graph on $n$ vertices to be a connected graph with $n$ vertices, each of degree $2$, then there is some work to be done. Let $G$ be such a graph, with vertex set $V$; one way to proceed is to show that $G$ is isomorphic to the graph $C_n$ that I described in the first paragraph. To do this, pick any vertex of $G$ and label it $v_1$, and pick either of the vertices adjacent to $v_1$ and label it $v_2$.

Now suppose that you’ve labelled vertices $v_1,\dots,v_m$ for some $m$ such that $2\le m<n$ in such a way that the vertices $v_1,\dots,v_m$ are all distinct, and $v_{k+1}$ is adjacent to $v_k$ for $k=1,\dots,m-1$.

Let $V_0=\{v_1,\dots,v_m\}$, and suppose that $v_m$ is adjacent to $v_1$. Each $v_k\in V_0$ has exactly two neighbors in $G$, and both are in $V_0$, so $v_k$ is not adjacent to any vertex in $V\setminus V_0$. And $m<n$, so $V\setminus V_0\ne\varnothing$, so $G$ is not connected: if $v\in V\setminus V_0$, there is no path from $v$ to $v_1$. Thus, $v_m$ is not adjacent to $v_1$ in $G$. Clearly $v_m$ is not adjacent to any $v_k$ with $1<k<m$, since the two neighbors of each of those vertices are already accounted for. Thus, the other neighbor of $v_m$ (besides $v_{m-1}$) must belong to $V\setminus V_0$; label this vertex $v_{m+1}$, and continue.

We’ve just shown that this process stops only when $m=n$. At that point the only possibility for the other neighbor of $v_n$ (besides $v_{n-1}$) is $v_1$. To finish the argument, just verify that the map $k\mapsto v_k$ is an isomorphism between $C_n$ (as defined above) and $G$.

share|improve this answer
add comment

Show that any 'straight' path of length n-1 is unique up to isomorphism.

Delete an edge from both cycles. Deduce that they are isomorphic to each other.

Note: This requires the same amount of work to describe the actual isomorphism, but might seem more 'obviously true'.

share|improve this answer
add comment

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.