Discrete Math

The degree of a vertex in an undirected graph

In graph theory, a graph consists of vertices and edges connecting these vertices (though technically it is possible to have no edges at all.) The degree of a vertex represents the number of edges incident to that vertex. In this lesson, we will explore what that means with examples and look at different cases where the degree might not be as simple as you would guess.

Table of Contents

The degree of a vertex in a simple graph
Multigraphs and the degree of a vertex
Pseudographs and the degree of a vertex
Summary

[adsenseWide]

The degree of a vertex in a simple graph

A simple graph is the type of graph you will most commonly work with in your study of graph theory. In these types of graphs, any edge connects two different vertices. An example of a simple graph is shown below.

An example of a simple graph. There are 5 vertices. Each edge connects two different vertices.

We can label each of these vertices, making it easier to talk about their degree. When you are trying to determine the degree of a vertex, count the number of edges connecting the vertex to other vertices.

A graph with five vertices. They have been labelled v1, v2, v3, v4, and v5.

Consider first the vertex \(v_1\). There are two edges incident with this vertex. Therefore, \(v_1\) has degree 2.

The vertex labelled v1 has 2 edges connected to it. Therefore the degree of the vertex is 2.

Using a common notation, we can write: \(\text{deg}(v_1) = 2\).

In fact, the degree of \(v_4\) is also 2. Vertex \(v_2\) has 3 edges connected to it, so its degree is 3. Vertex \(v_3\) has only one edge connected to it, so its degree is 1, and \(v_5\) has no edges connected to it, so its degree is 0.

Graph with the degree of each vertex shown. There is one vertex of degree 3, two vertices of degree 2, one of degree 1, and one of degree 0.

Not all graphs are simple graphs. We still must consider two other cases: multigraphs and pseudographs.

Multigraphs and the degree of a vertex

Multigraphs allow for multiple edges between vertices. An example of a multigraph is shown below.

An example of a multigraph. There are four vertices. The vertex v1 and vertex v2 are connected by three edges. This is why this is a multigraph and not a simple graph.

In a multigraph, the degree of a vertex is calculated in the same way as it was with a simple graph. In the graph above, the vertex \(v_1\) has degree 3, since there are 3 edges connecting it to other vertices (even though all three are connecting it to \(v_2\)).

Graph showing the degree of a vertex in a multigraph. The vertex v1 has three edges incident to it (connecting it to other vertices), so it has degree 3 even though all three edges connect it to v2.

We can now use the same method to find the degree of each of the remaining vertices.

Image showing the degree of each vertex in a multigraph. The vertex v1 has 3 edges connected to it, so its degree is 3. v2 has 5 edges incident to it, so its degree is 5. v3 and v4 each have only one edge incident to them, so their degrees are each 1.

Hint: You can check your work by using the handshaking theorem. It states that the sum of all the degrees in an undirected graph will be 2 times the number of edges. In the example above, the sum of the degrees is 10 and there are 5 total edges.

Pseudographs and the degree of a vertex

Pseudographs are not covered in every textbook, but do come up in some applications. These are graphs that allow a vertex to be connected to itself with a loop. In the example below, we see a pseudograph with three vertices. Vertex v₂ and vertex v₃ each have an edge connecting the vertex to itself.

A pseudograph with three vertices. Two of the vertices are connected to themselves with an edge, called a loop.

When calculating the degree of a vertex in a pseudograph, the loop counts twice.

A pseudograph showing the degree of each vertex. Vertex v1 has one edge connected to it, so its degree is 1. Vertex v2 has two edges connected to it and a loop, so its degree is 4. Vertex v3 has one edge and a loop, so its degree is 3.

In the graph above, vertex \(v_2\) has two edges incident to it. But, it also has a loop (an edge connecting it to itself). This adds 2 to the degree, giving this vertex a degree of 4. Similarly, \(v_3\) has one edge incident with it, but also has a loop. Therefore its degree is 3.

