Lemma: sum of the degrees of the nodes is twice the number of edges.
Proof: We proceed by induction on the number of edges. If a graph has 0 edges, the the sum of degrees of edges is 0=2(0). Now, by way of induction, assume, for all graphs with n edges, the sum of the degrees of the nodes 2n; we wish to show that, for all graphs with n+1 edges, the sum of the degrees of the nodes is 2(n+1). But the sum of the degrees of the nodes is (2n)+2 = 2(n+1). ∎
The theorem follows as a corollary.
If you want practice proving things and haven’t had much experience so far, I’d recommend Mathematics for Computer Science, a textbook from MIT and distributed under a free license, along with the associated video lectures *. To use Terry Tao’s words, Sipser is writing at both level 1 and 3: he’s giving arguments an experienced mathematician is capable of filling in the details to form a rigorous argument, but also doing so in such a way that a level 1 mathematician can follow along. Critically, however, from what I understand from reading Sipser’s preface, he’s definitely not writing a book to move level 1 mathematicians to level 2, which is a primary goal of the MIT book. If you’re looking to prove things because you haven’t done it much before, I infer you’re essentially looking to transition from level 1 to 2, hence the recommendation.
A particular technique I picked up from the MIT book, which I used here, was that, for inductive proofs, it’s often easier to prove a stronger theorem, since it gives you stronger assumptions in the inductive step.
PM me if you want someone to look over your solutions (either for Sipser or the MIT book). In the general case, I’m a fan learning from textbooks and believe that working things out for yourself without being helped by an instructor makes you stronger, but I’m also convinced that you need feedback from a human when you’re first getting learning how to prove things.
* The lectures follow an old version of the book, which ~350 pages shorter and, crucially, lacks exercises.
I think it’s actually cleaner to prove the theorem non-inductively (though I appreciate that what GS asked for was specifically a cleaned-up inductive proof). E.g.: “Count pairs (vertex,edge) where the edge is incident on the vertex. The number of such pairs for a given vertex equals its degree, so the sum equals the sum of the degrees. The number of such pairs for a given edge equals 2, so the sum equals twice the number of edges.”
(More visually: draw the graph. Now erase all of each edge apart from a little bit at each end. The resulting picture is a collection of stars, one per vertex. How many points have the stars in total?)
I’ve actually never studied automata, computability, or complexity before either, so that’s really why I picked up Sipser. But I’m downloading your other recommendation now (just moved, mobile Internet only); I can certainly imagine that some books are more useful than others for learning proof, I just saw an opportunity to practice and see how my natural ability is. I’ll try to include things more specifically for learning proof in my diet. I sure will PM you if I need some feedback (I expect to), thanks.
Lemma: sum of the degrees of the nodes is twice the number of edges.
Proof: We proceed by induction on the number of edges. If a graph has 0 edges, the the sum of degrees of edges is 0=2(0). Now, by way of induction, assume, for all graphs with n edges, the sum of the degrees of the nodes 2n; we wish to show that, for all graphs with n+1 edges, the sum of the degrees of the nodes is 2(n+1). But the sum of the degrees of the nodes is (2n)+2 = 2(n+1). ∎
The theorem follows as a corollary.
If you want practice proving things and haven’t had much experience so far, I’d recommend Mathematics for Computer Science, a textbook from MIT and distributed under a free license, along with the associated video lectures *. To use Terry Tao’s words, Sipser is writing at both level 1 and 3: he’s giving arguments an experienced mathematician is capable of filling in the details to form a rigorous argument, but also doing so in such a way that a level 1 mathematician can follow along. Critically, however, from what I understand from reading Sipser’s preface, he’s definitely not writing a book to move level 1 mathematicians to level 2, which is a primary goal of the MIT book. If you’re looking to prove things because you haven’t done it much before, I infer you’re essentially looking to transition from level 1 to 2, hence the recommendation.
A particular technique I picked up from the MIT book, which I used here, was that, for inductive proofs, it’s often easier to prove a stronger theorem, since it gives you stronger assumptions in the inductive step.
PM me if you want someone to look over your solutions (either for Sipser or the MIT book). In the general case, I’m a fan learning from textbooks and believe that working things out for yourself without being helped by an instructor makes you stronger, but I’m also convinced that you need feedback from a human when you’re first getting learning how to prove things.
* The lectures follow an old version of the book, which ~350 pages shorter and, crucially, lacks exercises.
I think it’s actually cleaner to prove the theorem non-inductively (though I appreciate that what GS asked for was specifically a cleaned-up inductive proof). E.g.: “Count pairs (vertex,edge) where the edge is incident on the vertex. The number of such pairs for a given vertex equals its degree, so the sum equals the sum of the degrees. The number of such pairs for a given edge equals 2, so the sum equals twice the number of edges.”
(More visually: draw the graph. Now erase all of each edge apart from a little bit at each end. The resulting picture is a collection of stars, one per vertex. How many points have the stars in total?)
I really appreciate this comment, thank you.
I’ve actually never studied automata, computability, or complexity before either, so that’s really why I picked up Sipser. But I’m downloading your other recommendation now (just moved, mobile Internet only); I can certainly imagine that some books are more useful than others for learning proof, I just saw an opportunity to practice and see how my natural ability is. I’ll try to include things more specifically for learning proof in my diet. I sure will PM you if I need some feedback (I expect to), thanks.