Lab: Graph Problems

Because graphs describe such a wide variety of phenomena, it is not surprising that there are many graph problems we might consider. A comprehensive study of graph theory and algorithms is beyond the scope of this course, but it is important as a working computer programmer to be aware of these different problems. Being able to see a graph problem lurking within the problem you are trying to solve usually leads to a quick and efficient solution!

In this lab, we’ll explore several of the most common graph problems. You’ll employ artificial and real-world examples to understand the practical nature of the formal definitions involved with the problem. And then, you’ll use that built-up intuition to explore a problem within this area of graph theory.

Problem 1: Bipartiteness

Definition (Bipartite Graphs) Let $G = (V, E)$ be a simple graph. We call $G$ bipartite if there exists a partition of the vertices of $V$ into two sets, $V_1$ and $V_2$ such that $V_1 \cap V_2 = \emptyset$ and for any edge $(u, v) \in E$, $u \in V_1$ and $v \in V_2$.

1. Create two artificial examples of graphs, one that is bipartite and one that is not bipartite.
2. Instantiate your artificial examples to a real-world example where the notion of bipartiteness would be useful. Describe what the vertices and edges of your graph represent and describe how to interpret the notion of bipartiteness in this context.

3. Consider the following additional definition:

   Definition (Perfect Matching): Let $G = (V, E)$ be a simple graph. A perfecting matching $M \subseteq E$ of $G$ is a subset of the edges of $E$ such that every vertex of $V$ is incident (i.e., mentioned) in exactly one edge of $M$.

   Give a perfect matching, if there exists one, in your positive artificial example above, and in a sentence or two, describe what a perfecting matching means in your real-world scenario.

Problem 2: Cliques

Definition (Cliques) Let $G = (V, E)$ be a simple graph. A clique is a subset of vertices $V’ \subseteq V$ such that for any pair of vertices $u, v \in V’$ that $(u, v) \in E$. Call a $k$-clique a clique that contains $k$ vertices.

1. Create two artificial examples of graphs, one that contains a $4$-clique and one that does not contain a $4$-clique, i.e., a clique of size $4$.
2. Instantiate your artificial examples to a real-world example where the notion of a clique would be useful. Describe what the vertices and edges of your graph represent and describe how to interpret the notion of clique in this context.

3. Consider the following additional definition:

   Definition (Complete Graph): $G = (V, E)$ is a complete graph if for every pair of vertices $u, v \in V$, $(u, v) \in E$.

   In a few sentences, describe what the relationship is between a complete graph and a clique and describe what this interpretation means in the context of the real-world example you gave previously.

Problem 3: Coloring

Definition (Coloring) Let $G = (V, E)$ be a simple graph and $C$ be a set of colors. A coloring of graph $G$ is a function $h : V \rightarrow C$ such that for any pair of vertices $u, v \in V$, if $(u, v) \in E$, then $h(u) \neq h(v)$. We call a graph $k$-colorable if it has a coloring with a set of $k$ colors.

1. Create two artificial examples of graphs, one that contains a $3$-coloring and one that does not contain a $3$-coloring, i.e., a coloring of size $3$.

2. The famous four color theorem says the following:

   Theorem (The Four Color Theorem): any map can be colored with at most four colors.

   By “map” in this claim, we mean a geographic map, e.g., a map of the United States, or a map of the counties in Iowa. Test this theorem out by drawing 2–3 simple maps with, e.g., 5–6 regions and giving them a 4-coloring.

3. For each of your maps, give a corresponding graph that represents that map. What do nodes and edges represent in the graph?

4. Draw a graph that does not contain a 4-coloring and attempt to translate it into a physical map based on your answer to the previous part. In a sentence or two, what about that graph makes it so that you cannot translate it into a geographic map?

   (Hint: for a simple non-4-colorable graph, look back to problem 2 and the notion of completeness. Using completeness, try to sketch out the smallest possible graph that certainly does not contain a 4-coloring because it has “too many edges.”)