gpt pro 5.2 attempt on Math-6007

A critical vertex, edge, or set of edges, is one whose deletion lowers the chromatic number. Let $k\geq 4$ and $r\geq 1$. Must there exist a graph $G$ with chromatic number $k$ such that every vertex is critical, yet every critical set of edges has size $>r$? A graph $G$ with chromatic number $k$ in which every vertex is critical is called $k$-vertex-critical. This was conjectured by Dirac in 1970 for $k\geq 4$ and $r=1$. Dirac's conjecture was proved, for $k=5$, by Brown [Br92]. Lattanzio [La02] proved there exist such graphs for all $k$ such that $k-1$ is not prime. Independently, Jensen [Je02] gave an alternative construction for all $k\geq 5$. The case $k=4$ and $r=1$ remains open. Martinsson and Steiner [MaSt25] proved this is true for every $r\geq 1$ if $k$ is sufficiently large, depending on $r$. Skottova and Steiner [SkSt25] have improved this, proving that such graphs exist for all $k\geq 5$ and $r\geq 1$. The only remaining open case is $k=4$ (even the case $k=4$ and $r=1$ remains open). Erdős also asked a stronger quantitative form of this question: let $f_k(n)$ denote the largest $r\geq 1$ such that there exists a $k$-vertex-critical graph on $n$ vertices such that no set of at most $r$ edges is critical. He then asks whether $f_k(n)\to \infty$ as $n\to \infty$. Skottova and Steiner [SkSt25] have proved this for $k\geq 5$, establishing the bounds\[n^{1/3}\ll_k f_k(n) \ll_k \frac{n}{(\log n)^C}\]for all $k\geq 5$, where $C>0$ is an absolute constant. This is Problem 91 in the graph problems collection. See also [917] and [1032] . References [Br92] Brown, Jason I., A vertex critical graph without critical edges . Discrete Math. $1992$, 99--101. [Je02] Jensen, Tommy R., Dense critical and vertex-critical graphs . Discrete Math. $2002$, 63--84. [La02] Lattanzio, John J., A note on a conjecture of {D}irac . Discrete Math. $2002$, 323--330. [MaSt25] Martinsson, Anders and Steiner, Raphael, Vertex-critical graphs far from edge-criticality . Combin. Probab. Comput. $2025$, 151--157. [SkSt25] E. Skottova and R. Steiner, Critical edge sets in vertex-critical graphs . arXiv:2508.08703 $2025$.

FORMAL RESTATEMENT

All graphs here are finite, simple, undirected. For a graph $G$, let $\chi(G)$ be its chromatic number. A vertex $v$ is critical if $\chi(G-v)<\chi(G)$. An edge set $F\subseteq E(G)$ is critical if $\chi(G-F)<\chi(G)$. Fix integers $k\ge 4$ and $r\ge 1$. Question: Does there exist a graph $G$ such that

1. $\chi(G)=k$,
2. every vertex is critical (equivalently, $G$ is $k$-vertex-critical), and
3. every critical edge set $F$ has size $|F|>r$?

A quantitative variant defines $f_k(n)$ as the largest $r$ such that there exists a $k$-vertex-critical graph $G$ on $n$ vertices with no critical edge set of size $\le r$, and asks whether $f_k(n)\to\infty$ as $n\to\infty$.

QUICK LITERATURE/CONTEXT CHECK

I do not use external results beyond what is in the problem text. The problem text states that for $k\ge 5$ and any $r\ge 1$, such graphs exist, and that $k=4$ remains the only open case (including $r=1$).

ATTACK PLAN

Proof-track ideas (for $k=4$).

• Derive necessary structural constraints for a hypothetical $4$-vertex-critical graph with no small critical edge sets (connectivity, minimum degree, edge cuts), then attempt to show those constraints are incompatible.
• Try to adapt known $k\ge 5$ constructions (mentioned in the text) down to $k=4$ by replacing gadgets and maintaining $4$-criticality.

Disproof-track ideas.

