91Ó°ÊÓ

Prove the 6 -color theorem: every planar graph has chromatic number 6 or less. Do not assume the 4 -color theorem (whose proof is MUCH harder), but you may assume the fact that every planar graph contains a vertex of degree at most \(5 .\)

At a school dance, 6 girls and 4 boys take turns dancing (as couples) with each other. (a) How many couples danced if every girl dances with every boy? (b) How many couples danced if everyone danced with everyone else (regardless of gender)? (c) Explain what graphs can be used to represent these situations.

For each of the following, try to give two different unlabeled graphs with the given properties, or explain why doing so is impossible. (a) Two different trees with the same number of vertices and the same number of edges. A tree is a connected graph with no cycles. (b) Two different graphs with 8 vertices all of degree 2 . (c) Two different graphs with 5 vertices all of degree 4 . (d) Two different graphs with 5 vertices all of degree 3 .

Not all graphs are perfect. Give an example of a graph with chromatic number 4 that does not contain a copy of \(K_{4}\). That is, there should be no 4 vertices all pairwise adjacent.

Euler's formula \((v-e+f=2)\) holds for all connected planar graphs. What if a graph is not connected? Suppose a planar graph has two components. What is the value of \(v-e+f\) now? What if it has \(k\) components?

Is there anything we can say about whether a graph has a Hamilton path based on the degrees of its vertices? (a) Suppose a graph has a Hamilton path. What is the maximum number of vertices of degree one the graph can have? Explain why your answer is correct. (b) Find a graph which does not have a Hamilton path even though no vertex has degree one. Explain why your example works.

Unless it is already a tree, a given graph \(G\) will have multiple spanning trees. How similar or different must these be? (a) Must all spanning trees of a given graph be isomorphic to each other? Explain why or give a counterexample. (b) Must all spanning trees of a given graph have the same number of edges? Explain why or give a counterexample. (c) Must all spanning trees of a graph have the same number of leaves (vertices of degree 1 )? Explain why or give a counterexample.

We often define graph theory concepts using set theory. For example, given a graph \(G=(V, E)\) and a vertex \(v \in V,\) we define $$ N(v)=\\{u \in V:\\{v, u\\} \in E\\} $$ We define \(N[v]=N(v) \cup\\{v\\}\). The goal of this problem is to figure out what all this means. (a) Let \(G\) be the graph with \(V=\\{a, b, c, d, e, f\\}\) and \(E=\\{\\{a, b\\},\\{a, e\\},\\{b, c\\},\\{b, e\\},\\{c, d\\},\\{c, f\\},\\{d, f\\},\\{e, f\\}\\} .\) Find \(N(a), N[a], N(c),\) and \(N[c]\) (b) What is the largest and smallest possible values for \(|N(v)|\) and \(|N[v]|\) for the graph in part (a)? Explain. (c) Give an example of a graph \(G=(V, E)\) (probably different than the one above) for which \(N[v]=V\) for some vertex \(v \in V\). Is there a graph for which \(N[v]=V\) for all \(v \in V ?\) Explain. (d) Give an example of a graph \(G=(V, E)\) for which \(N(v)=\emptyset\) for some \(v \in V\). Is there an example of such a graph for which \(N[u]=V\) for some other \(u \in V\) as well? Explain.

Prove that if you color every edge of \(K_{6}\) either red or blue, you are guaranteed a monochromatic triangle (that is, an all red or an all blue triangle).

Give an example of a graph that has exactly 7 different spanning trees. Note, it is acceptable for some or all of these spanning trees to be isomorphic.