Vertices and Edges (An introduction to graph theory)

An interesting area of mathematics is graph theory, and it deals with a simple question: how do things connect together? In graph theory, we’re interested in vertices (also called nodes) that have relationships with other nodes. These relationships are called edges (or branches), and with these two ideas, we can explore many different and interesting problems. However, the reason I’m bringing this up now is that I’ve been watching a superb series of videos that explain the workings of graph theory, and I wanted to both share the series and comment on some of the problems. To do this, we’ll have to go through a bit of the theory to ground ourselves comfortably, though we won’t go into enormous depth.

But first, the series is called Bits of Graph Theory, and it’s created by Dr. Sarada Herke. I’m barely past the beginning, and I’ve already found the videos to be immensely useful. So if you wanted to go into more depth, I really recommend that you check out her videos. You won’t regret it.

With that out of the way, let’s begin.

So what’s a graph? At it’s most bare form, a graph is a collection of vertices and edges. If you want to go really minimalist, a graph could be simply a collection of vertices. From there, we can connect vertices in any way that is pertinent to the situation at hand.

What I love about graph theory over a lot of other mathematics is that it’s so visual. This is true for other subjects within mathematics, but you usually have to build up a lot of theory and background before you start seeing those visual connections. For graph theory, on the other hand, things are immediately visual (and can even be helpful in solving the problem), as you can see from a few examples.

These are all examples of perfectly valid graphs. Some look strange, but they all represent relationships between the vertices. One thing to note is that we don’t care how a graph looks, as long as the structure is the same. As such, these two graphs are equivalent, if perhaps a little ugly.

So if you want to make a graph, you just need to draw some vertices and connect them with various lines. One thing you cannot do is have a “hanging” edge. Put differently, every edge has to be capped by a vertex on each side.

Next, a useful property of vertices is what is called the degree of a vertex. It’s the idea that each vertex has a certain number of connections to it, marked by the edges that go to and from the vertex. Here’s a graph with the degree of each vertex.

From this, we have a special case. What if every vertex has the same degree? More specifically, if any vertex in a specific graph G has a degree of k, then we call the graph k-regular. I’m introducing this because I want us to tackle a nice problem involving regular graphs.

Lastly, I want to introduce the notion of a simple graph. This just means we don’t have any loops or “multiple connections” in the graph. I could go on and on about them, but I think a sketch will be more useful.

So that’s the basics of graph theory, in a very brief nutshell. Obviously, there’s a lot more to cover, but I wanted to bring these ideas up because we will use them next time to tackle a problem that Dr. Herke in her video series poses, and there’s a nice way to visualize the problem that I have found. Stay tuned for that!

First Principles

When I was younger and first going through the “jump” between secondary mathematics and physics to that of CÉGEP and university, I always got frustrated when teachers would just shrug their shoulders when we grumbled about having too many things to remember for the test. Their advice was to simply remember the fundamentals, and rederive any result that was needed afterward.

I still think that this isn’t the most useful advice for exam that only last for fifty minutes. During this time, the tests are usually a mad scramble to make sure one can answer all the questions in the allotted time. If you have to pause and waste five to ten minutes on a question, it can be difficult to finish the rest of the test.

However, I’m come to really understand my teachers’ advice for learning in general. As my mathematics professors keep on telling me, “Mathematicians are lazy. We try to remember as little as possible, while secure in the knowledge that we can recover the result if we want to.”

Does that mean I forget what the real number line is, or work through a delta-epsilon limit proof every time I run into a new problem? Of course not. For most applications and situations, this would be overkill. But what it means is that I try to remember the fundamentals of concepts, and I avoid trying to remember special scenarios. This is effective because, if you deeply understand how the concept works, it’s not too difficult to extend to certain special cases. The converse is not true. If you are able to remember the special cases, it doesn’t mean that you understand what’s going on, it means you know what the formula is for that situation.

In my experience with tutoring students in secondary school, this is most manifest in the manipulating of algebraic equations. This is arguably the basis of most of the mathematics that the average student will encounter for most of their lives. Being able to solve and manipulate equations is important for statistics, probability, calculus, and linear algebra (not to mention any physics or most other science courses). Not being able to manipulate equations introduces a huge crutch into one’s mathematical ability (at least, at the level of secondary school and introductory classes as I mentioned above). It’s therefore extremely important that students find themselves comfortable with the manipulation of equations.

