Winging it
Nov. 12th, 2007 04:02 pmSo I arrive at my discrete math midterm[0] half an hour late. That's half the time gone. Oh, this doesn't look bad... only 5 problems. 1 is easy. 5 is easy. 4 is easy. 2... well, do I want do induct on m or on n-m? I'll induct on m, it'll be more straightforward that way. That leaves problem #3.
Problem #3 is to prove that any finite graph on two or more vertices must have two vertices of the same degree. Huh. Not certain I've ever seen that before and I have little idea what to do. Well, I only have 5 minutes left (though the professor comes up and says since I was so late she'll give me a little extra time, which turns out to be about 3 minutes or so). Better do something.
(I think you can guess where this story is going - I turn in a horribly complicated proof of something that could have been done in a line or two.)
So... I'll induct. 2 is obvious. So say true for n, we want n+1. Assume otherwise, remove a vertex. Which one? How about the one of least degree? OK... so that drops the degree of everything by 1, contradiction, right? No, only the one's it's adjacent to. Wait, why least degree? Why not arbitrary? No... I'll want least degree. Actually, change that. Let's go with max degree instead. So - remove it, there's a pair with the same degree, it must be connected to precisely one of them. So I can look at it in terms of these pairs. No, wait, what if there's a triple? Ah, well, in that case we're done as there are only two possible degrees we can get out of that. So, pairs. This means the removed vertex has degree at most n/2, and since it was of max degree, each vertex does, so by pigeonhole, two must have the same degree. Done! No, wait! That's only if they're all in pairs! So say there are m pairs, then there are at most (n-2m)+m=n-m edges, m≥1 by inductive hypothesis, so degree at most n-1, there are n+1 vertices, pigeonhole again. Actually done.
And this (written up not quite so train-of-thought) is what I turn in. Shortly afterwards I realize I could have noted that the degree of the removed vertex is at most n-1 by simply noting that there's some vertex it's not connected to (as there's some pair), and so least degree would have worked after all (getting degree at least 1 instead of at most n-1).
And of course shortly after that my pigeonhole thinking leads me to the simple proof. There are n vertices, and n possible degrees from 0 to n-1. Meaning if all the degrees are distinct, there's one of each degree. In particular, there's one connected to nothing else, one connected to everything else, contradiction.
Now I just wish I could see how horrified the grader is on seeing my proof. Hopefully I'll get some sort of comment about it.
-Harry
[0]I'm following here the UChicago convention of referring to all non-final tests as "midterms", regardless of how many or when they are.
Problem #3 is to prove that any finite graph on two or more vertices must have two vertices of the same degree. Huh. Not certain I've ever seen that before and I have little idea what to do. Well, I only have 5 minutes left (though the professor comes up and says since I was so late she'll give me a little extra time, which turns out to be about 3 minutes or so). Better do something.
(I think you can guess where this story is going - I turn in a horribly complicated proof of something that could have been done in a line or two.)
So... I'll induct. 2 is obvious. So say true for n, we want n+1. Assume otherwise, remove a vertex. Which one? How about the one of least degree? OK... so that drops the degree of everything by 1, contradiction, right? No, only the one's it's adjacent to. Wait, why least degree? Why not arbitrary? No... I'll want least degree. Actually, change that. Let's go with max degree instead. So - remove it, there's a pair with the same degree, it must be connected to precisely one of them. So I can look at it in terms of these pairs. No, wait, what if there's a triple? Ah, well, in that case we're done as there are only two possible degrees we can get out of that. So, pairs. This means the removed vertex has degree at most n/2, and since it was of max degree, each vertex does, so by pigeonhole, two must have the same degree. Done! No, wait! That's only if they're all in pairs! So say there are m pairs, then there are at most (n-2m)+m=n-m edges, m≥1 by inductive hypothesis, so degree at most n-1, there are n+1 vertices, pigeonhole again. Actually done.
And this (written up not quite so train-of-thought) is what I turn in. Shortly afterwards I realize I could have noted that the degree of the removed vertex is at most n-1 by simply noting that there's some vertex it's not connected to (as there's some pair), and so least degree would have worked after all (getting degree at least 1 instead of at most n-1).
And of course shortly after that my pigeonhole thinking leads me to the simple proof. There are n vertices, and n possible degrees from 0 to n-1. Meaning if all the degrees are distinct, there's one of each degree. In particular, there's one connected to nothing else, one connected to everything else, contradiction.
Now I just wish I could see how horrified the grader is on seeing my proof. Hopefully I'll get some sort of comment about it.
-Harry
[0]I'm following here the UChicago convention of referring to all non-final tests as "midterms", regardless of how many or when they are.
