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 :eek: . 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)

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.

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.

yes, that is what I was thinking guys, but is drawing the graph enough?

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.

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 ;)

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.

ok, thanks guys (Okinrus, sang, perspective) , I think I can take it from here...I'll post the written solution later tonight...

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.

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 :)

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 ;)

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 :)