91Ó°ÊÓ

Consider the complete graph \(K_{n}\) for \(n \geq 3\). Color \(r\) of the vertices in \(K_{n}\) red and the remaining \(n-r(=g)\) vertices green. For any two vertices \(v, w\) in \(K_{n}\) color the edge \(\\{v, w\\}\) (1) red if \(v, w\) are both red; (2) green if \(v, w\) are both green; or (3) blue if \(v, w\) have different colors. Assume that \(r \geq g\). a) Show that for \(r=6\) and \(g=3\) (and \(n=9\) ) the total number of red and green edges in \(K_{9}\) equals the number of blue edges in \(K_{9}\). b) Show that the total number of red and green edges in \(K_{n}\) equals the number of blue edges in \(K_{n}\) if and only if \(n=r+g\), where \(g, r\) are consecutive triangular numbers. [The triangular numbers are defined recursively by \(t_{1}=\) \(1, t_{n+1}=t_{n}+(n+1), n \geq 1 ;\) so \(t_{n}=n(n+1) / 2\). Hence \(\left.t_{1}=1, t_{2}=3, t_{3}=6, \ldots\right]\)

a) How many subgraphs \(H=(V, E)\) of \(K_{6}\) satisfy \(|V|=\) \(3 ?\) (If two subgraphs are isomorphic but have different vertex sets, consider them distinct.) b) How many subgraphs \(H=(V, E)\) of \(K_{6}\) satisfy \(|V|=4 ?\) c) How many subgraphs does \(K_{6}\) have? d) For \(n \geq 3\), how many subgraphs does \(K_{n}\) have?

Explain why each of the following polynomials in \(\lambda\) cannot be a chromatic polynomial. a) \(\lambda^{4}-5 \lambda^{3}+7 \lambda^{2}-6 \lambda+3\) b) \(3 \lambda^{3}-4 \lambda^{2}+\lambda\) c) \(\lambda^{4}-3 \lambda^{3}+5 \lambda^{2}-4 \lambda\)

a) For all \(x, y \in \mathbf{Z}^{+}\), prove that \(x^{3} y-x y^{3}\) is even. b) Let \(V=\\{1,2,3, \ldots, 8,9\\} .\) Construct the loop-free undirected graph \(G=(V, E)\) as follows: For \(m, n \in V\), \(m \neq n\), draw the edge \(\\{m, n\\}\) in \(G\) if 5 divides \(m+n\) or \(m-n\) c) Given any three distinct positive integers, prove that there are two of these, say \(x\) and \(y\), where 10 divides \(x^{3} y-x y^{3}\)

For \(n \in \mathbf{Z}^{+}\)where \(n \geq 4\), let \(V^{\prime}=\left\\{v_{1}, v_{2}, v_{3}, \ldots, v_{n-1}\right\\}\) be the vertex set for the complete graph \(K_{n-1}\). Construct the loop-free undirected graph \(H_{n}=(V, E)\) from \(K_{n-1}\) as follows: \(V=V^{\prime} \cup\\{v\\}\), and \(E\) consists of all the edges in \(K_{n-1}\) together with the new edge \(\left\\{v, v_{1}\right\\}\) a) Show that \(H_{n}\) has a Hamilton path but no Hamilton cycle. b) How large is the edge set \(E\) ?

Let \(G\) be a directed graph on \(n\) vertices. If the associated undirected graph for \(G\) is \(K_{n}\), prove that \(\sum_{v \in V}[o d(v)]^{2}=\) \(\sum_{v \in V}[i d(v)]^{2}\)

Let \(G=(V, E)\) be a loop-free connected undirected graph with \(|V| \geq 2\). Prove that \(G\) contains two vertices \(v, w\), where \(\operatorname{deg}(v)=\operatorname{deg}(w)\)