# Thread: Graph theory questions

1. ## Graph theory questions

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

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

3. Show that a connected $\alpha$-critical graph has no cut vertices. $\alpha$ is the independence number and a graph is
$\alpha$-critical if $\alpha$(G - e) > $\alpha$(G) for all e in the edge set of G.

Sorry I forgot that little bit of extra instruction before.