# Section7.2Parity and Counting arguments

This section is concerned with two very powerful elements of the proof-making arsenal: “Parity” is a way of referring to the result of an even/odd calculation; Counting arguments most often take the form of counting some collection in two different ways — and then comparing those results. These techniques have little to do with one another, but when they are applicable they tend to produce really elegant little arguments.

In (very) early computers and business machines, paper cards were used to store information. A so-called “punch card” or “Hollerith card” was used to store binary information by means of holes punched into it. Paper tape was also used in a similar fashion. A typical paper tape format would involve 8 positions in rows across the tape that might or might not be punched, often a column of smaller holes would appear as well which did not store information but were used to drive the tape through the reading mechanism on a sprocket. Tapes and cards could be “read” either by small sets of electrical contacts which would touch through a punched hole or be kept separate if the position wasn't punched, or by using a photo-detector to sense whether light could pass through the hole or not. The mechanisms for reading and writing on these paper media were amazingly accurate, and allowed early data processing machines to use just a couple of large file cabinets to store what now fits in a jump drive one can wear on a necklace. (About 10 or 12 cabinets could hold a gigabyte of data).

Paper media was ideally suited to storing binary information, but of course most of the real data people needed to store and process would be alphanumeric 1 . There were several encoding schemes that served to translate between the character sets that people commonly used and the binary numerals that could be stored on paper. One of these schemes still survives today — ASCII. The American Standard Code for Information Interchange uses 7-bit binary numerals to represent characters, so it contains 128 different symbols. This is more than enough to represent both upper- and lower-case letters, the 10 numerals, and the punctuation marks — many of the remaining spots in the ASCII code were used to contain so-called “control characters” that were associated with functionality that appeared on old-fashioned teletype equipment — things like “ring the bell,” “move the carriage backwards one space,” “move the carriage to the next line,” etc. These control characters are why modern keyboards still have a modifier key labeled “Ctrl” on them. The following listing gives the decimal and binary numerals from 0 to 127 and the ASCII characters associated with them — the non-printing and control characters have a 2 or 3 letter mnemonic designation.

Now it only takes 7 bits to encode the 128 possible values in the ASCII system, which can easily be verified by noticing that the left-most bits in all of the binary representations above are 0. Most computers use 8 bit words or “bytes” as their basic units of information, and the fact that the ASCII code only requires 7 bits lead someone to think up a use for that additional bit. It became a “parity check bit.” If the seven bits of an ASCII encoding have an odd number of 1's, the parity check bit is set to 1 — otherwise, it is set to 0. The result of this is that, subsequently, all of the 8 bit words that encode ASCII data will have an even number of 1's. This is an example of a so-called error detecting code known as the “even code” or the “parity check code.” If data is sent over a noisy telecommunications channel, or is stored in fallible computer memory, there is some small but calculable probability that there will be a “bit error.” For instance, one computer might send 10000111 (which is the ASCII code that says “ring the bell”) but another machine across the network might receive 10100111 (the 3rd bit from the left has been received in error) now if we are only looking at the rightmost seven bits we will think that the ASCII code for a single quote has been received, but if we note that this piece of received data has an odd number of ones we'll realize that something is amiss. There are other more advanced coding schemes that will let us not only detect an error, but (within limits) correct it as well! This rather amazing feat is what makes wireless telephony (not to mention communications with deep space probes — whoops! I mentioned it) work.

The concept of parity can be used in many settings to prove some fairly remarkable results.

In Section 6.3 we introduced the idea of a graph. This notion was first used by Leonhard Euler to solve a recreational math problem posed by the citizens of Königsberg, Prussia (this is the city now known as Kaliningrad, Russia.) Königsberg was situated at a place where two branches of the Pregel river 2  come together — there is also a large island situated near this confluence. By Euler's time, the city of Königsberg covered this island as well as the north and south banks of the river and also the promontory where the branches came together. A network of seven bridges had been constructed to connect all these land masses. The townsfolk are alleged to have become enthralled by the question of whether it was possible to leave one's home and take a walk through town which crossed each of the bridges exactly once and, finally, return to one's home.

Euler settled the question (it can't be done) be converting the map of Königsberg into a graph and then making some simple observations about the parities of the nodes in this graph. The degree of a node in a graph is the number of edges that are incident with it (if a so-called “loop edge” is present it adds two to the node's degree). The “parity of a node” is shorthand for the “parity of the degree of the node.”

The graph of Königsberg has 4 nodes: one of degree 5 and three of degree 3. All the nodes are odd. Would it be possible to either modify Königsberg or come up with an entirely new graph having some even nodes? Well, the answer to that is easy — just tear down one of the bridges, and two of the nodes will have their degree changed by one; they'll both become even. Notice that, by removing one edge, we effected the parity of two nodes. Is it possible to create a graph with four nodes in which just one of them is even? More generally, given any short list of natural numbers, is it possible to draw a graph whose degrees are the listed numbers?

##### Exercise7.2.1

Try drawing graphs having the following lists of vertex degrees. (In some cases it will be impossible…)

• $\{1,1,2,3,3\}$

• $\{1,2,3,5\}$

• $\{1,2,3,4\}$

• $\{4,4,4,4,5\}$

• $\{3,3,3,3\}$

• $\{3,3,3,3,3\}$

When it is possible to create a graph with a specified list of vertex degrees, it is usually easy to do. Of course, when it's impossible you struggle a bit… To help get things rolling (just in case you haven't really done the exercise) I'll give a hint — for the first list it is possible to draw a graph, for the second it is not. Can you distinguish the pattern? What makes one list of vertex degrees reasonable and another not?

