Suppose we'd like to estimate \(\pi\). Here's an approximation to more digits than you'd normally need: 3.14159265359.
If we have to compute \(\pi\) ourselves, rather than asking the internet, we might need to use numerical approximations. These might give us an upper bound of 3.1416 and a lower bound of 3.1415. If we're doing a calculation involving \(\pi\), we could use these to figure out how much our approximation might change the final result.
But upper and lower bounds don't have to be so close to the actual number. For example, 3 is a lower bound on \(\pi\). OK, not so bad. But -10 is also a lower bound on \(\pi\). An lower bound on \(\pi\) is any number \(\le \pi\). -10 is just not a very helpful lower bound.
Here's practical example of upper and lower bounds. Suppose that we have rolled out a sheet of cookie dough and would like to cut cookies out of it. Here a 15cm by 20cm sheet of dough and some sample cookies.
Collecting scraps and rolling out the same dough again damages the texture, so we'd like to get as many cookies as possible out of each sheet. So here I've tried to pack in as many cookies as possible:
Looks like I managed to fit in 10 cookies. So 10 is a lower bound on how many cookies can be made out of this sheet of dough.
To get an upper bound, let's look at the areas. The area of each cookie is about 22.3 square cm. The sheet of dough has area 300 square cm. Dividing the two gives us 13.45 cookies. So an upper bound on the number of whole cookies is 13.
Notice that there is a gap between the lower bound of 10 and the upper bound of 13. Since this is an irregular shape, it's not clear how many more cookies I can fit into the sheet.
This problem shows up in a more serious form in the clothing industry. Manufacturers need to cut large pieces of cloth into the pieces that will be sew to make clothing. Scraps of cloth are hard to re-use. So they put significant effort into making the cutting pattern (called a marker) so as to maximize usage of the cloth. Notice that they need to make a lot of markers, because a given garment (e.g. a shirt) would be made in a large range of sizes. Although it's hard to get a provably optimal solution, marker making programs can produce good approximate ones.
In graph coloring, we need to put a color on each node, with the rule that adjacent nodes may not have the same color. Here's a graph and one way to color it with four colors:
And it's actually impossible to color it with three colors, because this graph contains a \(K_4\), i.e. a graph with four nodes and all possible edges. Since all pairs of nodes in \(K_4\) are connected by an edge, none of them can have the same color.
The chromatic number of a graph is the minimum number of colors required to color it. To show that 4 is the chromatic number of the graph above, we had to show two things:
We used different methods to show the two bounds. We proved that 4 was an upper bound on the chromatic number by showing a coloring of the graph with four colors. We proved the lower bound of 4 by finding a \(K_4\) inside our graph.
It's helpful to be familiar with the chromatic numbers of various special graphs. If you find one of them in your large complex graph, that gives you a lower bound on its chromatic number. Also, a special subgraph is often a good place to start when trying to color your full graph.
As we just saw above, a complete graph \(K_n\) requires n colors.
If the graph has any edges at all, it requires at least two colors. (A 1-colorable graph has no edges.)
It's easy to test if a graph is 2-colorable. You can start coloring anywhere, using only two colors, and see if you run into any problems. Notice that 2-colorable means bipartite.
The chromatic number of a cycle \(C_n\) depends on whether the number of nodes is odd or even. Even cycles need two colors; odd cycles need three.
Wheel graphs are similar, except that an extra color is needed for the node in the middle. Notice that \(W_n\) has n+1 nodes.
You can often make a good guess at a graph's chromatic number by looking for the special graphs above. However, to be sure, you need to color the whole graph. For example, the Moser spindle is made entirely out of triangles but has chromatic number 4.
Consider this graph
With a bit of fiddling around, we can find a way to color it with four colors.
This gives us an upper bound on its chromatic number. But is this exact or is there a way to color it with only three colors? As we saw above, the simplest way to make a lower bound argument is by finding a subgraph whose chromatic number we already know. But sometimes it takes a bit of effort to find it. In this case, our graph contains a Moser spindle:
To make this part of the argument precise in a text-based interface, give the name of the special graph you've found and clearly describe its location. E.g. for a wheel graph, list the nodes in the ring and then say which node is the hub. For this Moser spindle, we could quote the sequence of triangles: fgc, gcd, dah, and ahe.
Suppose we didn't know about the Moser spindle or couldn't find it in the previous graph. The fall-back method is to do a step-by-step analysis of all the ways we could try to color it with only three colors and show that none of them can work. This kind of "try it and see" argument is difficult to write in a complete and precise way but it will lead into our next topic.
Suppose we try to color our example graph with three colors. The triangle at the top requires three colors and it doesn't matter how we put them on the three nodes:
If we examine nodes that are adjacent to the part that's already colored, we have only one way to color h, then a, then e.
But then we are stuck, because node b is adjacent to nodes with all three colors.
So we've tried out the hypothesis that 3 colors is enough, and discovered that it didn't work out.
Notice that this partial coloring cannot be completed using only four colors, since b and f are adjacent to one another and also adjacent to nodes with R, G and B. The plan needs to be reworked a bit to finish with only four colors and it's helpful to remember how to color the Moser spindle.
A proof by contradiction uses this sort of argument. We suppose that our claim is false and show that this leads to an impossible situation. The outline is:
Claim: PProof: Suppose not. That is (give the negation of P).
...
X and not X (contradiction)
In a sense, we're creating a fantasy world. We intend to prove P, so obviously we think P is true. But we're assuming it's not. So we're deliberately creating a world that is problematic and we're messing with it until it fails.
Technically, we should end on a literal logical contradiction, "X and not X". However, in practice, it's fine to end with any statement well known to be false (e.g. \(x^2 < 0\)) or a pair of statements well known to be inconsistent (e.g. \(x < 3\) and \(x > 17\)).
This dates back to Euclid, around 3rd century BC.
Background information and assumptions:
Earlier in the term, we proved one direction of the last fact. The other direction is also not hard to prove.
Claim: \(\sqrt{2}\) is not rational.
Proof:
Suppose not. That is, suppose that \(\sqrt{2}\) is rational.Since \(\sqrt{2}\) is rational, we can write it as \(\sqrt{2} = \frac{a}{b}\) where a and b are integers, b is not zero, and a and b do not share any factors.
Squaring both sides of \(\sqrt{2} = \frac{a}{b}\) gives us \(2 = \frac{a^2}{b^2}\).
So \(a^2 = 2b^2\).
So \(a^2\) is even.
Since \(a^2\) is even, a must be even. So \(a = 2p\) where p is an integer.
Substituting this back into our equation gives us \((2p)^2 = 2b^2\).
Simplifying \((2p)^2 = 2b^2\) gives us \(2p^2 = b^2\).
So \(b^2\) is even, which means that b is even.
We've shown that both a and b are even. But we assumed at the start that they did not share any common factors. So we've found a contradiction.
Proof by contradiction can be very useful for proving certain types of claims where other proof methods would be awkward. A typical example is a non-existence claim, e.g. there is no coloring with 3 colors, there is no fraction equivalent to \(\sqrt{2}\). There's a few situations where proof by contradiction is the only option that works.
However, the method of creating and then destroying a fantasy world is frequently less convincing than a "constructive" proof where you incrementally build up a set of facts. There is even a branch of mathematics that has experimented with building most of standard mathematics without proof by contradiction.
Also, contradiction proofs are easy to start but can be hard to finish, because of the vague goal in the outline. It's easy to end up going around in circles.
Claim: Suppose that G is a graph with n nodes. If all the nodes have degree \(\ge \frac{n-1}{2}\), then G is connected.
Main idea: if you put enough edges into a graph, appropriately spread out, eventually there has to be a way to get from any node to any other node.
Notation: if x is a graph node, then N(x) is the set of all "neighbors" of x, i.e. all nodes directly connected to x by an edge. Notice that N(x) does not include x.
Proof:
Suppose that G is a graph with n nodes and all nodes have degree \(\ge \frac{n-1}{2}\). Let v and w be nodes in G. We need to show that there is a walk from v to w.Suppose not. That is, suppose that there is no walk from v to w.
First section: establish relationship between key sets.
Since there is no walk from v to w, v and w can't be equal.
v and w also can't be neighbors. So N(v) can't contain w, and it was defined not to contain v. Similarly, N(w) can't contain either v or w.
Also, N(v) and N(w) can't intersect. Suppose there was a point p in both sets. Then we would have a path from v to w via p, which we know not to be possible.
The dotted lines are a reminder that v is not in N(v) and w is not in N(w).
Summarize:
- v and w aren't equal.
- N(v) does not contain v or w.
- N(w) does not contain v or w.
- N(v) and N(w) do not intersect.
So the sets N(v), N(w), and {v,w} are all disjoint.
Second section: calculate total size of three key sets
So \( |N(v) \cup N(w) \cup \{v,w\}| = |N(v)| + |N(w)| + |\{v,w\}| \).Since every node has degree \(\ge \frac{n-1}{2}\), N(v) contains at least \(\frac{n-1}{2}\) nodes, and N(w) contains at least \(\frac{n-1}{2}\) nodes.
So we have \( |N(v) \cup N(w) \cup \{v,w\}| = |N(v)| + |N(w)| + |\{v,w\}| \ge \frac{n-1}{2} + \frac{n-1}{2} + 2 = (n-1) + 2 = n+1 \)
So \( |N(v) \cup N(w) \cup \{v,w\}| \ge n+1 \)
But G contains only n nodes. So we have a contradiction.
Recap for reader
We assumed that there was no walk from v to w, and that led to a contradiction. So there must be a walk from v to w.
Since v and w were arbitrarily chosen, this means there is a walk between any two nodes in G. So G is connected.