• For $k=4$, attempt to show every $4$-vertex-critical graph has a critical edge (Dirac's conjecture at $(k,r)=(4,1)$); even a proof for restricted families (planar, triangle-free, bounded degree) would be progress.
• Computational search in known families (wheels, Mycielski graphs, Hajós joins) to see whether critical edges persist.

WORK

Fast reality check (explicit computation on standard families).

Using a brute-force exact chromatic-number checker (backtracking) I verified:

• $K_4$ is $4$-vertex-critical and has critical edges (indeed every edge is critical).
• Odd wheels $W_n$ (wheel on $n$ vertices with $n-1$ an odd cycle, i.e. $n$ even) are $4$-chromatic and $4$-vertex-critical for $n\in\{6,8,10,12\}$; each has a critical edge (minimum critical edge-set size $=1$).
• The Mycielski graph of $C_5$ (11 vertices, 4-chromatic and triangle-free) is $4$-vertex-critical and has a critical edge (minimum critical edge-set size $=1$).

These checks only test a few explicit families; they do not address the open case.

Lemma 944.1 (minimum degree in $k$-vertex-critical graphs).

If $G$ is $k$-vertex-critical (i.e. $\chi(G)=k$ and $\chi(G-v)=k-1$ for all $v\in V(G)$), then \[ \delta(G)\ge k-1. \]

Proof. Assume for contradiction that $G$ has a vertex $v$ with degree $d(v)\le k-2$. Since $G$ is $k$-vertex-critical, $G-v$ is $(k-1)$-colorable; fix a proper coloring of $G-v$ with colors $\{1,\dots,k-1\}$. The neighbors of $v$ use at most $d(v)\le k-2$ colors among these $k-1$ colors, so there exists a color $c\in\{1,\dots,k-1\}$ not used on $N(v)$. Assign color $c$ to $v$. This extends the coloring to a proper $(k-1)$-coloring of $G$, contradicting $\chi(G)=k$. $\Box$

Lemma 944.2 ($k$-vertex-critical graphs are 2-connected).

If $G$ is $k$-vertex-critical, then $G$ has no cut-vertex (i.e. $G$ is 2-connected).

Proof. Assume for contradiction that $v$ is a cut-vertex. Then $G-v$ has at least two connected components; pick a partition of $V(G)\setminus\{v\}$ into nonempty sets $A,B$ such that there are no edges between $A$ and $B$ in $G-v$. Let $G_A$ be the induced subgraph on $A\cup\{v\}$ and $G_B$ the induced subgraph on $B\cup\{v\}$.

Claim: $\chi(G_A)\le k-1$ and $\chi(G_B)\le k-1$. Indeed, if $\chi(G_A)=k$, then for any $x\in B$ the graph $G-x$ still contains $G_A$ as a subgraph, so $\chi(G-x)\ge \chi(G_A)=k$. This contradicts $k$-vertex-criticality, which gives $\chi(G-x)=k-1$. The same argument applies to $G_B$.

Now fix proper $(k-1)$-colorings $\varphi_A$ of $G_A$ and $\varphi_B$ of $G_B$. Let the color of $v$ under $\varphi_A$ be $c_A\in\{1,\dots,k-1\}$ and under $\varphi_B$ be $c_B$. If $c_A\ne c_B$, permute the color names in $\varphi_B$ by a bijection of $\{1,\dots,k-1\}$ sending $c_B$ to $c_A$; this yields another proper coloring of $G_B$ in which $v$ has color $c_A$. Now the two colorings agree on $v$, so together they define a proper $(k-1)$-coloring of all of $G$ (there are no edges between $A$ and $B$). This contradicts $\chi(G)=k$. $\Box$

VERIFICATION

• Lemma 944.1: checked that the extension step is valid because only neighbors of $v$ can conflict with $v$'s color.
• Lemma 944.2: checked the key claim: if a subgraph has chromatic number $k$, deleting a vertex outside that subgraph cannot reduce its chromatic number, so the whole graph still needs $k$ colors.
• Computation sanity: For $K_4$, deleting any edge yields a graph with a $K_3$ plus a pendant vertex adjacent to two vertices, which is 3-colorable; hence each edge is critical.

FINAL

UNRESOLVED (i) Strongest proved partial result: any $k$-vertex-critical graph must satisfy $\delta(G)\ge k-1$ (Lemma 944.1) and be 2-connected (Lemma 944.2). Computations show that standard $4$-vertex-critical families (odd wheels, Mycielski$C5$) do have critical edges. (ii) First gap: resolve the $k=4$ case, even for $r=1$: either construct a $4$-vertex-critical graph with no critical edge, or prove every $4$-vertex-critical graph has a critical edge. (iii) Top 3 next moves:

1. Prove additional necessary structure for a minimal counterexample at $k=4$ (e.g. 3-connectedness, constraints on edge cuts, reducible configurations), then attempt a discharging-style contradiction.
2. Run a targeted computer search in families known to generate all $4$-critical graphs up to a given size (e.g. via Ore/Hajós constructions) and record whether any lacks critical edges.
3. Examine whether $k\ge 5$ constructions from the problem text can be modified to lower chromatic number while preserving the "far from edge-critical" property.

(iv) Minimal counterexample structure: a $4$-vertex-critical graph with no critical edge set of size $\le r$ would likely need to be highly connected (at least 2-connected by Lemma 944.2), with minimum degree at least 3 (Lemma 944.1), and to avoid all obvious reducible gadgets (wheels/Mycielski-type constructions) that introduce critical edges.