CSC/MAT 208 (Spring 2024)

Lab: Graph Problems

Problem 1: Bipartiteness

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:

    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

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 contains 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:

    \(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

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 contains 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 contains 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.”)