|
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). |
||||
|
|
|
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$. |
|||
|
|
|
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'. |
|||
|
|
