Mathematical Induction Applied to Graph Theory
Algorithmically Speaking - #11: A not-so-common introduction to one of the most powerful mathematical tools.
Hello there, and welcome to a new edition of Algorithmically Speaking!
Today, we will discuss Mathematical Induction, specifically how it can be used in graph theory to demonstrate theorems and propositions.
In this post, I will present one of the fundamental propositions of graph theory and walk you through proving that the proposition holds. I will ensure that the content is accessible to all, regardless of your familiarity with the art of proving theorems in mathematics.
Whether you are a math connoisseur or a total newb to the field, I think you will benefit tremendously from today’s discussion. This example shows why people like me invest a considerable part of their lives diving deeper and deeper into science, specifically looking at the intersection of math and computer science and how these principles can be applied in real-world scenarios.
In order, this is our agenda for today:
🤔 What is mathematical induction? — an introduction to mathematical induction and a classic example of how to use it.
⭐ A fundamental proposition of graph theory — some basic graph theory concepts and a fundamental proposition.
💡 Mathematical Induction to the Rescue — the application of mathematical induction for proving a proposition in graph theory.
This article is part of a chapter on Fundamental Definitions of graph theory in my upcoming book, The Competitive Programmer Graphs Handbook. You can read all the details here:
You can support the book by preordering your digital, DRM-free copy, with early and frequent updates, including all future editions.
Let’s get started!
🤔 What is Mathematical Induction?
Mathematical induction is a method for proving that a statement P(n) is true for every natural number n, that is, that the infinitely many cases P(0), P(1), P(2), P(3),… all hold. This is done by proving a simple case and then showing that if we assume the claim is valid for a given case, the following case is also valid.
A proof by induction consists of two cases. The first, the base case, proves the statement for n=0 without assuming knowledge of other cases. The second case, the induction step, proves that if the statement holds for any given case n=k, it must also hold for the next case n=k+1. These two steps establish that the statement holds for every natural number n. The base case does not necessarily begin with n=0, but often with n=1, and possibly with any fixed natural number n=N, establishing the statement’s truth for all natural numbers n≥N
.
Since the premise of mathematical induction is that it works for proving statements concerning natural numbers, it is expected to see it being used in the field of number theory. For example, a classic example is to confirm that the sum of the first n natural numbers is equal to n * (n + 1) / 2.
More formally,
The proof using mathematical induction would be something like this, formatted as best as I can using the substack editor:
If k = 0, 0 = 0 * (0 + 1) / 2.
If k > 0, we assume that for a particular k,
P(k)
holds.That is, 0 + 1 + … + k = k * (k + 1) / 2.
It follows that 0 + 1 + … + k + (k + 1) = k * (k + 1) / 2 + (k + 1).
After some algebraic simplification, we get that 0 + 1 + … + k + (k + 1) = (k + 1) * (k + 2) / 2. ∎
The induction step is established since P(k + 1) holds. Since the base case and the induction step have been proved true by mathematical induction, the statement P(n) holds for every natural number n.
⭐ A Fundamental Proposition of Graph Theory
In the second chapter of my upcoming book, I walk you through a series of basic definitions and concepts in graph theory that lay the basis for fully understanding the forthcoming chapters. One of these basic concepts is what we refer to as degrees.
The degree of a vertex in an undirected graph G is the number of edges incident to that vertex. For a vertex u, the degree of u equals the number of edges e = (x, y) such that x = u or y = u. In directed graphs, the degree concept differs slightly because the edges have direction. The in-degree of a vertex u refers to the number of edges that enter u. The number of edges that leave the vertex is called the out-degree.
For today’s discussion, we will focus on a fundamental proposition that holds for undirected graphs. The proposition is the following,
Let G = < V, E > be an undirected graph. The number of vertices with odd degrees is even.
Let’s see how to prove this statement using mathematical induction!
💡 Mathematical Induction to the Rescue
Here’s the sketch of a proof for the previous proposition, as rigorous as I can make it look in a Substack blog.
Proof. Let k be the number of edges in G:
If k = 0, every vertex has an even degree, so there are zero vertices with an odd degree, which is an even number.
k ⇒ k + 1. Let G =< V, E > be any graph with k + 1 edges. Taking an arbitrary edge e from G, we obtain G′ = G < V, E − e >. By the induction hypothesis, in G′, the number of vertices with odd degrees is even. Three cases can occur when the edge e is added back:
It is added between two vertices with an even degree in G′. In this case, both will have odd degrees, increasing the number of vertices with odd degrees by two, thus keeping this number even.
The edge is added between two vertices with an odd degree in G′. Here, the opposite happens; these nodes will have an even degree, and the number of vertices with an odd degree will decrease by two. This keeps the number of vertices with odd degrees even.
The edge is added between a vertex with an even degree and another with an odd degree in G′. In this case, the parity of the degree of each change. The number of vertices with odd degrees remains the same. ∎
This proof is beautiful. It takes advantage of the fact that mathematical induction works for natural numbers, applying the proof by induction to the number of edges of the graph, which is always a natural number.
We have explored the concept of mathematical induction and its application in proving theorems in graph theory. We have demonstrated how mathematical induction can prove the fundamental proposition that the number of vertices with odd degrees in an undirected graph is even.
By providing step-by-step explanations and examples, we aimed to make the content accessible to those familiar with and new to mathematics. We hope this discussion has provided valuable insights into the intersection of math and computer science and how these principles can be applied.
Stay tuned for more insightful discussions in future editions.
And that’s it for today! If you are finding this newsletter valuable, consider doing any of these:
1) ✉️ Subscribe to the newsletter — if you aren’t already, consider becoming a free or paid subscriber.
2) 💛 Get early access to my book— thanks to all of you who have contributed to support my writing. The book I'm writing covers this and similar topics in more depth.
3) 🍻 Read with your friends — this newsletter grows because readers share. I don’t use social media too much to advertise my writing. I’m counting on you!
Have a great day! ☀️
Alberto
Nice proof! I love mathematical proofs, hope to read more like this :)