\(\newcommand{\newpara}{}
\newcommand{\nats}{\mathbb{N}}
\newcommand{\subcountawry}{\bf{When\ Counting\ Goes\ Awry}}
\newcommand{\seccountingstepscases}{\bf{Counting\ with\ Steps\ and\ Cases}}
\newcommand{\subalgfac}{\bf{Algebra:\ Factorials}}
\newcommand{\seccountingsubsets}{\bf{Counting\ Subsets}}
\newcommand{\secbitstrings}{\bf{Counting\ Bit\ Strings}}
\newcommand{\subhs}{Counting Handshakes}
\newcommand{\circled}[1]{\tikz[baseline=(char.base)]{\node[shape=circle,draw,inner sep=2pt] (char) {#1};}}
\newcommand{\xcircle}[1]{\circled{#1}}
\newcommand{\subdiscrete}{What is Discrete Mathematics?}
\newcommand{\sublearning}{Learning Discrete Mathematics}
\newcommand{\exerR}{Recap}
\newcommand{\subcountingawry}{When Counting Goes Awry}
\newcommand{\exerP}{Practice}
\newcommand{\subfactorials}{Algebra: Factorials}
\newcommand{\exerU}{Understand}
\newcommand{\subsubsetschoose}{Subsets and the Binomial Coefficients}
\newcommand{\exerE}{Explore}
\newcommand{\subcombinecount}{Combining Counting Techniques}
\newcommand{\subproofscountnosums}{Proof Format: Combinatorial Proof}
\newcommand{\subbitstrings}{Bit Strings}
\newcommand{\subcountbitstrings}{Number of Bit Strings}
\newcommand{\subrephrasingsubset}{Detour: Rephrasing the Question}
\newcommand{\subexplog}{Algebra: Exponential Notation and Logarithms}
\newcommand{\subbridges}{Crossing Bridges}
\newcommand{\subdefngraph}{The Definition of a Graph}
\newcommand{\subgraphcomp}{Graph Complements}
\newcommand{\subdegseq}{Degree Sequences}
\newcommand{\substdgraphs}{Standard Graphs}
\newcommand{\subadjmat}{The Adjacency Matrix of a Graph}
\newcommand{\subcolormaps}{Coloring Maps}
\newcommand{\subchromatic}{Coloring Graphs}
\newcommand{\subgraphconj}{Graph Conjectures}
\newcommand{\subplanarity}{Planarity}
\newcommand{\subisograph}{Isomorphic Graphs}
\newcommand{\subgraphtrees}{Subgraphs and Trees}
\newcommand{\subnonisograph}{Nonisomorphic Graphs}
\newcommand{\subgraphclassification}{Graph Classification}
\newcommand{\subrobots}{Detour: Robots}
\newcommand{\sublockers}{Opening and Closing Lockers}
\newcommand{\subevenodd}{Even and Odd Integers}
\newcommand{\subdivides}{Divisibility}
\newcommand{\subfractions}{Algebra: Equivalent Fractions}
\newcommand{\subdivalg}{The Division Algorithm, \fn{div}, and \fn{mod}}
\newcommand{\subpolys}{Algebra: Polynomials}
\newcommand{\subpffcases}{Proof Format: Proof by Cases}
\newcommand{\subnotlast}{Not Last Game}
\newcommand{\submod}{The Mod Clock}
\newcommand{\subzn}{The Integers mod $n$}
\newcommand{\subprimes}{Primes and Composites}
\newcommand{\subprimefact}{Prime Factorization}
\newcommand{\subcountdiv}{Detour: Listing and Counting Divisors}
\newcommand{\subgcd}{Greatest Common Divisor}
\newcommand{\subea}{The Euclidean Algorithm}
\newcommand{\subcoprime}{Coprime Integers}
\newcommand{\subandor}{And and Or}
\newcommand{\subpffandor}{Proof Formats: $\land$ and $\lor$ by Cases}
\newcommand{\subequivneg}{Logical Equivalence and Negations}
\newcommand{\subpffcontra}{Proof Format: Contradiction}
\newcommand{\subsetgame}{The Game SET}
\newcommand{\subquant}{Quantifiers}
\newcommand{\subpffquants}{Proof Formats: $\forall$ and $\exists$}
\newcommand{\subcex}{Negating Quantified Statements and Counterexamples}
\newcommand{\subifthen}{Promises: Conditional Statements}
\newcommand{\subpffifthen}{Proof Format: Direct Proof of $\to$}
\newcommand{\subnegcond}{Broken Promises: Negating Conditional Statements}
\newcommand{\subpfforimplication}{Proof Formats: Proof of $\lor$ Using Implication}
\newcommand{\subconv}{The Converse and Biconditional Statements}
\newcommand{\subpffiff}{Proof Format: $\leftrightarrow$}
\newcommand{\subcp}{The Contrapositive}
\newcommand{\subpffcp}{Proof Format: $\to$ Using the Contrapositive}
\newcommand{\subequiv}{Logical Equivalence}
\newcommand{\subneg}{Simplifying Negations}
\newcommand{\subinference}{Logical Inference}
\newcommand{\subinfsetsnumbers}{Infinite sets of numbers}
\newcommand{\subdefnfnnotation}{Function Notation and Vocabulary}
\newcommand{\subpiecewise}{Piecewise-defined Functions}
\newcommand{\subfndotgraphs}{Dot Diagrams and Graphs of Functions}
\newcommand{\subfloorceiling}{Floor and Ceiling}
\newcommand{\subnumberfn}{Number-theoretic Functions}
\newcommand{\subfngraphs}{Graph-theoretic Functions}
\newcommand{\subbitstringfunctions}{Functions Involving Bit Strings}
\newcommand{\suborderedpair}{Ordered Pairs and the Definition of Function}
\newcommand{\subpairing}{Pairings}
\newcommand{\subonetooneonto}{One-to-one and Onto}
\newcommand{\subperms}{Permutations}
\newcommand{\subinverses}{Inverse Functions}
\newcommand{\subpffunique}{Proof Format: Uniqueness}
\newcommand{\subdefnseq}{The Definition of Sequence}
\newcommand{\submodelseq}{Modeling with Explicitly-defined Sequences}
\newcommand{\subseqprimes}{Detour: Sequences Involving Primes}
\newcommand{\subelements}{Elements of a Set}
\newcommand{\subsetbuild}{Set-Builder Notation}
\newcommand{\subsetops}{Set Operations}
\newcommand{\subsubsets}{Subsets of a Set}
\newcommand{\subbsrepsubset}{Bit String Representation of Subsets}
\newcommand{\subsetsofsets}{Sets of Sets}
\newcommand{\subsetfn}{Detour: Set-theoretic Functions}
\newcommand{\subdefnpartition}{The Definition of Partition}
\newcommand{\subselfconj}{Conjugate Partitions}
\newcommand{\subbulgsol}{Collecting Coins}
\newcommand{\subcartprod}{The Cartesian Product of Sets}
\newcommand{\subfncartprod}{Functions Involving Cartesian Products}
\newcommand{\subdefnrelation}{Relations and Their Representations}
\newcommand{\subrelppty}{Properties of Relations}
\newcommand{\subequivclass}{Equivalence Relations and Equivalence Classes}
\newcommand{\subcongmod}{Congruence mod $n$}
\newcommand{\subhanoi}{The Towers of Hanoi}
\newcommand{\subrecdefseq}{Recursively-defined Sequences}
\newcommand{\subntr}{Modeling with Recursively-defined Sequences}
\newcommand{\subpffmathind}{Proof Format: Mathematical Induction}
\newcommand{\subalgind}{Algebra: Evaluating $f(n-1)$}
\newcommand{\subpffindseq}{Proof Format: Special Case of Mathematical Induction for Proving an Explicit Rule for a Recursively-defined Sequence}
\newcommand{\submatpowers}{Matrix Products and Powers}
\newcommand{\subpffindmatrix}{Proof Format: Special Case of Mathematical Induction for Proving an Explicit Formula for the Power of a Matrix}
\newcommand{\subgroups}{Finite Groups}
\newcommand{\subproperbs}{Proper Bit Strings}
\newcommand{\subrecsets}{Recursively-defined Sets}
\newcommand{\subrecgraphs}{Recursively-defined Graphs}
\newcommand{\subfib}{The Fibonacci Sequence and Higher Order Recursions}
\newcommand{\submodelhigher}{Modeling with Higher Order Recursions}
\newcommand{\subfibpatterns}{Detour: Fibonacci Patterns and Proof}
\newcommand{\subpffstrongind}{Proof Format: Strong Mathematical Induction}
\newcommand{\subhowmanysq}{Counting Squares}
\newcommand{\subfactrep}{Factorial Representations}
\newcommand{\subsigmapi}{Sum and Product Notation}
\newcommand{\subbaseb}{Base $b$ Representation}
\newcommand{\subbinary}{Binary Representation}
\newcommand{\subhex}{Hexadecimal Representation}
\newcommand{\subhexforbinary}{Hex as a Shorthand for Binary}
\newcommand{\subsumconj}{Sum Conjectures}
\newcommand{\subprodconj}{Product Conjectures}
\newcommand{\subsumfib}{Detour: Fibonacci Sums}
\newcommand{\subfactorpolys}{Algebra: Factoring Polynomials}
\newcommand{\subarithtri}{The Arithmetic Triangle}
\newcommand{\subpascalpatterns}{Patterns in the Arithmetic Triangle}
\newcommand{\subbinomthm}{The Binomial Theorem}
\newcommand{\subfactorialbinom}{Explicit Formula for Binomial Coefficients}
\newcommand{\subpffsumproofsind}{Proof Format: Special Case of Mathematical Induction for Proving Sum and Product Formulas}
\newcommand{\subpffcombsums}{Proof Format: Combinatorial Proof of Sums}
\newcommand{\subspecialsum}{Detour: Special Sums}
\newcommand{\subfracalg}{Algebra: Fraction Arithmetic}
\newcommand{\subhotelinf}{Hotel Infinity}
\newcommand{\subdefndiscrete}{The Definition of Discrete}
\newcommand{\seclisting}{Organized Listing}
\newcommand{\vocab}{\textbf}
\newcommand{\str}{\texttt}
\newcommand{\fn}{\texttt}
\newcommand{\bs}{\texttt}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section3.3Coloring Graphs
In many logistical applications of graph theory, the problem can be translated into a question about coloring graphs. Examples of such applications include 1
source: wikipedia, graph coloring
scheduling (events or tasks), resource allocation (such as assigning computer registers), and physical arrangements (such as assigning seating). In this section, we introduce graph coloring, look at applications to scheduling, and consider the minimum number of colors needed for standard graphs.
You can use letters for the colors, such as B = blue, G = green, R = red, P = purple. You can color it by hand Four Color Challenge color the map there, and capture a screenshot of your solution.
Draw a rectangle and divide it into six regions to create a new map that can be colored using only two colors. And show how to color it using B = blue and G = green.
Draw a rectangle and divide it into six regions to create a new map that can be colored using three colors but not two colors. Show how to color it using three colors: B = blue, G = green, and R = red and explain why it is impossible to color it using only two colors.
In the map you colored in (a), find a portion of the map with four regions where all four colors were needed. Copy that portion of the map and show that four colors work using B = blue, G = green, R = red, P = purple. Next, explain why it is impossible to color that portion of the map using only three colors. Hint: if it is possible to color that portion of the map using only three colors, then you need to pick a different portion.
Draw a graph with a vertex for each region of the map of midwest states shown in Figure 3.1.22 (in Section 3.1 Exercise 5). Draw an edge between two vertices if the corresponding regions share an edge (more than a point).
Solution.
Rephrase the map coloring question as a question about the graph.
Solution.
What is the smallest number of colors that we need in order to color the vertices of the graph in such a way that adjacent vertices are different colors?
The chromatic number of a graph is the smallest number of colors needed to color the graph. For example, the complete bipartite graph, \(K_{6,3}\text{,}\) shown in Figure 3.2.10 has chromatic number two because it can be colored using two colors (black and white) and one color would not work because there are adjacent vertices.
Example3.3.6Chromatic number of complete graph and cycle.
Determine the chromatic number \(k\) of each graph by finding a \(k\)-coloring and then explaining why all \(k\) colors are necessary.
The complete graph \(K_5\text{.}\)Solution.
First, we can color each vertex its own color using five colors. Since any pair of vertices in \(K_5\) are adjacent, they must be different colors and so we cannot use fewer than five colors. Thus, the chromatic number of \(K_5\) is five.
If we try to color the vertices of \(C_5\) using only two colors (gray and black), as shown in Figure 3.3.7, we run into a problem. The fifth vertex cannot be gray (because it is adjacent to a vertex colored gray) and it cannot be black (because it is adjacent to a vertex colored black). It must be a third color, say white.
To show the chromatic number of a graph is \(k\text{,}\) you should draw the graph, show how to color the vertices using \(k\) colors, and then explain why fewer than \(k\) colors cannot work.
Explain why the chromatic number of the cycle graph \(C_4\) is two but the chromatic number of the cycle graph \(C_5\) is three.
Example3.3.10Chromatic number of complicated graphs.
Find the chromatic number of the wheel graph \(W_5\text{.}\)Solution.
First, notice that the five outer vertices form a copy of \(C_5\text{.}\) Since \(C_5\) has chromatic number three, the outer vertices require at least three different colors. The hub vertex is adjacent to all five outer vertices, and so it must be yet another color. Therefore, we need at least four colors to color the wheel \(W_5\text{.}\)
Find the chromatic number of the graph \(E\) drawn in Figure 3.3.9.
Solution.
First, notice that the center four vertices form a copy of \(K_4\text{.}\) Since \(K_4\) has chromatic number four, we know that those four vertices must be four different colors. Therefore, we need at least four colors to color the entire graph \(E\text{.}\)
Each organization can run only one of its events at a time. In addition, events A and V both want to use the theater and events M, P, and N all want to use the main conference hall, so those events need to be at different times.
Draw a graph representing the situation where each event is a vertex and an edge connects two events if they cannot be scheduled in the same time block.
Solution.
Color each vertex with a time that event could be scheduled using the key: black = late morning, gray = early afternoon, and white = late afternoon.
Solution.
We have looked at several specific graphs and calculated quantities such as the number of vertices and edges, the degree sequence, and the chromatic number. What about families of graphs? Let’s look at an example.
Example3.3.16Graph conjectures for the complete graphs.
Consider the complete graphs \(K_s\) for \(s \ge 1\text{.}\) Conjecture the number of vertices and edges, the degree sequence, and the chromatic number of \(K_s\text{.}\) Some of your answers should involve \(s\text{.}\)
By definition, \(K_s\) has \(s\) vertices. Recall that \(K_s\) models the number of handshakes in a group of \(s\) people. By Theorem 1.1.4, the number of edges is \(1+2+3+\ldots+(s-1) = \frac{s(s-1)}{2}\text{.}\) Alternatively, there is an edge for each pair of vertices. Thus, the number of edges is equal to the number of ways to select two out of \(s\) vertices, which is \(\binom{s}{2}\text{.}\)
We can color the vertices of \(K_s\) with \(s\) colors by assigning each vertex its own color. Because each vertex is adjacent to every other vertex, no two vertices can be the same color. Thus, all \(s\) colors are necessary. The chromatic number of \(K_s\) is \(s\text{.}\)
Consider the star graphs \(K_{1,t}\) for \(t \ge 2\text{.}\) Conjecture the number of vertices and edges, the degree sequence, and the chromatic number of \(K_{1,t}\text{.}\) Some of your answers should involve \(t\text{.}\)
Consider the paths \(P_s\) for \(s \ge 2\text{.}\) Conjecture the number of vertices and edges, the degree sequence, and the chromatic number of \(P_s\text{.}\) Some of your answers should involve \(s\text{.}\)
Consider the cycles \(C_s\) for \(s \ge 3\text{.}\) Conjecture the number of vertices and edges, the degree sequence, and the chromatic number of \(C_s\text{.}\) Some of your answers should involve \(s\text{.}\)
Go to Map Colouring to color more complicated maps. Save screenshots of three puzzles that you attempted. Were you able to solve all three? If not, where did you get stuck?
Copy the map of the northeast states drawn in Figure 3.3.21 and show how to 4-color the map. Note: Both parts of New York (NY) should be one color — one part (Upstate New York) is labeled NY, the other part (NYC/Long Island) sits below Connecticut (CT)/Rhode Island (RI) and is long and skinny.
Copy the map of midwest states drawn in Figure 3.1.22 (in Section 3.1 Exercise 5) and show how to color the map using three colors. Note: We discussed this map in Example 3.3.3.
Find a portion of the map where all three colors were needed. Copy that portion of the map and explain why it is impossible to color that portion of the map using only two colors.
Read the Quanta magazine article “Only Computers Can Solve This Map-Coloring Problem” and answer the following questions based on that article.
According to this article, the Four-Color Problem was introduced in a letter, which is a common way mathematics was communicated historically. Who wrote the letter and to whom did they send it?
There are seven people and seven committees. Each person is on several committees, as described by Table 3.3.32. There are four standard meeting times: 8-9:30 AM, 10-11:30 AM, 2-3:30 PM, and 4-5:30 PM. We would like to schedule meeting times for the committees in such a way that we avoid having two meetings at the same time if any person is a member of both committees. Is there a way to do it?
Is there a way to assign meeting times? If so, color each vertex with a time it could meet using the key: red is 8-9:30 AM, blue is 10-11:30 AM, green is 2-3:30 PM, and orange is 4-5:30 PM.
Hint: An edge should indicate that the two committees have at least one member in common, which means that that pair of committees cannot be scheduled at the same time. The graph has seven vertices and 12 edges.
What can we say about the chromatic number \(k\) of a graph \(G\) if …? Your answer should be a conjecture in the form of an equation or inequality involving \(k\text{.}\)
Here is an algorithm to 4-color the vertices of graph \(G\) when the maximum degree of any vertex in \(G\) is three.
Assign each color a number: red (1), blue (2), green (3), and orange (4). Label the vertices \(v_1\text{,}\)\(v_2\text{,}\) …, \(v_n\text{.}\) Color the vertex \(v_1\) red (1).
Go to the next vertex and color it the smallest number color that is available, keeping in mind that the vertex cannot be colored the same as any adjacent vertex. Repeat this step until \(v_n\) is colored.
Now consider a general graph \(G\) where the maximum degree of any vertex is three. Explain why there will always be a color available in Step 2 of the algorithm. Hint: Each vertex has degree three.
Hint: When we get to a new vertex to color, how many colors are already used by its neighbors? Explain why there is always at least one of the four colors available to color the new vertex?
There are many correct answers to each part. The hints describe how to build one such example.
Hint: There are many correct answers. Try starting with the star \(K_{1,3}\) which is a complete bipartite graph, but then add more vertices and connect them with an edge to the leaves in \(K_{1,3}\text{.}\)
SubsubsectionExercises for 3.3.C Graph Conjectures
15.Practice.
Consider the complete bipartite graphs \(K_{s,t}\) for \(s,t \ge 1\text{.}\) Conjecture the number of vertices and edges, the degree sequence, and the chromatic number of \(K_{s,t}\text{.}\) Some of your answers should involve \(s\) or \(t\text{.}\)
Consider the wheels \(W_s\) for \(s \ge 3\text{.}\) Conjecture the number of vertices and edges, the degree sequence, and the chromatic number of \(W_s\text{.}\) Some of your answers should involve \(s\text{.}\)
Hint: There are \(s+1\) vertices, there is exactly one vertex with degree \(s\text{,}\) and the chromatic number is three or four depending on whether \(s\) is even or odd (be sure to say which is which).
Consider the ladders \(L_{2 \times t}\) for \(t \ge 2\text{.}\) Conjecture the number of vertices and edges, the degree sequence, and the chromatic number of \(L_{2 \times t}\text{.}\) Some of your answers should involve \(t\text{.}\)
Hint: There are four vertices of degree two, and the rest have degree three. One way to count edges is to add the number of horizontal edges in the first row, the number of horizontal edges in the second row, and the number of vertical rungs.
How to count the number of vertices, the number of edges, the degree sequence, and the chromatic number for a family of graphs (in terms of parameters such as \(s\) or \(t\))?
For \(s,t \ge 1\text{,}\) the grid graph (or lattice graph) is denoted \(L_{s\times t}\text{.}\) Its vertices are the point,s \((x,y)\text{,}\) in the \(xy\)-plane where \(x = 1, 2, \ldots,
s\) and \(y = 1, 2, \ldots, t\text{.}\) There is an edge connecting two points with the same \(x\)-coordinate when their \(y\)-coordinates differ by 1. Also, there is an edge connecting two points with the same \(y\)-coordinate when their \(x\)-coordinates differ by 1. The ladder graphs are the special case where \(s=2\text{.}\)
List the vertices of \(L_{3 \times 4}\) and draw those points in the \(xy\)-plane.
The tree \(B_1\) has a root vertex at the top. The root vertex is adjacent to two child vertices drawn below. The tree \(B_2\) starts with the tree \(B_1\) and then, for each end vertex, draws two new adjacent child vertices below. These new vertices are grandchildren of the root. The tree \(B_3\) starts with \(B_2\) and then, for each end vertex, draws two new adjacent child vertices below. These new vertices are great-grandchildren of the root. This pattern continues to give a family of perfect binary trees, denoted \(B_s\) for \(s\ge 1\text{.}\)
In the perfect binary tree \(B_3\text{,}\) count the number of children, the number of grandchildren, and the number of great-grandchildren of the root. Use these numbers to find the number of vertices in \(B_3\text{.}\) Hint: don’t forget the root.
What are the degrees of the vertices in \(B_s\) and how many vertices of each degree are there? Hint: The root and the leaves have degrees that are from the middle vertices.
Draw the cycle \(C_5\text{.}\) Then, using a different colored pen, add the edges of the complement \(\overline{C_5}\) to your graph. What is the resulting graph?
Draw the path \(P_5\text{.}\) Then, using a different colored pen, add the edges of the complement \(\overline{P_5}\) to your graph. What is the resulting graph? It might look a little different than usual.
If we draw a graph \(G\) that has five vertices and then, using a different colored pen, we add the edges of the complement \(\overline{G}\) to the graph, what is the resulting graph? Explain.
Generalize: if \(G\) is any graph with \(s\) vertices and \(m\) edges, how many edges does the complement \(\overline{G}\) have? Hint: Theorem 3.3.17 is useful.
