Problem Set 4

Due Friday, October 22 at 2:30 pm Pacific

---

This fourth problem set explores graph theory and the pigeonhole principle. It’s designed to take you on a tour of the beauty of finite structures and some of their amazing properties. Plus, you’ll get to see some pretty pictures and learn about why all this matters in the first place. 😃

Good luck, and have fun!

Starter Files

Here are the starter files for the problems you'll submit electronically:

📦 PS4 Starter Files

Unpack the files somewhere convenient and open up the bundled project.

If you would like to type your solutions in $\LaTeX$, you may want to download this template file where you can place your answers:

🖋 PS4 $\LaTeX$ Template

Problem One: Independent and Dominating Sets

As a refresher from lecture, an independent set in a graph $G = (V, E)$ is a set $I \subseteq V$ with the following property:

\[\forall u \in I. \forall v \in I. \Set{u, v} \not\in E \text.\]

Now, a new definition. A dominating set in $G$ is a set $D \subseteq V$ with the following property:

\[\forall v \in V. (v \not\in D \to \exists u \in D. \Set{u, v} \in E)\text.\]

In general, whenever you find a new definition or new mathematical term, it’s good to play around with the definition a bit to get a feel for what it looks like.

1. Give two different examples of dominating sets of the graph shown below, each of which has cardinality four or less. No justification is necessary.

   

2. Let $G = (V, E)$ be an arbitrary graph with the following property: every node in $G$ is adjacent to at least one other node in $G$. Prove that if $I$ is an independent set in $G$, then $V - I$ is a dominating set in $G$.

   Notice that we're asking you to show that $V - I$ is a dominating set, not that $I$ is a dominating set. Also, we recommend drawing some pictures here to get a sense of how this works.

   Use the formal definitions to guide your proofs. If you proceed via a direct proof or via contrapositive, what, exactly, will you be assuming, and what will you be proving? If you write this as a proof by contradiction, what specifically is it that you’re assuming for the sake of contradiction?

An independent set $I$ in a graph $G$ is a maximal independent set in $G$ if there is no independent set $I'$ in $G$ where $I \subsetneq I'$. (Here, $I \subsetneq I'$ denotes that $I$ is a strict subset of $I'$, meaning that $I \subseteq I'$ and $I \ne I'$).

3. Find independent sets $I$ and $J$ of the graph from part (i) of this problem such that $I$ is maximal but $\abs{I} \lt \abs{J}$. No justification is necessary.

   Yes, this is possible. The definition of a maximal independent set is meant to be taken literally.

4. Prove that if $I$ is a maximal independent set in $G = (V, E)$, then $I$ is a dominating set of $G$.

   You can build a great intuition for this result by drawing some pictures and thinking about what has to happen for a set of nodes to be an independent set and for a set of nodes to be a dominating set. When it comes time to write out your proof, however, you’ll need to use the formal first-order definitions of independent sets, maximal independent sets, and dominating sets.

Problem Two: Linkage Graphs

Graphs come in all shapes and sizes. This problem concerns a particular family of graph called the linkage graphs and some of their properties.

First, a new piece of notation. The uniqueness quantifier, denoted $\exists!x. A$, means “there exists exactly one choice of $x$ where $A$ is true.” For example, the statement $\exists!c. Cat(c)$ says “there is exactly one cat,” and the statement

\[\begin{aligned} & \forall p. (Person(p) \to \\ & \quad \exists!r. (Robot(r) \land Loves(p, r)) \\ &)\end{aligned}\]

says “everyone loves exactly one robot.”

With that in mind, let’s begin with a definition. An undirected graph $G = (V, E)$ is called a linkage graph if it satisfies the following requirement:

\[\begin{aligned} & \forall u \in V. \forall v \in V. (u \ne v \to \\ & \quad \exists!z \in V. (\Set{u, z} \in E \land \Set{v, z} \in E) \\ & ) \end{aligned}\]

As a reminder, undirected graphs cannot have edges from nodes back to themselves.

This definition is surprisingly compact, and yet it tells us a lot about the structure of linkage graphs. In the remainder of this problem, you’ll explore some properties of linkage graphs and eventually get a feeling for what shapes they have.

1. Prove that if $G = (V, E)$ is a linkage graph, then $G$ does not contain any cycles of length four.

   This is a great spot to draw a bunch of pictures. See if you can intuit this one visually, then translate what you’ve drawn out into a formal written argument.

In lecture, we talked about triangles in graphs. As a refresher, a triangle in a graph is a cycle of length three.

2. Let $G = (V, E)$ be a linkage graph with more than one node. Prove that for every node $v \in V$, there’s a triangle that contains $v$.

   Again, draw pictures.

3. Run the provided starter program and choose the “Graph Editor” option. Use the provided program to draw a linkage graph with exactly seven nodes in res/Linkage.graph. You can check your answer using the “Run Tests” button. Submit this file online via Gradescope.

Problem Three: Friends, Strangers, Enemies, and Hats

In lecture, we proved the Theorem on Friends and Strangers, which says that if you have a group of six people where, for each pair of people, those people either know one another (they’re friends) or they don’t know each other (they’re strangers), you can always find three mutual friends or three mutual strangers. Here, “three mutual friends” means “three people where each two of them are friends,” and “three mutual strangers” means “three people where each two of them are strangers.”

This is one of many different results about what must happen when you get a sufficiently large number of people together. The rest of this problem explores some other results in that vein.

