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.

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

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.

  • $\begingroup$ Any advice on whether on not this holds would be appreciated. Though I think it works. No? $\endgroup$ – user45793 Nov 15 '12 at 3:28
  • $\begingroup$ The "list" feature keeps relabelling my 2nd case from 2 to 1. :@ $\endgroup$ – user45793 Nov 15 '12 at 3:32
  • $\begingroup$ I've edited your post to fix your list numbering. I find that just bolding the numbers will fix the auto-correction (I agree it's annoying sometimes). $\endgroup$ – EuYu Nov 15 '12 at 3:34
  • $\begingroup$ 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? $\endgroup$ – EuYu Nov 15 '12 at 4:45
  • $\begingroup$ Ya I thought of a better proof while I slept, I'll edit here in a sec $\endgroup$ – user45793 Nov 15 '12 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy