I’ve been trying to prove things more often because I haven’t done it a lot and I’m interested in a mathy career. I started reading Sipser’s Introduction to the Theory of Computation and came across a chance to try and prove the statement ‘For every graph G, the sum of the degrees of all nodes in G is even.’ I couldn’t find other proofs online, so I thought I’d share mine here before I look at the book, especially because mine might be completely different and I wouldn’t really know if it was any good.
A graph G equals the set of the set of nodes/vertices V and the set of edges E. That is, G = {V, E}.
Let G be the empty graph with no nodes and no edges. The sum of the degrees of the nodes of this graph is zero, which is even.
Let G be the graph with one node and no edges. The sum of the degrees of the nodes of this graph is zero, which is even.
Let G be an arbitrary, non-empty graph such that the sum of the degrees of the nodes in G is even.
Let G’ be a graph identical to G in all respects except that it contains an additional node that is a member of an additional pair in E with one other node. (That is, ‘make a new node’ and ‘make an edge’ to attach it to an existing node with.) The degree of a node equals the number of pairs in E of which the node is a member. Each pair contains two elements, so that if a graph G has i edges and j equals the sum of the degrees of all nodes in G, then the sum of the degrees of all nodes in a graph G’ with i+1 edges will equal j+2. Because this is true for an arbitrary, non-empty graph G, it is true for every non-empty graph G. j is even by assumption, and the sum of two even numbers is even, so j+2 is even. Because this is true for an arbitrary, non-empty graph G’, it is true for every non-empty graph G.
For every non-empty graph G, the sum of the degrees of all nodes in G is even. The sum of the degrees of all nodes in the empty graph is even. Therefore, for every graph G, the sum of the degrees of all nodes in G is even.
FYI, this is called the sum of degrees theorem. In fact, the sum of degrees is not only an even number, but twice the number of edges in the graph. This is due to Euler, I think. He used the famous Koenigsberg bridges problem as a motivation for thinking about graphs.
Your operation for turning G into G’ doesn’t let you construct all graphs, e.g. K3 (the triangle graph) can’t be formed like that. The rest of that paragraph is probably more dense than it needs to be. You’re on the right track, but I can’t quite tell if you actually rely on that construction.
Thanks for the feedback. I think you can construct all graphs and use it to prove the theorem if you prove that you can add an arbitrary number of additional edges and nodes to an arbitrary graph and keep the sum of the degrees of all nodes even, instead of just one additional node and one additional edge. I also see what you mean about this:
I can’t quite tell if you actually rely on that construction.
I think the inductive hypothesis in the rest of that paragraph might be enough, and I just wrote down how I intuitively visualized the proof before that without realizing that it wasn’t necessary (nor sufficient, I now know) for the argument to carry through.
If you have an idea of how you would write the proof, I’d be interested in seeing it. I looked at the book and the proof is actually even less formal there.
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.
If I were doing it inductively, I’d go in the other direction, removing edges instead of adding them. Take a graph G with n>0 edges, and remove an edge to get G’. The degree sum of G’ is two less than the degree sum of G (two vertices lose one degree, or one vertex loses two degree). Then induction shows that the degree sum is twice the edge count. There are probably simpler proofs, but having been primed by yours, this is the one that comes to mind.
I feel like being completely formal is the sort of thing that you learn to do at the beginning of your math education, and then gradually move away from it. But you move to a higher class of non-rigor than you started from, where you’re just eliding bookwork rather than saying things that don’t necessarily work. E.g. here I’ve omitted the inductive base case, because I consider it obvious that the base case works, and the word “induction” tells me the shape of the argument without needing to write it explicitly.
I’ve been trying to prove things more often because I haven’t done it a lot and I’m interested in a mathy career. I started reading Sipser’s Introduction to the Theory of Computation and came across a chance to try and prove the statement ‘For every graph G, the sum of the degrees of all nodes in G is even.’ I couldn’t find other proofs online, so I thought I’d share mine here before I look at the book, especially because mine might be completely different and I wouldn’t really know if it was any good.
A graph G equals the set of the set of nodes/vertices V and the set of edges E. That is, G = {V, E}.
Let G be the empty graph with no nodes and no edges. The sum of the degrees of the nodes of this graph is zero, which is even.
Let G be the graph with one node and no edges. The sum of the degrees of the nodes of this graph is zero, which is even.
Let G be an arbitrary, non-empty graph such that the sum of the degrees of the nodes in G is even.
Let G’ be a graph identical to G in all respects except that it contains an additional node that is a member of an additional pair in E with one other node. (That is, ‘make a new node’ and ‘make an edge’ to attach it to an existing node with.) The degree of a node equals the number of pairs in E of which the node is a member. Each pair contains two elements, so that if a graph G has i edges and j equals the sum of the degrees of all nodes in G, then the sum of the degrees of all nodes in a graph G’ with i+1 edges will equal j+2. Because this is true for an arbitrary, non-empty graph G, it is true for every non-empty graph G. j is even by assumption, and the sum of two even numbers is even, so j+2 is even. Because this is true for an arbitrary, non-empty graph G’, it is true for every non-empty graph G.
For every non-empty graph G, the sum of the degrees of all nodes in G is even. The sum of the degrees of all nodes in the empty graph is even. Therefore, for every graph G, the sum of the degrees of all nodes in G is even.
FYI, this is called the sum of degrees theorem. In fact, the sum of degrees is not only an even number, but twice the number of edges in the graph. This is due to Euler, I think. He used the famous Koenigsberg bridges problem as a motivation for thinking about graphs.
Good work on thinking about proofs, +1 to you.
I love that I can come to this website and have one of Judea Pearl’s former students check my elementary graph-theoretic proofs.
But really, thanks for the encouragement. I had also been wondering if it had a name.
Your operation for turning G into G’ doesn’t let you construct all graphs, e.g. K3 (the triangle graph) can’t be formed like that. The rest of that paragraph is probably more dense than it needs to be. You’re on the right track, but I can’t quite tell if you actually rely on that construction.
Thanks for the feedback. I think you can construct all graphs and use it to prove the theorem if you prove that you can add an arbitrary number of additional edges and nodes to an arbitrary graph and keep the sum of the degrees of all nodes even, instead of just one additional node and one additional edge. I also see what you mean about this:
I think the inductive hypothesis in the rest of that paragraph might be enough, and I just wrote down how I intuitively visualized the proof before that without realizing that it wasn’t necessary (nor sufficient, I now know) for the argument to carry through.
If you have an idea of how you would write the proof, I’d be interested in seeing it. I looked at the book and the proof is actually even less formal there.
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.
If I were doing it inductively, I’d go in the other direction, removing edges instead of adding them. Take a graph G with n>0 edges, and remove an edge to get G’. The degree sum of G’ is two less than the degree sum of G (two vertices lose one degree, or one vertex loses two degree). Then induction shows that the degree sum is twice the edge count. There are probably simpler proofs, but having been primed by yours, this is the one that comes to mind.
I feel like being completely formal is the sort of thing that you learn to do at the beginning of your math education, and then gradually move away from it. But you move to a higher class of non-rigor than you started from, where you’re just eliding bookwork rather than saying things that don’t necessarily work. E.g. here I’ve omitted the inductive base case, because I consider it obvious that the base case works, and the word “induction” tells me the shape of the argument without needing to write it explicitly.