Thread: construction and induction proofs help

  1. #1
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572

    construction and induction proofs help

    I have my first assignment from my Languages and Automata class, and one of the problems is giving me a headache. I am supposed to prove a theorem using construction and induction. The proof by construction is a piece of cake (you could find my solution below) but the induction is not going so well. And this is supposed to be review . All help/hints will be appreciated; the theorem:

    For each even number n greater than 2, there exists a 3-regular graph with n nodes.

    (as a side note, for those who don't know, a k-regular graph is a graph where each node has degree k, i.e. k incident edges)

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  2. #2
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    I think you should be able to solve it by looking at a few common cases. For example, how would you form a 3-regular graph with 4 nodes? This would be the base case. Then the next case you would try to solve a 3-regular graph with 6 nodes using the 3-regular results for four nodes. If the pattern generalizes, you should be able to form a proof. If not, the induction will probably require two or more subproblems.

  3. #3
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    To prove it by induction:

    First show that the theorem is true for n=4 (simple)

    Then, assume that the theorem is true for n=k.

    Finally, show that your assumption implies that the therorem is true for n = k+2.
    This is quite easy to prove, just insert two nodes into the 3-regular graph and show that they also get three neighbours (connect them with eachother).

    Now we have proven the theorem by induction.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  4. #4
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    yes, that is what I was thinking guys, but is drawing the graph enough?

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  5. #5
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Quote Originally Posted by axon
    yes, that is what I was thinking guys, but is drawing the graph enough?
    You don't have to draw anything.

    For the n=k+2 case, just insert two nodes not adjacent to each other in the graph and connect them to each other as well. The number of connections of every node previously in the graph will be unchanged, while the two new nodes will have three connections as well.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  6. #6
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Quote Originally Posted by Sang-drax
    You don't have to draw anything.

    For the n=k+2 case, just insert two nodes not adjacent to each other in the graph and connect them to each other as well. The number of connections of every node previously in the graph will be unchanged, while the two new nodes will have three connections as well.
    ahhhh, took me a second to get what you are saying. For Sang-drax's solution to work you always arange the nodes in a circular/perimeter type fasion. Then, at any value of k, 2 new nodes are inserted into the perimeter accross from each other. Both nodes get connected to the neighbors on either side and to each other. This gives the new nodes a degree of 3 and leaves the other unchanged. *clicks into my head*

    Another solution (independant of arrangment) is to create a new node called A. select 2 nodes (X and Y) in the existing graph that are connected. Disconnect X and Y and connect A to both X and Y. Repeat this step with a new node B. (ie. B gets connected to 2 existing, connected nodes Z and W*. Z is disconnected from W). Connect A and B.
    * Z and W connot be equal to A. This is because you should be adding both nodes at the same time (n = k + 2). It was just easier to explain with one at a time.

    Of course you'd have to express this all mathematically for a proper inductive proof

  7. #7
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Quote Originally Posted by Perspective
    ahhhh, took me a second to get what you are saying. For Sang-drax's solution to work you always arange the nodes in a circular/perimeter type fasion.
    I wasn't saying anything about the arrangement of the nodes. Not all graphs of this type can be arranged into a circular shape. For example you could have two separate 3-regular graphs, each with 4 nodes and they combined will be one 3-regular graph with 8 nodes.

    But as you say, just break two connections A and B, insert the two new nodes where the connections were and finally connect the two new nodes with each other.

    Sorry if I'm being unclear, but I'm trying the best I can. I don't know any "mathematical English" and I've never heard of 3-regular graphs before this thread.

    EDIT: Attached an image of one possible 3-regular graph with 8 nodes.
    Last edited by Sang-drax; 09-08-2004 at 04:34 PM.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  8. #8
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    ok, thanks guys (Okinrus, sang, perspective) , I think I can take it from here...I'll post the written solution later tonight...

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  9. #9
    Registered User
    Join Date
    Aug 2003
    Posts
    470
    It looks like the trick is as follows. When forming the 6 node 3-regular graph, there is a 4 node 3-regular graph subset. By doing certain operations between the 3-regular subset and the other two nodes , which keep the 3-regular property of the subgraph, it's possible to build a 6-node 3-regular graph.

  10. #10
    C > C++ duders ggs's Avatar
    Join Date
    Aug 2001
    Posts
    435
    Whenever I see a simple problem like this, it is easy enough to reason out why things must be true, but I cannot imagine how to formally write the answer

    So, bumping to encourage axon to hurry up with formal proof
    .sect signature

  11. #11
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    oops, forgot to post it earlier...and my cam just ran out of battery, so the pic will have to wait till tomorrow...

    and BTW...the other "formal" proof is already posted

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  12. #12
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Quote Originally Posted by Sang-drax
    For example you could have two separate 3-regular graphs, each with 4 nodes and they combined will be one 3-regular graph with 8 nodes..
    hmm, i never thought of it that way. I just assumed the entire thing had to be connected for some reason. good point though

Popular pages Recent additions subscribe to a feed