4
$\begingroup$

Show that a k-critical graph is connected. Furthermore, show that it does not have a vertex whose removal disconnects the graph (such a vertex is known as a cut vertex).

I have managed to proove , I think, the first part Let's assume G is not connected. Since χ(G) = k, (If G1,G2,...,Gr are the components of a disconnected graph G, then χ(G) = max χ(Gi) 1≤i≤r ) then there is a component G1 of G such that χ(G1)=k.If v is any vertex of G which is not in G1,then G1 isa component of the subgraph G − v. Therefore, χ (G − v) = χ (G1 ) = k. This contradicts the fact that G is k-critical. Hence G is connected.

But I can't manage to prove the second part..ie that there is not cut vertex. Anyone can help?

2 Answers 2

5

Your statement is a special case of more general theorem I was researching when I came across your question:

T: Cut in a $k$-critical graph is not clique.

Proof: Assume that cut $S$ in $k$-critical graph $G=(V,E)$ is clique. Components of $G \setminus S$ are $\{C_1 \dots C_r\}$. For each subgraph of $G$ in the form of $C_i\cup S$, find total coloring $\phi_i$ with $k-1$ or less colors. Let $\{v_i \dots v_m\}$ be vertices of $S$ that have different colors in the coloring $\phi_i$. Now because $S$ is clique, you can permute the colors on $v_1 \dots v_m$ in such a way that $\phi_i(v_j)=j$. Finally, you unite all the colorings $\phi_1 \dots \phi_r$, thus getting total coloring on $G$ with only $k-1$ colors. This contradicts the $k$-criticality of $G$ and proves the theorem.

Because single vertex is a clique in every graph, your statement is proven.

PS: how is resurrecting of old threads looked upon in these parts?

  • 0
    I was missinng such reference exactly when writing this up! Thanks!2013-02-14
2

Recall that "critical" also means that you cannot remove an edge without reducing the chromatic number of the graph.

If G had a cut vertex you could remove an edge adjacent to that vertex without decreasing $\chi(G)$.

I hope this suffices as a hint.