Please solve and provide proof for problem 3.6 I have attached screenshots for extra information.

Problem 3.6. Find an ordering of the vertices of the bow tie graph from Erample 3.5 that permits you to apply Lemma 3.5 to compute its chromatic polynomial. Example 3.5. Below is an example of joining two copies of C to make a five-vertex graph called the bow tie. D: 11 Lemma 3.4. Suppose that G is a graph with a pendant verter. Suppose H is obtained from G by deleting the pendant verter and its associated edge. Then Xa(m) = (m - 1). XH(m) Proof: this proof is an exercise. Lemma 3.5. Suppose that there is an ordering of the vertices of a graph G so that for each verter v E VG) the set of neighbors of v that come before v in the ordering form the vertices of a complete induced sub-graph (these neighbors have all possible edges between them). Then the chromatic polynomial of G is a product of monomials, one per uerter, with the monomial for a verter v being (m-v) where v is the number of neighbors of v that come before it in the ordering. See Erample 3.4. Proof: Traverse the vertices in order. For each vertex v, since its neighbors that come before it in the order are all adjacent, there will be v colors already used leaving a choice of m - v valid choices for v. Multiplying the successive choices yields the polynomial given in the lemma. O. The preceding lemma is subtle (or confusing) enough to require an example. Example 3.4. Consider the graph, G, below. The vertices have been numbered. Verify that the order has the property required by Lemma 3.5, that the neighbors of each vertex that are before it in the ordering are all adjacent. We now traverse these colorings in order. If m colors are available there are m colors available for vertex 1. Since 2 is adjacent to 1, there are (m-1) colors available for it. Vertices 3-7 will each be adjacent to two vertices that have already been colored when we reach them in the ordering. These two vertices are adjacent, using up 2 colors, and leaving (m-2) choices of colors for each of these vertices. The chromatic polynomial of this graph is thus XG(m) = m(m - 1)(m - 2) Problem 3.6. Find an ordering of the vertices of the bow tie graph from Erample 3.5 that permits you to apply Lemma 3.5 to compute its chromatic polynomial. Example 3.5. Below is an example of joining two copies of C to make a five-vertex graph called the bow tie. D: 11 Lemma 3.4. Suppose that G is a graph with a pendant verter. Suppose H is obtained from G by deleting the pendant verter and its associated edge. Then Xa(m) = (m - 1). XH(m) Proof: this proof is an exercise. Lemma 3.5. Suppose that there is an ordering of the vertices of a graph G so that for each verter v E VG) the set of neighbors of v that come before v in the ordering form the vertices of a complete induced sub-graph (these neighbors have all possible edges between them). Then the chromatic polynomial of G is a product of monomials, one per uerter, with the monomial for a verter v being (m-v) where v is the number of neighbors of v that come before it in the ordering. See Erample 3.4. Proof: Traverse the vertices in order. For each vertex v, since its neighbors that come before it in the order are all adjacent, there will be v colors already used leaving a choice of m - v valid choices for v. Multiplying the successive choices yields the polynomial given in the lemma. O. The preceding lemma is subtle (or confusing) enough to require an example. Example 3.4. Consider the graph, G, below. The vertices have been numbered. Verify that the order has the property required by Lemma 3.5, that the neighbors of each vertex that are before it in the ordering are all adjacent. We now traverse these colorings in order. If m colors are available there are m colors available for vertex 1. Since 2 is adjacent to 1, there are (m-1) colors available for it. Vertices 3-7 will each be adjacent to two vertices that have already been colored when we reach them in the ordering. These two vertices are adjacent, using up 2 colors, and leaving (m-2) choices of colors for each of these vertices. The chromatic polynomial of this graph is thus XG(m) = m(m - 1)(m - 2)