
Graph theory questions
1. Show that the join of a 3cycle and a 5cycle contains no $\displaystyle K_6$ but that every 2edge coloring yields a monochromatic triangle.
2. Let $\displaystyle G_1$ and $\displaystyle G_2$ be kcritical 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_1vv_1)$ U $\displaystyle (G_2vv_2) + v_1v_2$ is kcritical.
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.