Graph theory questions

**grad444** · November 11th 2008, 11:37 AM

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.

Thread: Graph theory questions

LinkBack

Thread Tools

Display

Graph theory questions

Similar Math Help Forum Discussions

Graph Theory / Chromatic Number of a Complete Graph

(Graph Theory)Prove that graph X is a tree.

Graph Theory: Relationship between maximum degree of a graph and maximal matching

Graph Theory - Size of a Line Graph

Graph Theory Questions

Search Tags