An Introduction to Combinatorics and Graph Theory

1 An Introduction toCombinatorics and GraphTheoryDavid GuichardThis work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License. Toview a copy of this license, send a letter toCreative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA. If you distributethis work or a derivative, include the history of the copy of the text was compiled from source at 14:52 on 1/30 will be glad to receive corrections and suggestions for improvement .. and permutations .. coefficients .. numbers .. with repetition .. Pigeonhole Principle.

2 's Theorem .. numbers .. Inclusion-Exclusion Formula .. Position Permutations ..4634 Contents3 Generating 's Binomial Theorem .. Generating Functions .. of Integers .. Relations .. Numbers ..644 Systems of Distinct of SDRs .. SDRs .. Squares .. to Graph Theory ..825 Graph Basics .. Circuits and Walks .. Cycles and Paths .. Graphs .. Spanning Trees .. Coloring .. Chromatic Polynomial .. Planar Graphs .. Graphs ..127 Contents56P olya{Red eld of Symmetries .. 's Theorem .. olya-Red eld Counting ..144 AHints149 Index1511 FundamentalsCombinatorics is often described brie y as being about counting, and indeed counting isa large part of Combinatorics .}

3 As the name suggests, however, it is broader than this: itis about combining things. Questions that arise include counting problems: \How manyways can these elements be combined?" But there are other questions, such as whether acertain combination is possible, or what combination is the \best" in some sense. We willsee all of these, though counting plays a particularly large Theory is concerned with various types of networks, or really models of networkscalled graphs. These are not the graphs of analytic geometry, but what are often describedas \points connected by lines", for example.

4 The preferred terminology isvertexfor a point andedgefor a line. The lines need notbe straight lines, and in fact the actual de nition of a Graph is not a geometric de gure above is simply a visualization of a Graph ; the Graph is a more abstract object,consisting of seven vertices, which we might namefv1; : : : ; v7g, and the collection of pairsof vertices that are connected; for a suitable assignment of namesvito the points inthe diagram, the edges could be represented asfv1; v2g,fv2; v3g,fv3; v4g,fv3; v5g,fv4; v5g,fv5; v6g,fv6; 1 we have a chess board, and a collection of tiles, like dominoes, each of which is thesize of two squares on the chess board.

5 Can the chess board be covered by the dominoes?First we need to be clear on the rules: the board is covered if the dominoes are laid down sothat each covers exactly two squares of the board; no dominoes overlap; and every squareis covered. The answer is easy: simply by laying out 32 dominoes in rows, the board canbe covered. To make the problem more interesting, we allow the board to be rectangularof any size, and we allow some squares to be removed from the board. What can be sayabout whether the remaining board can be covered? This is such a board, for example:.What can we say?

6 Here is an easy observation: each domino must cover two squares, sothe total number of squares must be even; the board above has an even number of that enough? It is not too hard to convince yourself that this board cannot be covered;is there some general principle at work? Suppose we redraw the board to emphasize thatit really is part of a chess board:.Aha! Every tile must cover one white and one gray square, but there are four of theformer and six of the latter, so it is impossible. Now do we have the whole picture? No; Examples9for example:.The gray square at the upper right clearly cannot be covered.

7 Unfortunately it is not easyto state a condition that fully characterizes the boards that can be covered; we will seethis problem again. Let us note, however, that this problem can also be represented asa Graph problem. We introduce a vertex corresponding to each square, and connect twovertices by an edge if their associated squares can be covered by a single domino; here isthe previous board:.. Here the top row of vertices represents the gray squares, the bottom row the white domino now corresponds to an edge; a covering by dominoes corresponds to a collectionof edges that share no endpoints and that areincidentwith (that is, touch) all six no edge is incident with the top left vertex, there is no the most famous problem in Graph Theory concerns map coloring: Given amap of some countries, how many colors are required to color the map so that countriessharing a border get different colors?

8 It was long conjectured that any map could becolored with four colors, and this was nally proved in 1976. Here is an example of a smallmap, colored with four colors:.Typically this problem is turned into a Graph Theory problem. Suppose we add to eachcountry a capital, and connect capitals across common boundaries. Coloring the capitals so10 Chapter 1 Fundamentalsthat no two connected capitals share a color is clearly the same problem. For the previousmap:.. Any Graph produced in this way will have an important property: it can be drawn so thatno edges cross each other; this is aplanargraph.

9 Non-planar graphs can require morethan four colors, for example this Graph :.. This is called thecomplete graphon ve vertices, denotedK5; in a complete Graph ,each vertex is connected to each of the others. Here only the \fat" dots represent vertices;intersections of edges at other points are not vertices. A few minutes spent trying shouldconvince you that this Graph cannot be drawn so that its edges don't cross, though thenumber of edge crossings can be why anm nboard can be covered if eithermornis even. Explain why it cannotbe covered if bothmandnare two diagonally opposite corners of an ordinary 8 8 board are removed.

10 Can theresulting board be covered? thatmandnare both odd. On anm nboard, colored as usual, all four cornerswill be the same color, say white. Suppose one white square is removed from any locationon the board. Show that the resulting board can be that one corner of an 8 8 board is removed. Can the remainder be covered by1 3 tiles? Show a tiling or prove that it cannot be Combinations and the square in row 3, column 3 of an 8 8 board is removed. Can the remainder becovered by 1 3 tiles? Show a tiling or prove that it cannot be two diagonally opposite corners of anm nboard, wheremis odd andnis that the remainder can be covered with one white and one black square are removed from ann nboard,neven.