##### Exercise 7.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\}\)

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?

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?

(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

In an undirected graph, the number of vertices having an odd degree is even.

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.

In an undirected graph the sum of the degrees of the vertices is even.

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:

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

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

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\).

A magic square of order \(n\) has a magic sum equal to \(\displaystyle\frac{n^3+n}{2}\).

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}\fiComplete the proof of the fact that “Every graph has an even number of odd nodes.”

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

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.

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.

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

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

Construct magic squares of order 4 and 5.

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

Is there a magic hexagon of order 3?