Study Graph Theory to Learn Proofs

What's the best subject to start learning proof-based mathematics? With a dizzying array of subjects to pick from, it's hard to tell which you're ready for and which are specialized subfields of specialized subfields.

Most college curricula offer real analysis, complex analysis, number theory, abstract algebra, and probability theory as introductory proof-based classes. Others may offer a proof-based approach to linear algebra, and more rigorous curricula may even include things like functional analysis. While all of these subjects form the bedrock of higher mathematics, it is my opinion that none of them is well-suited to teaching proofs per se.

Why is this? The reason is that these classes focus on proving information that students have spent nearly two decades learning how to use. As I explained in a previous post, trying to write proofs for this information is like trying to unlearn and then relearn your native language. This mental interference makes learning proofs far more difficult than it should be, and many sadly conclude that proofs are only for the most beard-strokingliest druids of their generation, forever beyond the grasp of mortals.

But wouldn't it be great if there were a mathematical subject that didn't suffer from these problems? What if students could just focus on the proofs and not suffer from chronic and severe "itsobviousis"? Well, there is such a subject, and it's called graph theory.

Graph theory is the study of (wait for it) graphs. These aren't graphs of equations, but graphs made of discrete vertices connected to each other by edges. They are often represented as "ball and stick" models like the one below:

The Petersen graph
The Petersen graph

What makes graph theory a great place to start learning proofs? Three reasons: It's new, it's self-contained, and it separates the proof techniques from the proof topics.

Graph theory's novelty and general detachment from regular "numbers math" make it the perfect choice for a first course in proofs. In fact, some students may be surprised to learn these graph doodads count as math at all, since math, as everyone knows, is about numbers. But not all math is about numbers, and graph theory is not some kind of "let's pretend easier stuff is math to make us feel better about not being good at real math" ruse, either. It's just as interesting and challenging as any other area of math, and it has plenty of real-world applications to boot. By starting with a blank slate, students are much less likely to get confused by their existing knowledge, and are not as likely to suffer from artificially high expectations. There is no native language to unlearn in order to relearn, so confusion of that kind is side-stepped altogether.

Graph theory is also fairly self-contained, so the barrier to entry is lower than for other topics. It requires some set theory, some knowledge of induction and many other interesting proof techniques, but in general it does not require many years of study of lower-level subjects to comprehend. In contrast, partial differential equations requires knowledge of multivariable calculus, which in turn requires knowledge of calculus and some linear algebra, which both in turn require knowledge of algebra. By the time you need to incorporate other areas of mathematics to in order to understand topics like probabilistic graph algorithms or spectral theory, you'll have gained more than enough experience to be able to learn those topics on your own.

Finally, graph theory has proof techniques that are easier to separate from its subject matter. Instead of trying to use algebra to write proofs about algebra, which is very confusing, graph theory makes use of set theory, induction, and other proof techniques to prove things about graphs. It is precisely this difference between the chisel and the marble that makes sculpting the proofs much easier. The only place for you to focus your attention is in the proper direction, since you have no prior knowledge to distract you in the first place.

In summary, graph theory is a great place to start learning proofs because it does not suffer from the problems of familiarity afflicting more typical subjects such as real analysis. And heck, it's just fun to visualize, and it provides an interesting break from a life of numbers math. And if none of these reasons is enough, I'll leave you with one more: you'll learn you how to solve the Good Will Hunting problem.