1. Show that the join of a 3-cycle and a 5-cycle contains no $\displaystyle K_6$ but that every 2-edge coloring yields a monochromatic triangle.

2. Let $\displaystyle G_1$ and $\displaystyle G_2$ be k-critical graphs with exactly one vertex v in common, and let $\displaystyle vv_1$ and $\displaystyle vv_2$ be edges of $\displaystyle G_1$ and $\displaystyle G_2$. Show that the graph $\displaystyle (G_1-vv_1)$ U $\displaystyle (G_2-vv_2) + v_1v_2$ is k-critical.

3. Show that a connected $\displaystyle \alpha$-critical graph has no cut vertices. $\displaystyle \alpha$ is the independence number and a graph is

$\displaystyle \alpha$-critical if $\displaystyle \alpha$(G - e) > $\displaystyle \alpha$(G) for all e in the edge set of G.

Sorry I forgot that little bit of extra instruction before.