Puzzle10
On the table rest 8 dominoes, as shown below. If you were to line them up in a single row, so that any two sides touching had matching numbers, what would the sum of the two end numbers be?
Section1.2Walking Around Graphs
Ā¶How might you use graph theory to solve the puzzle above? One thing to try would be to create a graph consisting of six vertices, one for each value that appears on the dominoes. Then connect the vertices if their numbers belong to the same domino. This seems reasonable, but then how would you represent the line of matched up dominoes the puzzle requests?
Say you start with domino \((4,6)\text{.}\) That is an edge in our graph. Next we need to place a domino with a 6 on it (or a 4, but let's say the 4 will be an endpoint). This amounts to selecting another edge, one that is incident to the vertex 6. Say we pick \((6,5)\text{.}\) The edge we must select after that will need to be incident to vertex 5. And so on.
The edges we select in the graph need to be linked up. It makes sense to think about the selection of edges as traveling through the graph, moving along edges from vertex to vertex. Let's capture this notion carefully.
Definition1.2.1
A walk in a graph \(G = (V,E)\) is a sequence of vertices \(v_0, v_1, v_2, \ldots, v_n\) such that \(\{v_i, v_{i+1}\} \in E\) for all \(0 \le i \lt n\text{.}\) That is, consecutive vertices in the sequence are adjacent in the graph.
A trail is a walk that does not repeat any edges. If the trail starts and ends at the same vertex (i.e., \(v_1 = v_n\)) then it is called a circuit
A path is a trail that does not repeat any vertices, except perhaps for \(v_0 = v_n\text{.}\) In the case that \(v_0 = v_n\text{,}\) the path is called a cycle.
Do these definitions capture what a walk/trail/path should mean in a graph? All three of these describe ways in which to move around in the graph, perhaps tracing along the edges without lifting up your pencil.
Note: some sources give slightly different definitions for these concepts. For example, sometimes a walk is defined as a alternating sequence of vertices and edges \(v_1e_1v_2e_2v_3\cdots e_{n-1}v_n\) with the requirement that \(v_i\) is incident to \(e_i\text{,}\) which is incident to \(v_{i+1}\text{.}\) We have not named our edges, so this definition would not make sense. Another common way to define path is as a subgraph isomorphic to \(P_n\) for some \(n\text{.}\) This is almost equivalent to our definition, except that we allow our paths to possibly be isomorphic to \(C_n\) for some \(n\) as well. Some sources use path where we use walk and use simple path where we use path.
Walks and paths are useful for considering all sorts of graph theoretic concepts. For example, you might want to find the distance between two vertices. This would be defined as the shortest path starting at one and ending at the other (where the length of a path is the number of edges in it). If you have a notion of distance, you can define the center and radius of a graph. Graphs are connected provided between any two vertices, there is a path (or equivalently, a walk).
Subsection1.2.1Euler paths and circuits
Ā¶To solve the domino problem, as well as the Bridges of Kƶnigsberg, we need to consider walks that use every edge exactly once.
Definition1.2.2
A walk in a graph that uses every edge exactly once is called an Euler path. An Euler path that starts and ends at the same vertex is called an Euler circuit.
Although it is tradition, Euler path is a bad name. These should be called an Euler trail or Euler walk, since by our definitions, an Euler path is usually not a path at all. An Euler circuit is also sometimes called an Euler tour.
Activity11
Our goal is to find a quick way to check whether a graph (or multigraph) has an Euler path or circuit.
(a)
Which of the graphs/multigraphs below have Euler paths? Which have Euler circuits?
(b)
List the degrees of each vertex of the (multi)graphs above. Is there a connection between degrees and the existence of Euler paths and circuits?
(c)
Is it possible for a graph with a degree 1 vertex to have an Euler circuit? If so, draw one. If not, explain why not. What about an Euler path?
(d)
What if every vertex of the graph has degree 2. Is there an Euler path? An Euler circuit? Draw some graphs.
(e)
Below is part of a graph. Even though you can only see some of the vertices, can you deduce whether the graph will have an Euler path or circuit?
So what does it take for a graph to have an Euler path or circuit? Of course if a graph is not connected, there is no hope of finding such a path or circuit. For the rest of this section, assume all the graphs discussed are connected.
The bridges of Kƶnigsberg problem is really a question about the existence of Euler paths. There will be a route that crosses every bridge exactly once if and only if the multigraph below has an Euler path:
This graph is small enough that we could actually check every possible walk that does not reuse edges, and in doing so convince ourselves that there is no Euler path (let alone an Euler circuit). On small graphs which do have an Euler path, it is usually not difficult to find one. Our goal is to find a quick way to check whether a graph has an Euler path or circuit, even if the graph is quite large.
One way to guarantee that a graph does not have an Euler circuit is to include a āspike,ā a vertex of degree 1.
The vertex \(a\) has degree 1, and if you try to make an Euler circuit, you see that you will get stuck at the vertex. It is a dead end. That is, unless you start there. But then there is no way to return, so there is no hope of finding an Euler circuit. There is however an Euler path. It starts at the vertex \(a\text{,}\) then loops around the triangle. You will end at the vertex of degree 3.
You run into a similar problem whenever you have a vertex of any odd degree. If you start at such a vertex, you will not be able to end there (after traversing every edge exactly once). After using one edge to leave the starting vertex, you will be left with an even number of edges emanating from the vertex. Half of these could be used for returning to the vertex, the other half for leaving. So you return, then leave. Return, then leave. The only way to use up all the edges is to use the last one by leaving the vertex. On the other hand, if you have a vertex with odd degree that you do not start a path at, then you will eventually get stuck at that vertex. The path will use pairs of edges incident to the vertex to arrive and leave again. Eventually all but one of these edges will be used up, leaving only an edge to arrive by, and none to leave again.
What all this says is that if a graph has an Euler path and two vertices with odd degree, then the Euler path must start at one of the odd degree vertices and end at the other. In such a situation, every other vertex must have an even degree since we need an equal number of edges to get to those vertices as to leave them. How could we have an Euler circuit? The graph could not have any odd degree vertex as an Euler path would have to start there or end there, but not both. Thus for a graph to have an Euler circuit, all vertices must have even degree.
So there is clearly a connection between the parity of vertex degrees and Euler paths and circuits. Here are two theorems the describe that connection.
Theorem1.2.3
A connected graph has an Euler circuit if and only if the degree of every vertex is even.
Theorem1.2.4
A connected graph has an Euler path if and only if there are at most two vertices with odd degree.
We will need to prove these theorems, and doing so will give us an excuse to think about proving theorems in general. However, note that these theorems answer the bridges of Kƶnigsberg problem. The graph has all four vertices with odd degree, there is no Euler path through the graph. Thus there is no way for the townspeople to cross every bridge exactly once.
Subsection1.2.2Interlude: Implications and Proofs
Ā¶We would like to prove the theorems we conjectured above about Euler paths and circuits. To help us understand how we could do this, and to make sure our proof is correct, we should take a few moments to recall some basic facts about mathematical statements, their logical form, and how this can help us in writing proofs. A more detailed discussion of these topics is found in SectionsĀ B.4 and SectionĀ B.5.
All mathematical statements have a logical form that determines the meaning of the statement and often suggests a method for proving (or disproving) the statement. At the most basic level, a statement might be atomic, if it is not composed of simpler statements, or otherwise molecular. A molecular statement is built up of smaller statements by connecting them with a logical connective. Such statements might be a conjunction (two statements connected by an āandā) a disjunction (two statements connected by an āorā), an implication or conditional (usually in the form āif ā¦ then ā¦ā), or a negation (claiming a statement is not true).
There are other logical connectives, used both in mathematical statements and in ordinary language, but every one can be reduced to these four (actually, you can get away with as few as two of them). For example, it is very common in mathematics to encounter statements of the form ā\(P\) if and only if \(Q\text{.}\)ā This is called a biconditional, but it is nothing more than the conjunction of two implications. That is, ā\(P\) if and only if \(Q\)ā means āif \(P\) then \(Q\text{,}\) and if \(Q\) then \(P\text{.}\)ā
The truth of falsity of a molecular statement is determined entirely by the truth or falsity of its parts, governed by set rules of the connectives. These rules can be communicated through truth tables. We use the standard symbols \(\wedge\) for āandā, \(\vee\) for āorā, \(\imp\) for implications and \(\neg\) for negations.
| \(P\) | \(Q\) | \(P\wedge Q\) |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
| \(P\) | \(Q\) | \(P\vee Q\) |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
| \(P\) | \(Q\) | \(P\imp Q\) |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
| \(P\) | \(\neg P\) |
| T | F |
| F | T |
Note that the truth table for \(P \vee Q\) shows us that we always mean the inclusive or, in that when both \(P\) and \(Q\) are true, we say that \(P \vee Q\) is true.
The other truth table worth looking closely at is the one for implications. This might strike you as strange at first. If \(P\) is false, the implication \(P \imp Q\) is true (no matter the truth value of \(Q\)). Also, there is no need for \(P\) to ācauseā \(Q\) to be true. For example, the statement āIf 2 is even, then 2 is primeā is true, despite there being no connection between the concepts of āevenā and āprimeā.
Activity12
Decide which of the statements below are true and which are false.
(a)
If 8 is prime, then the 7624th digit of \(\pi\) is an 8.
(b)
If the 7624th digit of \(\pi\) is an 8, then \(5\) is prime.
(c)
If 5 is prime, then most horses have 4 legs.
(d)
If 5 is prime, then 8 is prime.
Examining the truth table for \(P \imp Q\) further, we notice that it is possible for \(P \imp Q\) to be true but \(Q \imp P\) to be false. (What would the truth values of \(P\) and \(Q\) need to be to make this the case?) We call \(Q \imp P\) the converse of \(P \imp Q\text{.}\)
Activity13
Give three examples of implications which are true whose converse is false. Then give three examples of implications which are true whose converse is true.
Hint
You might think about the relationship between a function being continuous and being differentiable. Or a shape being a square or a rectangle.
The claim \(P\) if and only if \(Q\) is the claim that both an implication and its converse are true. This is the form that TheoremsĀ 1.2.3 and TheoremĀ 1.2.4 about Euler circuits and paths take. Looking at the form, we see what it would take to prove them.
To prove a biconditional, you simply must prove both implications (the implication and its converse). How do you prove an implication though? Well, by looking at the truth table, we see that we must prove that we are always in rows 1, 3, or 4. The only case we need to exclude is the one where \(P\) is true and \(Q\) is false.
So assume \(P\) is true (the other case is automatic). Under this assumption, we argue that \(Q\) is true as well.
Alternatively, we could start by assuming \(Q\) is false. If we can then conclude that \(P\) is also false, we have excluded the one suspect case, as we can conclude that \(P \imp Q\text{.}\) You could also conclude that \(\neg Q \imp \neg P\text{,}\) which is the contrapositive of \(P \imp Q\text{.}\) By comparing truth tables, it is easy to see that any implication is equivalent to its contrapositive, so proving a contrapositive is equivalent to proving its implication.
There is one important piece we should mention here: the use of quantifiers.
Activity14
Is it possible for both a statement and its converse to be false? What could you say about \(P\) and \(Q\) for such a statement?
What about the statement, āif \(p\) is prime, then \(p\) is oddā. This statement is false. So is its converse. But the truth tables for \(P \imp Q\) and \(Q \imp P\) do not have a false in the same row. So what is going on?
The key is that we are secretly adding a universal quantifier in front of statements like this. What we really mean is that for all \(p\), if \(p\) is prime, then \(p\) is odd. This is false, because there exists (the existential quantifier) some counterexample. The converse of the statement is, for all \(p\text{,}\) if \(p\) is odd, then \(p\) is prime. This is also false, because there exists a counterexample. Necessarily, it will be a different counterexample than the one that proved the implication was false.
How do you prove a universally quantified statement is true? You must prove the implication is true for all cases. To prove that for all \(n\text{,}\) if \(n^2\) is even, then so is \(n\text{,}\) you must prove this for \(n = 1\text{,}\) \(n = 2\text{,}\) \(n =3\text{,}\) etc. But to get on with your life, you might as well prove it for all of them at once. Let \(n\) be an arbitrary integer. Now prove the statement for that arbitrary \(n\text{.}\) In this case, you might want to assume \(n\) is NOT even and prove that \(n^2\) is not even, to give a proof by contrapositive. But since \(n\) was arbitrary, you have shown that your poof would work for any value of \(n\text{.}\)
Subsection1.2.3Proofs for Euler Paths and Circuits
Ā¶Now let's try to prove TheoremsĀ 1.2.3 and TheoremĀ 1.2.4. Actually, we really only need to prove one of these, and the other one should follow from it.
Activity15
Suppose we have already proved TheoremĀ 1.2.3, that a graph has an Euler circuit if and only if every vertex has even degree. Suppose now we want to prove TheoremĀ 1.2.4, that a graph has an Euler path if and only if it has at most two odd degree vertices.
(a)
Given a graph with an Euler path, how can you get a graph that definitely has an Euler circuit? How did this affect the number of odd degree vertices?
Hint
Add something to your graph so you can āfinishā the Euler path. Don't forget to consider the case that the start and end vertex are already adjacent.
(b)
Given a graph with at most two odd degree vertices, build a graph that has only even degree vertices. If you have an Euler circuit of your new graph, what would that Euler circuit become if you looked at your original graph?
Hint
If there are no odd degree vertices, you are done. If there are two, you could connect them with an edge, except maybe they are already adjacent. What could you do then?
(c)
What do each of the above tasks demonstrate? That is, write a proof of TheoremĀ 1.2.4 assuming TheoremĀ 1.2.3. Make sure you specify how each ādirectionā (implication and converse) of the proof is established by the tasks above.
Good, so we only need to prove TheoremĀ 1.2.3.
Activity16
Which of the two implications will be easier to prove? State both implications and say specifically what it would take to prove each. Say what would be required both for doing a direct proof and a proof by contrapositive.
Activity17
Suppose you had a graph and were given an Euler circuit for that graph. How might you represent that Euler circuit? If you listed each edge in order, where each edge was given as a pair of vertices, how many times would each vertex appear in the list? What have you just shown?
The other direction is harder. If you know every vertex has even degree, you must now show there is an Euler circuit. One thing you could do is to give a procedure for building one. But then you must prove that this procedure is correct. We will come back to this question when we look at mathematical induction.
Subsection1.2.4Hamilton Paths
Ā¶Suppose you wanted to tour Kƶnigsberg in such a way where you visit each land mass (the two islands and both banks) exactly once. This can be done. In graph theory terms, we are asking whether there is a path which visits every vertex exactly once. Such a path is called a Hamilton path (or Hamiltonian path). We could also consider Hamilton cycles, which are Hamilton paths which start and stop at the same vertex.
Example1.2.5
Determine whether the graphs below have a Hamilton path.
Solution
The graph on the left has a Hamilton path (many different ones, actually), as shown here:
The graph on the right does not have a Hamilton path. You would need to visit each of the āoutsideā vertices, but as soon as you visit one, you get stuck. Note that this graph does not have an Euler path, although there are graphs with Euler paths but no Hamilton paths.
It appears that finding Hamilton paths would be easier because graphs often have more edges than vertices, so there are fewer requirements to be met. However, nobody knows whether this is true. There is no known simple test for whether a graph has a Hamilton path. For small graphs this is not a problem, but as the size of the graph grows, it gets harder and harder to check whether there is a Hamilton path. In fact, this is an example of a question which as far as we know is too difficult for computers to solve; it is an example of a problem which is NP-complete.
While a complete classification for which graphs have Hamilton paths is hard, there are some simpler things we can say. The following is one example.
Activity18
Consider the following graph:
(a)
Find a Hamilton path. Can your path be extended to a Hamilton cycle?
(b)
Is the graph bipartite? If so, how many vertices are in each āpartā?
(c)
Use your answer to part (b) to prove that the graph has no Hamilton cycle.
(d)
Suppose you have a bipartite graph \(G\) in which one part has at least two more vertices than the other. Prove that \(G\) does not have a Hamilton path.