##### Exercise7.2.2

(If you didn't do the last exercise, stop being such a lame-o and try it now. BTW, if you did do it, good for you! You can either join with me now in sneering at all those people who are scurrying back to do the last one, or try the following:)

Figure out a way to distinguish a sequence of numbers that can be the degree sequence of some graph from the sequences that cannot be.

Okay, now if you're reading this sentence you should know that every other list of vertex degrees above is impossible, you should have graphs drawn in the margin here for the 1st, 3rd and 5th degree sequences, and you may have discovered some version of the following

A slightly pithier statement is: All graphs have an even number of odd nodes.

We'll leave the proof of this theorem to the exercises but most of the work is done in proving the following equivalent result.

##### Proof

The question of whether a graph having a given list of vertex degrees can exist comes down to an elegant little argument using both of the techniques in the title of this section. We count the edge set of the graph in two ways — once in the usual fashion and once by summing the vertex degrees; we also note that since this latter count is actually a double count we can bring in the concept of parity.

Another perfectly lovely argument involving parity arises in questions concerning whether or not it is possible to tile a pruned chessboard with dominoes. We've seen dominoes before in Section 5.1 and we're just hoping you've run across chessboards before. Usually a chessboard is 8 × 8, but we would like to adopt a more liberal interpretation that a chessboard can be any rectangular grid of squares we might choose. 3  Suppose that we have a supply of dominoes that are of just the right size that if they are laid on a chessboard they perfectly cover two adjacent squares. Our first question is quite simple. Is it possible to perfectly tile an $m \times n$ chessboard with such dominoes?

First let's specify the question a bit more. By “perfectly tiling” a chessboard we mean that every domino lies (fully) on the board, covering precisely two squares, and that every square of the board is covered by a domino.

The answer is straightforward. If at least one of $m$ or $n$ is even it can be done. A necessary condition is that the number of squares be even (since every domino covers two squares) and so, if both $m$ and $n$ are odd we will be out of luck.

A “pruned board” is obtained by either literally removing some of the squares or perhaps by marking them as being off limits in some way. When we ask questions about perfect tilings of pruned chessboards things get more interesting and the notion of parity can be used in several ways.

Here are two tiling problems regarding square chessboards:

1. An even-sided square board (e.g. an ordinary $8 \times 8$ board) with diagonally opposite corners pruned.

2. An odd-sided board with one square pruned.

Both of these situations satisfy the basic necessary condition that the number of squares on the board must be even. You may be able to determine another “parity” approach to these tiling problems by attempting the following

##### Exercise7.2.5

Below are two five-by-five chessboards each having a single square pruned. One can be tiled by dominoes and the other cannot. Which is which?

\ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi

The pattern of black and white squares on a chessboard is an example of a sort of artificial parity, if we number the squares of the board appropriately then the odd squares will be white and the even squares will be black. We are used to chessboards having this alternating black/white pattern on them, but nothing about these tiling problems required that structure 4  If we were used to monochromatic chessboards, we might never solve the previous two problems — unless of course we invented the coloring scheme in order to solve them. An odd-by-odd chessboard has more squares of one color than of the other. An odd-by-odd chessboard needs to have a square pruned in order for it to be possible for it to be tiled by dominoes — but if the wrong colored square is pruned it will still be impossible. Each domino covers two squares — one of each color! (So the pruned board must have the same number of white squares as black.)

We'll close this section with another example of the technique of counting in two ways.

A magic square of order $n$ is a square $n \times n$ array containing the numbers $1, 2, 3, \ldots , n^2$. The numbers must be arranged in such a way that every row and every column sum to the same number — this value is known as the magic sum.

For example, the following is an order $3$ magic square.

 1 6 8 5 7 3 9 2 4

The definition of a magic square requires that the rows and columns sum to the same number but says nothing about what that number must be. It is conceivable that we could produce magic squares (of the same order) having different magic sums. This is conceivable, but in fact the magic sum is determined completely by $n$.

# Subsection7.2.1Exercises

1. A walking tour of Königsberg such as is described in this section, or more generally, a circuit through an arbitrary graph that crosses each edge precisely once and begins and ends at the same node is known as an Eulerian circuit. An Eulerian path also crosses every edge of a graph exactly once but it begins and ends at distinct nodes. For each of the following graphs determine whether an Eulerian circuit or path is possible, and if so, draw it. \ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi \ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi

2. Complete the proof of the fact that “Every graph has an even number of odd nodes.”

3. Provide an argument as to why an $8 \times 8$ chessboard with two squares pruned from diagonally opposite corners cannot be tiled with dominoes.

4. Prove that, if $n$ is odd, any $n \times n$ chessboard with a square the same color as one of its corners pruned can be tiled by dominoes.

5. The five tetrominoes (familiar to players of the video game Tetris) are relatives of dominoes made up of four small squares. \ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi All together these five tetrominoes contain 20 squares so it is conceivable that they could be used to tile a $4 \times 5$ chessboard. Prove that this is actually impossible.

6. State necessary and sufficient conditions for the existence of an Eulerian circuit in a graph.

7. State necessary and sufficient conditions for the existence of an Eulerian path in a graph.

8. Construct magic squares of order 4 and 5.

9. A magic hexagon of order 2 would consist of filling-in the numbers from 1 to 7 in the hexagonal array below. The magic condition means that each of the 9 “lines” of adjacent hexagons would have the same sum. Is this possible? \ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi

10. Is there a magic hexagon of order 3?