Prove that the sum of the degrees of the vertices of any finite graph is even.
This is my proof:
Each edge ends at two vertices. If we begin with just the vertices and no edges, every
vertex has degree zero, so the sum of those degrees is zero, an even number. Now add edges
one at a time, each of which connects one vertex to another, or connects a vertex to itself (if
you allow that). Either the degree of two vertices is increased by one (for a total of two) or
one vertex’s degree is increased by two. In either case, the sum of the degrees is increased
by two, so the sum remains even.
Is this proof correct / sufficient?
Best Answer
Your proof works.
Depending on which level of rigor is expected of you, it may be that you're supposed to rephrase "add edges one at a time" into a proof by mathematical induction over the number of edges in the graph.
This will generally only be the case if you're in a course where the mechanics of induction proofs have been hammered into you ad nausaeam already. That could be the case in an omnibus "discrete mathematics" course, for example.