Skip to main content
\(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\mbox{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section1.5Exercises

1

For each of the following sequences, either give an example of such a graph, or explain why one does not exist.

  1. A graph with six vertices whose degree sequence is \([5,5,4,3,2,2]\)

  2. A graph with six vertices whose degree sequence is \([5,5,4,3,3,2]\)

  3. A graph with six vertices whose degree sequence is \([5,5,5,5,3,3]\)

  4. A simple graph with six vertices whose degree sequence is \([5,5,5,5,3,3]\)

2

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 from the other pool. They're having trouble setting up such a schedule, so they've come to you. By using an appropriate graph-theoretic model, either argue that they cannot use their current plan or devise a way for them to do so.

3

Figure 1.5.6 contains four graphs on six vertices. Determine which (if any) pairs of graphs are isomorphic. For pairs that are isomorphic, give an isomorphism between the two graphs. For pairs that are not isomorphic, explain why.

Figure1.5.6Are these graphs isomorphic?
4

Let \(\bfG\) be a simple graph with \(n\) vertices and degree sequence \(a_1,a_2,\dots,a_n\text{.}\) What's the degree sequence of its complement \(\bfG^c\text{?}\)

5

Let \(G\) be the graph with graph with vertices consisting of the 10 three element subsets of \(\{a,b,c,d,e\}\text{,}\) and two vertices adjacent if they share exactly one element. So, for example, the two vertices \(v=\{a,c,e\}\) and \(w=\{b,c,d\}\) are adjacent, but neither \(v\) or \(w\) is adjacent to \(u=\{a,b,c\}\text{.}\)

Draw \(G\) in a way that shows it is isomorphic to the Petersen graph.

Now let \(H\) be the graph with vertices consisting of the 10 two element subsets of \(\{a,b,c,d,e\}\text{,}\) and two vertices adjacent if they share no elements. Without drawing \(H\text{,}\) write down an isomorphism between \(G\) and \(H\text{.}\) Hint: There's a "natural" bijection between the two and three element subsets of \(\{a,b,c,d,e\}\)

6

Recall that \(G^c\) denotes the complement of a graph \(G\text{.}\) Prove that \(f:G\to H\) is an isomorphism of graphs if and only if \(f:G^c\to H^c\) is an isomorphism.

7

Determine the number of non-isomorphic simple graphs with seven vertices such that each vertex has degree at least five.

Hint

Consider the previous exercise

8

Consider the standard Instant Insanity puzzle, with four cubes and four colours. Explain why one would expect there to be 331,776 different cube configurations. Further explain why there would be fewer configurations if any cubes are coloured with symmetries.

In the text, we solve the puzzle by finding certain pairs of subgraphs. Assuming that none of the cubes are coloured symmetrically, explain why each pair of subgraphs corresponds to at least 8 different cube configurations that are actually solutions, and why, depending on the isomorphism type of the subgraphs found, there may be more solutions.

9

Variations of the Insant Insanity puzzle increase the number of cubes and the number of colours. Explain how to modify our graph theoretic solution to solve the puzzle when we have \(n\) cubes, each face of which is coloured one of \(n\) colours, and we want to line up the cubes so that each of the top, bottom, front and rear strings of cubes displays each of the \(n\) colours exactly once.

10

Use the method from the previous question to solve the following set of six cubes, marketed under the name "Drive ya crazy", where each face is coloured either blue, cyan, green, orange, red, or yellow.

Figure1.5.7The six cubes from "Drive Ya crazy"