Homework # 22
So for #1 on the homework we're pretty sure that it works for all prime numbers, but we have no idea why. Um. So can you give us a hint plz.
Homework # 22
Forum
» courses / Intro to Formal Math (Fall 2010)
» Homework # 22
Summary:
ahh
Well, we've seen that it works for 5, which is prime. I'm assuming that you have verified that it does not work when there are 6 vertices, but it does when there are 7. How about 8 and 9? If you are patient and careful (and draw the picture large enough), you can probably do these by hand. Skip worrying about 8 for a moment and try 9 (which is not prime). I'm hinting that you may not have the right answer.
So its not just prime numbers, but were still having trouble seeing how all the numbers are related to eachother. Can you give us another hint please :]
OK, imagine you have some random complete graph. Instead of thinking about drawing the graph without lifting your pencil, imagine that all of the edges are already there and you want to color all the edges without lifting up your crayon. In your graph, all of the vertices have the same number of edges connected to them. In fact, if you started with $n$ vertices, then each vertex has $n-1$ edges connected to it. Focus on one of the vertices for a moment and assume that you haven't colored any of the edges connected to that vertex. Eventually, you will color one of the edges coming into the vertex you have in mind and then it will have to leave on a different edge. If the number of vertices is larger than 3, then you still have some edges to color that are connected to the vertex in question. Eventually, you'll return to the vertex. What can happen? Can you leave again? Can you get stuck there? If so, perhaps you've hit every other edge anyway, or maybe not.
So at this point we think that's it's odd numbers and 2, and we think we have a pretty good reason. It worked with odd numbers because we were able to draw lines in a circle and we just kept drawing a line to the next empty space. The same thing almost worked for even numbers until we had to draw a line straight across and then we got stuck. It worked for 2 obviously, because drawing it straight across was the only line.
I hope that made sense; are we headed in the right direction.
Guess What! For all the graphs that work, apart from 2, the number of lines is divisible by the number of points! Not only that but there is a pattern. 3*1 = 3, 5*2 = 10, 7*3 = 21, number of points * n = number of lines.
That is rather cool. I hope it's important.
Ah, interesting realization. It may help you realize one key piece of information. Recall that we had another formula for the number of edges that worked for any $n$. It might be helpful to think about this formula and your realization.
OK, we're going to sleep on it. Can we see you in your office tomorrow at 11:00?
I teach at 11:15, but I'll be available briefly at 11. I think that it is great that you are thinking deeply about this!
/forum/t-286179/homework-22#post-