1. There’s a party with 36 attendees. Each person is wearing a hat, and there are seven possible hat colors: aureolin, bole, chartreuse, drab, ecru, fulvous, and gamboge. (Yes, those are all colors.) As in the Theorem on Friends and Strangers, for any pair of people at the party, either the pair are friends or the pair are strangers.

   Prove that you can always find three mutual friends all wearing the same color hat or three mutual strangers all wearing the same color hat.

2. There’s a party with 17 attendees. This time, things are a bit more complicated. For each pair of people at the party, either those people are strangers, those people are friends, or those people are enemies. Fortunately, none of them are wearing hats. 😃

   Prove that you can always find three mutual friends, or three mutual strangers, or three mutual enemies.

Find problems like these interesting? Take Math 107 (Graph Theory) or Math 108 (Combinatorics)!

Problem Four: Bipartite Graphs

The bipartite graphs are an important and common family of graphs. They appear in a huge number of settings – error-correcting codes, computational social choice theory, and algorithm design, to name a few.

Let’s begin with a formal definition. An undirected graph $G = (V, E)$ is called bipartite if there exist two sets $V_1$ and $V_2$ such that

• every node $v \in V$ belongs to exactly one of $V_1$ and $V_2$, and
• every edge $e \in E$ has one endpoint in $V_1$ and the other in $V_2$.

The sets $V_1$ and $V_2$ here are called bipartite classes of $G$.

1. Suppose you have an $8 \times 8$ chessboard. We form a graph from the board as follows: there's a node for each square on the board, and an edge between any pair of squares that are immediately adjacent in one of the four cardinal directions (up, down, left, and right).

   Explain why this is a bipartite graph by telling us what the bipartite classes are and briefly explaining why all the edges have one endpoint in each bipartite class.

   Don’t do this in your head – draw lots of pictures!

Bipartite graphs have many interesting properties. One of the most fundamental is this one:

Theorem: An undirected graph $G$ is bipartite if and only if it contains no closed walks of odd length.

The forward direction of this implication has a nice intuition.

2. Explain, intuitively, why if $G$ is bipartite, then it has no closed walks of odd length. Specifically, give us a brief, informal explanation as to why every closed walk in $G$ has to have even length.

   It might help to draw some pictures.

The reverse direction of this implication – that if $G$ has no closed walks of odd length, then $G$ is bipartite – requires a different sort of argument.

Let’s pick some arbitrary graph $G = (V, E)$ that has no closed walks of odd length. For simplicity’s sake, we’ll assume that $G$ has just one connected component. If $G$ has two or more connected components, we can essentially treat each one of them as independent graphs. (Do you see why?)

Now, choose any node $x \in V$. Using node $x$ as an “anchor point,” we can define two sets $V_1$ and $V_2$ that we’ll need for the remainder of this argument:

\[V_1 = \Set{v \in V \suchthat \text{there is an odd-length walk from } x \text{ to } v }\] \[V_2 = \Set{v \in V \suchthat \text{there is an even-length walk from } x \text{ to } v }\]

This turns out to be a really useful way to group the nodes of $G$.

3. Given the choices of $G$ and $x$ from above, prove that $V_1$ and $V_2$ have no nodes in common.

   Remember that there might be multiple different walks of different lengths from $v$ to some other node $x$, so be careful not to talk about “the” walk between $v$ and $x$. Also note that these walks are not necessarily paths.

4. Using your result from part (iii), prove that $G$ is bipartite.

   The most common mistake on this problem is to not address all the parts of the definition of a bipartite graph. So start off by writing down a list of what you need to prove, then address each part in turn.

Problem Five: Iterated Injections

Let $f : A \to A$ be an injection from a finite set $A$ to itself. (A finite set is one whose size is a natural number.) Your goal in this problem is to prove the following result:

Theorem: For each $a \in A$, there is an $n \in \naturals$ where $f^{n+1}(a) = a$.

In other words, if you take any element $a \in A$ and repeatedly apply $f$ to $a$, you will eventually get back what you started with.

Here’s how we’re going to prove this. Pick any $a \in A$, and let $k = \abs{A}$. Now, look at the sequence

\[f^0(a), f^1(a), f^2(a), f^3(a), \dots, f^k(a)\text.\]

This is what you get if you start at $a$ and keep applying $f$ over and over again.

1. Prove that this sequence must contain at least one duplicate value.

Now, take the sequence above and consider the largest value of $n$ such that the sequence

\[f^0(a), f^1(a), \dots, f^n(a)\]

contains no repeated values. Since this is the longest such sequence, we know that the next term in the sequence, $f^{n+1}(a)$, must be equal to some term of the sequence shown above.

2. Prove that $f^{n+1}(a) = a$. (This proves the above theorem.)

This theorem has a bunch of surprising applications.

3. Let $f : A \to A$ be an injection from a finite set to itself. Prove that $f$ is also a bijection.

One consequence of your result from part (iii) is that if an injective function from a set $A$ to itself is not a bijection, then $A$ must not be finite. And indeed, this is one possible way to define what it means for a set to be infinite!

Optional Fun Problem: The Mouse and the Cheese

Suppose that you have a $3'' \times 3'' \times 3''$ cube of cheese subdivided into twenty-seven smaller $1'' \times 1'' \times 1''$ cubes of cheese. A mouse wants to eat the entire cube of cheese and does so as follows: she first picks any small cube to eat first, then moves to an adjacent small cube of cheese (i.e. a cube that shared a face with the cube that was just eaten) to eat next, then repeats this process.

Is it possible for the mouse to eat the center cube of cheese last? If so, show how. If not, prove it's impossible.