3
$\begingroup$

Is every connected, finite, undirected graph in which all vertices are degree two a cycle?

I feel like this is true, and this is my attempt at a proof:

Start at any vertex. From this vertex, leave to an adjacent vertex, and from there leave to the next and so on. Repeat this process, and every time you get to a vertex, you'll have exhausted one of its outgoing edges, so you will only have one choice -- to move on to the next vertex. Since the graph is finite and connected, eventually you will exhaust all unique vertices and since there is still one vertex (the first vertex we start at) with one unused edge, we must return to it.

$\endgroup$
  • 1
    $\begingroup$ That sounds good. $\endgroup$ – RKD Dec 7 '16 at 2:24
0
$\begingroup$

Yes, your proof looks good to me.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

No. You have not used the assumption that the graph is connected, nor the assumption that the degree of each vertex is exactly two. Your argument is the argument one would give to prove that a finite graph, in which every vertex has degree at least $2,$ contains a cycle. In order to prove that the graph is a cycle, you have to prove that it has no more vertices or edges besides the vertices and edges of your cycle. You can prove that using the assumptions that the graph is connected and that the vertex degrees are exactly $2.$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Could you elaborate on this? I thought I used the fact that the graph is connected by noting that I will have eventually had only one edge remaining leading back to the initial start vertex. I thought I used the fact that all vertices are exactly degree 2 by stating that every time I get to a vertex, I have only one way out. Also, there is at least a way to prove that a graph with the listed properties is indeed a cycle itself, right? $\endgroup$ – MonkeySeeMonkeyCode Dec 7 '16 at 6:19
  • $\begingroup$ How do you know that, when your cyclo closes, it has traversed every vertex of the graph? The reason is very simple. If there is a vertex $v$ that is not on the cycle, then since the graph is connected there is a path $P$ connecting $v$ to some vertex on the cycle; and where $P$ first hits the cycle, say at vertex $w,$ there are $3$ edges incident with $w,$ two edges of the cycle and an edge of $P,$ contradicting the assumption that the degree is exactly $2$. I don't see where you said anything like that. $\endgroup$ – bof Dec 7 '16 at 6:34
  • $\begingroup$ Ah I see. Thanks, I thought that I would not need to say all that to make the proof complete. I suppose this is part of being a student of mathematics, always learning... $\endgroup$ – MonkeySeeMonkeyCode Dec 7 '16 at 7:27
  • $\begingroup$ Well, at a more advanced level, the whole statement is too simple and obvious to need a proof. If a finite graph is $2$-regular and connected, then of course it's a cycle. On the other hand, if you're asked to prove such a simple proposition, then I think you should include very simple steps. But maybe I'm too picky. $\endgroup$ – bof Dec 7 '16 at 8:01
0
$\begingroup$

Let $X=(V(X),E(X))$ be the given graph.

We know that $X$ is 2-Regular,connected,simple, and undirected.

Aim : Want to show $X$ is Cycle.

Proof : Let $|V(X)|=n,$ and $V(X)=\{v_1,v_2,\dots,v_n\}$.

Wlog let us assume that $\{v_1,v_2\}$ and $\{v_1,v_n\}\ \in E(X)$ ,

consider $v_2$ since $deg(v_2)=2$, $v_2$ has to be in adjacent with any $v_i \in V(X)$, suppose $\{v_{2},v_n\}\in E(X)$ this will contradict the fact that graph $X$ is connected ! why ? {hint Look at the vertex $v_3$,it has got no path with $v_1$ which is a contradiction to the fact that $X$ is connected.}

So $\{v_{2},v_n\}\not\in E(X)$ again one can assume $\{v_{3},v_2\}\in E(X)$ again similar argument we put on $v_n$ and $v_2$ will work here and will get that $\{v_n,v_3\}\not\in E(X)$.

Repeat this process until you hit $v_{n-1}$ and there you can say that $\{v_{v-1},v_n\}\in E(X)$ which will result in saying that $X$ is cycle.

Basically this is your idea of proof only, I just written elaborately so that it will be clear to everyone why this fact is true.The numbering I have given to $V(X)$ is just random only so it doesn't affect our proof.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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