Note that with this convention, the handshaking theorem still applies to the graph. There are 4 edges, since each loop counts as an edge and the total degree is:

\(1 + 4 + 3 = 8 = 2 \times \text{(number of edges)}\)

[adsenseLargeRectangle]

Summary

The degree of a vertex is the number of edges incident to the vertex. This is simply a way of saying “the number of edges connected to the vertex”. It is common to write the degree of a vertex v as deg(v) or degree(v). If you are working with a pseudograph, remember that each loop contributes 2 to the degree of the vertex.

Negating the conditional if-then statement p implies q

The negation of the conditional statement “p implies q” can be a little confusing to think about. But, if we use an equivalent logical statement, some rules like De Morgan’s laws, and a truth table to double-check everything, then it isn’t quite so difficult to figure out. Let’s get started with an important equivalent statement to the conditional.

[adsenseWide]

One way to write the conditional is: “if p, then q”. Thus, if you know p, then the logical conclusion is q. Consider this as you review the following truth table.

Why is this true? Given “p implies q”, there are two possibilities. We could have “p”, and therefore “q” (so q is possibility 1). Or, we could have “not p”, and therefore, we would not have q (so we could use possibility 2 as not p). Thus, “p implies q” is equivalent to “q or not p”, which is typically written as “not p or q”. This is one of those things you might have to think about a bit for it to make sense, but even with that, the truth table shows that the two statements are equivalent.

Using this to negate the statement

Now we can use De Morgan’s laws to negate this statement:

\(\begin{align} \neg \left(p \implies q\right) &\equiv \neg \left(\neg p \lor q \right)\\ &\equiv \neg \neg p \land \neg q\\ &\equiv p \land \neg q\end{align}\)

This shows that the negation of “p implies q” is “p and not q”. If we were to apply this to a real-life statement, then we would have something like the following.

Statement: If I run fast, then I get tired. (p implies q)

Negation: I run fast and I do not get tired. (p and not q)

Verifying with a truth table

Although the work above is enough, you can always double check your results using a truth table. Let’s try it for this negation.

As you can see, we end up with the same truth values for each statement, so they are equivalent and we have verified that we did the negation correctly.

[adsenseLargeRectangle]

Summary

When trying to understand logical statements and how to negate them, it can be helpful to consider equivalent statements and to utilize truth tables to check your work at every stage. Finally, the negation of a statement may not always be what you expect – for example here we saw that the negation of the conditional is actually an “and” statement. As you develop your mathematical intuition for ideas like these, you will feel more and more comfortable with the sometimes surprising results.

Continue your study of discrete math

You may also find the following useful:

Analyzing compound propositions with truth tables

For compound propositions, a truth table shows under what conditions the compound statement is valid. This is just like basic truth tables for “and”, “or”, negation, etc but now we have a statement that utilizes more than one of these logical operators. To see how to approach these, we will carefully work through an example.

[adsenseWide]

Example – compound proposition

Construct the truth table for the following compound proposition.

\(\left(p \vee q\right) \wedge \neg r\)

Step 1: Set up your table

You need to have your table so that each component of the compound statement is represented, as well as the entire statement itself. In this case, that would be p, q, and r, as well as:

\(p \vee q\)
\(\neg r\)
\(\left(p \vee q\right) \wedge \neg r\)

Thus the initial table set up would be:

The order of the columns is not actually all that important. Ideally, you would put p,q,r next to each other so that you can be sure to write ever combination of possible truth values for them without missing any. After that, it is a good strategy to put pieces you will work with together. For instance, the 4th and 5th columns are the statements we combine to make the last column.

Step 2: Write out all the possible combinations of truth values for each individual proposition

In this case, we want to think of all the combinations of truth values for p, q, and r. It is important to be very systematic here so that you don’t miss any possibilities. Here is one way to think about it:

All statements could be true.

Two could be true, which is the same as one false. The false proposition could be any of the three.

Two could be false, which is the same as one true. The true proposition could be any of the three.

