Proving Connectedness of Cycle Graphs: An Alternative Approach

[buddyholly9999]

I remember when I was taking discrete analysis of data structures and we had to prove certain graph theory properties.

I'll give a specific example, prove that the cycle graph, C_n, is connected for all n.

From what I remember, it was induction we used to prove this...what I want to know is if there is any other way?

Oh yeah...I think this topic goes under general math...didn't see no graph theory categories..

 

[Hurkyl]

It depends on just what your definition of the "cycle graph" is... but I would expect that induction must be used. (but not necessarily explicitly -- e.g. maybe you could use a theorem that requires induction for its proof)

 

[buddyholly9999]

A cycle graph is a graph on n nodes containing a single cycle through all nodes.

The reason I bring this up is because I think I saw something the other day that said if every vertex of a graph G had something like at least (n-1)/2 degrees then it was connected.

 

[Hurkyl]

A cycle graph is a graph on n nodes containing a single cycle through all nodes

Then it depends on what you take as the definition of "cycle".

Are you comfortable with things like ordinal numbers? If so, I could explain to you why I think that induction will be necessary.

The reason I bring this up is because I think I saw something the other day that said if every vertex of a graph G had something like at least (n-1)/2 degrees then it was connected.

Suppose that it's disconnected. How big can the smallest connected component be?

 

[buddyholly9999]

Come on now...you know what the typical C_n refers to...shall I change my example to the Wheel graph? or perhaps the path graph?

I would like to know (using ordinal numbers) why exactly induction would absolutely be necessary if that's what you want to show me.

 

[Hurkyl]

Come on now...you know what the typical C_n refers to...shall I change my example to the Wheel graph? or perhaps the path graph?

Well, yes. Actually, there are boundary cases I'm not sure about -- for example, I can give reasons why we should consider the infinite graph:

... --> * --> * --> * --> ...

a cyclic graph, and reasons why we shouldn't. That's why I'm harping on the precise definition.


For example, I might define a cyclic graph to consist of, for some n > 2:

A sequence of vertices v_i (1 \leq i \leq n).
Edges between v_i and v_{i+1} (1 \leq i leq n), and also between v_1 and v_n, and no others.


If I reject induction, then I cannot restrict myself to the integers. The above definition makes sense if I plug in any ordinal number greater than 2. If I used 2\omega, for example, the graph C_{2\omega} would look like:

2\omega --> 1 --> 2 --> 3 --> 4 --> ...
\omega --> \omega + 1 -->
\omega + 2 --> ...


Other definitions of a cyclic graph might need more interesting transfinite models than ordinals, but I'm pretty sure they will exist.

The point being that induction is a key property of the natural numbers; if you don't invoke it, then you can't rule out various transfinite messes like the one above.



Of course, other definitions of cyclic don't have that problem. I might define a cyclic graph to be a connected graph where every vertex has degree 2. With this definition, there's no trouble showing cyclic graphs are connected.

(Notice that you can derive an inductive principle from it, though! This definition is essentially equivalent to induction)

 

[matt grime]

Am I being incredibly dumb here, but since there is a single cycle through all edges then there is only one path component so it is connected? (Note, all graphs have finitely many edges in my world unless explicitly stated otherwise.)