Unfortunately, this doesn’t seem to be a skill that is easily acquired, and it seems to stem from a core issue: students don’t seem to be taught that manipulating equations requires that you do the same action on both sides of an equation.

It’s a simple enough concept, but a lot of a student’s mathematical education rests on the shoulders of understanding this concept, so it needs to be understood. Therefore, if there is one fundamental idea about solving equations that needs to be remembered, it’s this.

In a similar vein, when students solve equations, they learn of multiple methods: comparison, substitution, and elimination. These are presented as “different” ways to solve equations, but what seems to often be missed on the students is that they are all essentially the same, albeit in special scenarios. Substitution and comparison are basically identical, and elimination is simply adding terms on both sides of an equation. As such, instead of remembering all of the methods, you simply need to remember two ideas:

  • You have to apply an operation to both sides of an equation (as I said above).
  • When you have an equality between two expressions, you can swap one for the other.

Of course, these two ideas aren’t necessarily obvious to the student who is first learning algebra. However, with a good number of examples and practice, I’m confident that a student armed with these two principles can begin to understand equations on a deeper level, without thinking about “bringing X over to the other side of an equation”.

This is the kind of thinking I try to apply when I learn new concepts. As I go further down the mathematical and physical roads, I’ve learned so many things that it’s difficult to remember everything. Therefore, I keep note of important concepts. This lets me retain the crux of many concepts, without necessary needing the details. Then, if I find myself in a situation where the details become more important, I can always refresh my knowledge by looking at my notes or in textbooks. I think this method is easier on the mind and allows one to search for the deeper connections that various subjects have with each other, because you’re not focusing as much on the details.

Contrapositive Implications as Dominoes

If you’ve ever learned logic, you know that jumping from one piece of information to another (through implication) isn’t always clear. You might remember something about if A implies B, then not B implies not A, and the like. What I want to do today is try and explore these concepts in a more visual way, which hopefully will let you remember these concepts with greater ease.

To do this, we’re going to use an analogy that involves dominoes. We will start with three propositions or statements, and call them A, B, and C. These will each be represented by a domino, and they will be lined up in the same order. Also note that I will just refer to these dominoes as A, B, and C from now on.

Initial set up

Let’s begin by imagining that we can only push a domino forward. That is, if we decide to knock down a domino, we need to push it to the right. This isn’t any special condition, but it’s just something that we will impose for now to make the situation more clear.

What happens if we push A? First, it will hit B, and then B will hit C. As such, we can say that A implies B, and B implies C. But, as we know from a chain of dominoes, the act of pushing A guarantees that C will fall, too (assuming you build your line well). As such, we can also say that A implies C.

Implications

Let’s look at a slightly different situation. What if I tell you that C falls? What can you tell me about A and B?

You might be tempted to say that A and B fall, but you should resist this conclusion! Remember, we want a statement that always applies, so it’s helpful to go back to your dominoes to test the implications. If C falls, what are the options for what happened?

There are three different possibilities for what could have happened.

  • A was pushed, which we have already seen will guarantee that C falls. In this case, all three dominoes will fall.
  • B is pushed, which we have also seen will cause C to fall. In this case, A is still upright, but the other two have fallen.
  • C is pushed, which means it obviously falls. In this case, the other two are still standing.

Because having C fall means any one of these three options occurred, we cannot say with certainty what happened to the other dominoes. Both could have fallen, or only B could have fallen. We know that it can’t be only A that fell, since that would imply the other two fell as well.

This might seem like a waste of time, because the conclusion we’ve come to is that having C fall tells us precisely nothing about the state of the other two. However, there’s another way to look at these results that will give us insight. What if C had not fell? What could we say about the other two dominoes?

Let’s look at it case by case. We know that pushing A automatically means C will fall. Likewise, pushing B means C will fall. Therefore, if we don’t find that C has fallen, then we can be sure that neither A or B were pushed. There’s simply no way to push the two first dominoes without causing the last one to fall.

This kind of statement is called the contrapositive. Formally, if we have a conditional statement, which is just a fancy way of saying that one smaller statement implies another, and it is of the form A implies B, then the contrapositive is given by not B implies not A. The way we write it is like this:

Notation

Hopefully, the example of dominoes makes sense for why the contrapositive works. It’s because we have a direct relationship of one domino causing a chain reaction with a bunch of other dominoes. If one part of the train further down has not fell, it has to be that the other parts have not fallen.

