Graph Theory

For the next Olympic Winter Games, the organizers wish to expand the number of teams competing in curling. They wish to have $14$ teams enter, divided into two pools of seven teams each. Right now, they're thinking of requiring that in preliminary play each team will play seven games against distinct opponents. Five of the opponents will come from their own pool and two of the opponents will come fro…

A pharmaceutical manufacturer is building a new warehouse to store its supply of $10$ chemicals it uses in production. However, some of the chemicals cannot be stored in the same room due to undesirable reactions that will occur. The matrix below has a $1$ in position $(i,j)$ if and only if chemical $i$ and chemical $j$ cannot be stored in the same room. Develop an appropriate graph theoretic model and determine…

A school is preparing the schedule of classes for the next academic year. They are concerned about scheduling calculus, physics, English, statistics, economics, chemistry, and German classes, planning to offer a single section of each one. Below are the lists of courses that each of six students must take in order to successfully graduate. Determine the smallest number of class periods that can be…

All trees with more than one vertex have the same chromatic number. What is it, and why?

Let $\GVE$ be a graph with $V=\{v_1,v_2,\dots,v_n\}$. Its degree sequence is the list of the degrees of its vertices, arranged in nonincreasing order. That is, the degree sequence of $\mathbf{G}$ is $(\deg_\mathbf{G}(v_1),\deg_\mathbf{G}(v_2),\dots,\deg_\mathbf{G}(v_n))$ with the vertices arranged such that $\deg_\mathbf{G}(v_1) \geq \deg_\mathbf{G}(v_2)\geq \cdots\geq \deg_\mathbf{G}(v_n)$. Below are five sequences of integers (along with $n$, the number of integers in the sequence). Identify

• the one sequence that cannot be the degree sequence of any graph;
• the two sequences that could be t…

Construct the labeled tree $\bfT$ with Prüfer code $96113473$.

Construct the labeled tree $\bfT$ with Prüfer code (using commas to separate symbols in the string, since we have labels greater than $9$) $10,1,7,4,3,4,10,2,2,8$.