Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

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?

share|improve this answer
    
Welcome to MSE! If you feel that you have something new to contribute to an old thread, this is absolutely fine. Similarly to you, someone else might look for an answer later, and will find what you added. For future submissions, you might find this summary of MathJax helpful: meta.math.stackexchange.com/questions/5020/… –  gnometorule Feb 14 '13 at 17:46
    
I was missinng such reference exactly when writing this up! Thanks! –  BoZenKhaa Feb 14 '13 at 18:10
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.