Practically, this means that you won’t succumb to the error of thinking that if one event implies a second, then automatically having the second event occur implies the first. It could be true, just like we saw with our three options above, but when we are making use of logical implications, we want to use the fact that one thing guarantees the other. Therefore, when you’re dealing with logical statements, think of the dominoes. Does having one statement happen imply the next, or is there another way it could have happened (without the first)?

Units

When students first start working in mathematics, units aren’t really something to worry about. Indeed, students begin with doing arithmetic, where there’s little need for extra fuss about units. Students get used to writing equations without ever thinking about units.

However, students are then suddenly thrown into science classes where there is an emphasis on having the correct units throughout a calculation. This isn’t a difficult concept, but it can seem mysterious to those who have only heard it from a teacher as if it’s a law handed down from the great mathematicians of history. The reality is much more simple, and being able to work with units is something called dimensional analysis, which can be a pretty powerful tool. So, let’s get started.

An equation isn’t just about the numbers

You know what an equation is. It’s some mixture of symbols and numbers that have an “$=$” sign somewhere in the middle. Simple enough, but let’s write down an example. If I wanted to write down the area of a triangle. It’s given by the following formula:

, where $b$ is the base of the triangle and $h$ is its height.

This is probably one of the first things you saw in secondary school. It’s a nice formula, and I’m sure you’ve spent many assignments calculating the area of various triangles. You might have even been told that, when calculating an area, when you wrote down your final answer, you should slap on so-called “area units”, like $m^2$ or $cm^2$. It might not have even been something you thought about. Instead, you just made sure to remember to include it at the end, or else your teacher would take off marks.

Maybe you wondered to yourself, “Why do they care so much about units?” I’m going to now answer your question.

In physics (and science in general), we study the world around us. Unlike mathematicians, we are very concerned with describing things that are physically possible. In the process of finding things out about the universe, we quickly found out that the best way to describe what we figured out was through mathematics. Still, when we write equations down, we don’t want to just have them output numbers. We want numbers that have meaning. Put more explicitly, there’s a huge difference between $3J$, $3m$, and $3s$. As such, we really do need units in order to make sure we get answers that have physical relevance.

Here’s the punchline: an equation means that both sides are the same.

Okay, you’re probably rolling your eyes at me. Of course both side of an equation are equal! That’s why it’s called an equation.

Fair enough, but in physics this has a slightly more subtle meaning. It also means that the units of the equation are equal, too. Let’s go back to the example above in order to get a feel for this. We had $A=\frac{1}{2} bh$, and we know that $A$ represents an area, which means it has units of something like $m^2$. This means that the other side of the equation needs the same units as well. The factor of $\frac{1}{2}$ doesn’t have any units, so we treat it as a pure number (which means it doesn’t contribute to the units of the expression). We then have $b$ and $h$, which each have units of lenght, such as $m$. Therefore, since we are taking the product $bh$, we multiply the units as well, giving us $m*m=m^2$, just like the left hand side. The units agree, and so we are done.

Units work like this in every equation you ever want to make. You can even think of units as “variables” that obey the same algebra as regular variables. In particular, you cannot simplify $a+b$ since they aren’t the same “thing”. Similarly, you can’t suddenly be adding a length and an area together, since their units wouldn’t agree ($m+m^2=?$). However, multiplication and division are allowed, in the sense that you can have units such as speed ($\frac{m}{s}$) or force ($\frac{(kg)m}{s^2}$).

The bottom line is that units have to always agree, which is why you can easily check if an answer you come up with in a calculation makes sense. Did you verify that you didn’t add units that can’t be added? Do both sides of your equation have the same units? This is a mistake I see many students make, and it’s usually the first line of attack I make into having students fix their equations.

This also answers another question you might have posed at one time. Why do some constants in formulas like ($\vec{F}=-G\frac{mM}{r^3}\vec{r}$) have such funny-looking units ($[G]=\frac{[L]^3}{[M][T]^2}=\frac{m^3}{(kg)s^2}$?

The reason is simple: to make the units work out in the equation! If we have a force on the left side, we need the units of a force on the right hand side. Thus, we need to have the units on $G$ that we have above if we want the equation to satisfy unit analysis.


Hopefully, I’ve made the case for why units are important and why they aren’t just something we tack on at the end of a calculation. They have significance, and so for that reason, it’s important to be able to reason with the units of an equation. It’s a very quick check to make sure the equation you’re creating to solve a problem is within the right ballpark. As long as you remember that the units on both sides of an equation need to come out to the same thing (even if they initially look widely different), it becomes easier to understand equations.