Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph theory (connectedness)

  1. Aug 29, 2006 #1
    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, [tex]C_n[/tex], 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..
  2. jcsd
  3. Aug 29, 2006 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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)
    Last edited: Aug 29, 2006
  4. Aug 29, 2006 #3
    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.
  5. Aug 29, 2006 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

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

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

    Suppose that it's disconnected. How big can the smallest connected component be?
  6. Aug 29, 2006 #5
    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.
  7. Aug 29, 2006 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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 [itex]v_i (1 \leq i \leq n)[/itex].
    Edges between [itex]v_i[/itex] and [itex]v_{i+1}[/itex] ([itex]1 \leq i leq n[/itex]), and also between [itex]v_1[/itex] and [itex]v_n[/itex], 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 [itex]2\omega[/itex], for example, the graph [itex]C_{2\omega}[/itex] would look like:

    [itex]2\omega[/itex] --> 1 --> 2 --> 3 --> 4 --> ...
    [itex]\omega[/itex] --> [itex]\omega + 1[/itex] -->
    [itex]\omega + 2[/itex] --> ...

    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. :smile:

    (Notice that you can derive an inductive principle from it, though! This definition is essentially equivalent to induction)
    Last edited: Aug 29, 2006
  8. Aug 30, 2006 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.)
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Graph theory (connectedness)
  1. Graph Theory (Replies: 3)

  2. Graph theory (Replies: 5)

  3. Graph theory (Replies: 10)

  4. Graph Theory (Replies: 3)

  5. Graph Theory (Replies: 1)