5
$\begingroup$

I just hate having to come here to ask questions. It's like accepting defeat that you can't solve it yourself.. but I've been trying to solve this for hours and can't find the intuition to solve the problem..

Let be a 4-critical graph having a vertex cut of cardinality 4. Prove that the induced subgraph [] has at most four edges.

Clearly $G[S]$ can't have 6 edges, since then it would be the complete graph on 4 vertices and thus 4-chromatic $\implies$ $G$ not 4-critical. I've been able to show existence of 4-critical graphs that have a vertex cut of cardinality 4 such that the graph induced by the vertex cut has 4 edges. I fail to see why something interesting happens with 5 edges. I've been trying to consider something like: showing that if there are 5 edges, then there exists a 3 colouring of the S-lobes (plural since S is vertex cut, 3 colouring since G is 4-critical) such that they are consistent on S $\implies$ G is 3-colourable.

Insights? Thanks.

  • 0
    If yo$u$'ve managed to answer your own question, it would be great if you could post it as an answer here. I'd also be quite interested in seeing the proof.2012-11-15

1 Answers 1

2

OK. Here it goes.

Let $G$ be a 4-critical graph having a vertex cut $S$ with $|S| = 4$ such that the induced graph, $G[S]$ has 5 edges. Then $G[S]$ is the complete graph on 4 vertices with a single edge deletion. Now since $S$ is a vertex cut $\implies$ there exist multiple $S$-lobes, each of which are proper subgraphs of $G$ and so they are at most 3-chromatic. Since every $S$-lobe contains the 3-cycle in $S$, each $S$-lobe then must be at least 3-chromatic and so each $S$-lobe is 3-chromatic.

Now consider an optimal 3-colouring of each of the $S$-lobes. The colouring of each $S$-lobe must colour the vertices of $S$ the same way (up to relabelling of colours). I.e. use 1 colour on each of the 2 vertices of degree 3, and colour the vertices of degree 2 the remaining colour. But since the colourings of each $S$-lobe agree on $S$, then that wold imply $G$ itself is 3-colourable, which we know to be false.

  • 0
    I think the proof is fine now. Your proof is reminiscent of the proof that a critical graph cannot have a clique cut. Thinking about it now, this seems to be a consequence of the more general fact that a critical graph cannot have a cut set which induces a graph with a unique coloring. Good job!2012-11-15