All three could be false.

Getting all the combinations covered is very important. A mistake here will throw off the entire table. One quick check, is that by the multiplication rule, there should be \(2 \times 2 \times 2 = 8\) possibilities. We have 8 rows, so that’s a good sign! (although it is still possible we mixed something up somewhere, so always double check).

Step 3: Complete the rest of the table using the basic properties or “and”, “or”, and negation

To complete this table, we need to apply the rules for “or” with p, q, apply the rule for negation for r, and then apply the rule for “and” for the last column. If you dont know these rule, you can review them here: Truth tables for and, or, and negation.

Finding \(p \vee q\). The “or” statement is true in all cases except when both p,q are false.
truth-table-example1-compound1

Finding \(\neg r\). This will have the opposite truth value of r.
truth-table-example1-compound2

Finding \(\left(p \vee q\right) \wedge \neg r\). This is an “and” statement for two of our columns. “And” is only true when both statements are true.
truth-table-example1-compound

Step 4: Bask in the glory that is your final answer

This is it – the final answer. A truth table that allows you to see all the conditions under which the compound proposition is true or false.
truth-table-example1-compound3
In addition to simply being a tool for understanding the compound statement on its own, this could now be used to determine whether or not a system is consistent and, if we were to add some columns to this, whether or not another statement is equivalent to this one. You can also use the truth tables of compound propositions to determine whether or not you are looking at a tautology, contradiction, or neither.

Summary

These types of truth tables don’t have to be difficult as long as you are very systematic with your approach. The issues come up when you lose track of which columns you are working with or when you miss a possible combination of truth values in the very beginning of your set up.

[adsenseLargeRectangle]

Continue reviewing discrete math topics

Previous: Truth tables for the conditional and biconditional (implies, and iff)

Truth tables – the conditional and the biconditional (“implies” and “iff”)

Just about every theorem in mathematics takes on the form “if, then” (the conditional) or “iff” (short for if and only if – the biconditional). Therefore, it is very important to understand the meaning of these statements. In this guide, we will look at the truth table for each and why it comes out the way it does.

[adsenseWide]

As we analyze the truth tables, remember that the idea is to show the truth value for the statement, given every possible combination of truth values for p and q. Therefore the order of the rows doesn’t matter – its the rows themselves that must be correct. For each truth table below, we have two propositions: p and q. They can either both be true (first row), both be false (last row), or have one true and the other false (middle two rows). Writing this out is the first step of any truth table.

The conditional – “p implies q” or “if p, then q”

p-implies-q-the-conditional-truth-table
The conditional statement is saying that if p is true, then q will immediately follow and thus be true. So, the first row naturally follows this definition. Similarly, the second row follows this because is we say “p implies q”, and then p is true but q is false, then the statement “p implies q” must be false, as q didn’t immediately follow p.

The last two rows are the tough ones to think about. So let’s look at them individually.

Row 3: p is false, q is true.
Think of the following statement. If it is sunny, I wear my sunglasses. If p is false, and q is true, then this is saying that it is not sunny, but I wore my sunglasses anyway. This certainly doesn’t invalidate my original statement as I might just like my sunglasses. So if p is false, but q is true, it is reasonable to think “p implies q” is still true.
Row 4: p is false, q is false.
Using the example about sunglasses above, this would be equivalent to it not being sunny and me not wearing my sunglasses. Again, this wouldn’t invalidate my statement that “if it is sunny, I wear my sunglasses”. Therefore, if p is false and q is true, “p implies q” is still true.

Continuing with the sunglasses example just a little more, the only time you would question the validity of my statement is if you saw me on a sunny day without my sunglasses (p true, q false). Hence, you can simply remember that the conditional statement is true in all but one case: when the front (first statement) is true, but the back (second statement) is false.

The biconditional – “p iff q” or “p if and only if q”

p-iff-q-biconditional-truth-table

