# Bounds on an induced subgraph of a 4-critical graph

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.

• mmm I think I may have gotten it.. – user45793 Nov 15 '12 at 1:38
• If you'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. – EuYu Nov 15 '12 at 2:35

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.
• I'm not too sure I follow your proof, particularly with part 2. What do you mean by "every $S$-lobe would assign the same colours to the vertices of $S$"? Is it not possible for the lobe to be $3$-colourable but for a cut-vertex connected to the lobe to require a fourth colour? – EuYu Nov 15 '12 at 4:45