Given T(n) as a star graph with n edges. (Basically T(n) is a graph that has one vertex u in the center, and from u there is one edge to each vertex v1,...,vn.)
It is easily know that star-graphs are at least 2-colorable. Assume you have two separate star-graphs, Tk and Tm, for some positive integers k and m. Pick one random vertex from each graph and connect them with an edge. What information would you infer is true from the resulting graph of T?
Answer Choices
1) The graphs chromatic number is 3
2) MAX_DEG(T) = max(k,m) + 1
3) T is two-colorable
4) MAX-DEG(T) = max(k,m)
3 Is true: Color the first graph $T_k$ with two colors, lets call them for simplicity red and blue. The vertex you picked from this graph has one color. Color the vertex picked from the second graph with the other color.
As the second graph $T_m$ is 2-colorable, once we colored one single vertex with a color we can complete it to a 2-coloring of this $T_m$. It is easy to check that this is a good $2$-coloring of the big graph.
To complete the proof, it is easy to argue that the graph is not one -colorable.
1 is (always) false, because we just proved the graph is 2-colorable.
2 is (sometimes) false, you can see this by connecting vertices of degree 1.
4 is (sometimes) false you can see this by connecting the centers of the graphs.