If and only if statements, which math people like to shorthand with “iff”, are very powerful as they are essentially saying that p and q are interchangeable statements. When one is true, you automatically know the other is true as well. Also, when one is false, the other must also be false. This is reflected in the truth table. Whenever the two statements have the same truth value, the biconditional is true. Otherwise, it is false.

The biconditional uses a double arrow because it is really saying “p implies q” and also “q implies p”. Symbolically, it is equivalent to:

\(\left(p \Rightarrow q\right) \wedge \left(q \Rightarrow p\right)\)

This form can be useful when writing proof or when showing logical equivalencies.

[adsenseLargeRectangle]

Summary

To help you remember the truth tables for these statements, you can think of the following:

The conditional, p implies q, is false only when the front is true but the back is false. Otherwise it is true.
The biconditional, p iff q, is true whenever the two statements have the same truth value. Otherwise it is false.

Continue reviewing discrete math topics

Previous: Truth tables for “not”, “and”, “or” (negation, conjunction, disjunction)

Next: Analyzing compound propositions with truth tables

Truth tables – negation, conjunction, disjunction (“not”, “and”, “or”)

Truth tables are a way of analyzing how the validity of statements (called propositions) behave when you use a logical “or”, or a logical “and” to combine them. Propositions are either completely true or completely false, so any truth table will want to show both of these possibilities for all the statements made.

For all these examples, we will let p and q be propositions. They could be statements like “I am 25 years old” or “it is currently warmer than 70°”. Any statements that are either true or false.

[adsenseWide]

Negation – “not p”

negation

Negation is the statement “not p”, denoted \(\neg p\), and so it would have the opposite truth value of p. If p is true, then \(\neg p\) if false. If p is false, then \(\neg p\) is true. Notice that the truth table shows all of these possibilities.

Conjunction – “and”

conjunction-and-truth-table

Consider the statement “p and q”, denoted \(p \wedge q\). To analyze this, we first have to think of all the combinations of truth values for both statements and then decide how those combinations influence the “and” statement. In words:

Row 1: the two statements could both be true.
In this case, it would make sense that “p and q” is also a true statement.
Row 2: p could be false while q is true.
For “p and q” to be true, we would need BOTH statements to be true. Since one is false, “p and q” is false.
Row 3: p could be true while q is false.
If this is the case, then by the same argument in row 2, “p and q” is false.
Row 4: the two statements could both be false.
If both statements are false, then “p and q” is false.

The order of the rows doesn’t matter – as long as we are systematic in a way so that we do not miss any possible combinations of truth values for the two original statements p, q.

Disjunction – “or”

disjunction-or-truth-table

You may not realize it, but there are two types of “or”s. There is the inclusive or where we allow for the fact that both statements might be true, and there is the exclusive or, where we are strict that only one statement or the other is true. In math, the “or” that we work with is the inclusive or, denoted \(p \vee q\). When we want to work with the exclusive or, we are specific and use different notation (you can read about this here: the exclusive or). This shows in the first row of the truth table, which we will now analyze:

Row 1: the two statements could both be true.
Since we are working with the inclusive or, the statement “p or q” will be true in this case.
Row 2: p could be false while q is true.
This is the essence of or. We are saying “one or both of the statements is true”. Therefore, “p or q” is true in this case.
Row 3: p could be true while q is false.
Same idea as the second row.
Row 4: the two statements could both be false.
Considering the meaning of or, if both statements are false, then it is not true that “p or q”, thus we list false for this statement.

Summary

To keep track of how these ideas work, you can remember the following:

“not p” always has the opposite truth value of p
“p and q” is true only when both statements are true (false otherwise)
“p or q” is false only when both statements are false (true otherwise)

Understanding these truth tables will allow us to later analyze complex compound compositions consisting of and, or, not, and perhaps even a conditional statement, so make sure you have these basics down!

[adsenseLargeRectangle]

Continue reviewing discrete math topics

Next: Truth tables for the conditional and biconditional (implies, and iff)