Erdős Problem #151

Erdős Problem #151 (Round 2): a new obstruction via common neighbourhoods

1) ROUND-2 OBJECTIVE

For Problem #151 I pursue path (C): I do not have a full proof or a counterexample, so the correct Round-2 goal is to isolate a sharp structural obstruction that any counterexample would have to satisfy.

Round 1 already proved the general inequality \[ \tau(G)\le n-\alpha(G), \] where $\alpha(G)$ is the independence number. The new Round-2 goal is to add a second, genuinely different mechanism that also forces small clique transversals.

2) Round-1 FOUNDATION USED

I use the following Round-1 facts.

1. The Round-1 lemma \[ \tau(G)\le n-\alpha(G). \]
2. The Round-1 proof that the conjecture holds trivially for triangle-free graphs.
3. The Round-1 observation that the general bound $\tau(G)\le n-\sqrt n$ is easy but much weaker than the target $\tau(G)\le n-H(n)$.

3) NEW INSIGHT / TOOL (ROUND 2)

The new tool is a codegree lemma.

For an edge $uv\in E(G)$, let \[ \mathrm{codeg}(u,v):=|N(u)\cap N(v)|. \] The new observation is that \[ \tau(G)\le n-\mathrm{codeg}(u,v) \] for every edge $uv$.

This is different in nature from the Round-1 bound involving $\alpha(G)$: it uses a dense local configuration (a large common neighbourhood of one edge), not a sparse global configuration (a large independent set).

4) ATTACK PLAN (ROUND 2)

The exact gap after Round 1 was that we only had one broad sufficient condition for the conjecture: \[ \alpha(G)\ge H(n)\quad\Longrightarrow\quad \tau(G)\le n-H(n). \] I will prove a second broad sufficient condition: \[ \exists\, uv\in E(G)\mbox{ with }|N(u)\cap N(v)|\ge H(n) \quad\Longrightarrow\quad \tau(G)\le n-H(n). \]

Combining the two will give a structural obstruction: every counterexample must satisfy simultaneously \[ \alpha(G)<H(n) \quad\mbox{and}\quad |N(u)\cap N(v)|<H(n)\ \mbox{for every edge }uv. \] In particular, every counterexample must also satisfy \[ \omega(G)\le H(n)+1, \] because any clique of size $r$ gives an edge with at least $r-2$ common neighbours.

5) WORK (ROUND 2)

Lemma (common-neighbourhood transversal).

For every graph $G$ on $n$ vertices and every edge $uv\in E(G)$, \[ \tau(G)\le n-|N(u)\cap N(v)|. \]

Proof.

Fix an edge $uv$. Let \[ S:=N(u)\cap N(v), \qquad T:=V(G)\setminus S. \] Then \[ |T|=n-|S|=n-|N(u)\cap N(v)|. \] I claim that $T$ is a clique transversal.

Suppose not. Then there exists a maximal clique $C$ of size at least $2$ with \[ C\cap T=\emptyset. \] So $C\subseteq S=N(u)\cap N(v)$. In particular, every vertex of $C$ is adjacent to $u$. Therefore \[ C\cup\{u\} \] is a clique strictly larger than $C$, contradicting the maximality of $C$.

So $T$ is indeed a clique transversal, and hence \[ \tau(G)\le |T|=n-|N(u)\cap N(v)|. \]

Corollary 1.

If $G$ has an edge $uv$ such that \[ |N(u)\cap N(v)|\ge H(n), \] then \[ \tau(G)\le n-H(n). \]

Proof.

Apply the lemma to that edge.

Corollary 2.

If \[ \max\left\{\alpha(G),\ \max_{uv\in E(G)} |N(u)\cap N(v)|\right\}\ge H(n), \] then \[ \tau(G)\le n-H(n). \]

Proof.

If $\alpha(G)\ge H(n)$, use the Round-1 bound $\tau(G)\le n-\alpha(G)$. Otherwise, if some edge has common neighbourhood size at least $H(n)$, use Corollary 1.

Corollary 3 (clique obstruction).

If $G$ is a counterexample to the conjectured inequality \[ \tau(G)\le n-H(n), \] then \[ \omega(G)\le H(n)+1. \]

Proof.

Suppose $\omega(G)\ge H(n)+2$, and let $K$ be a clique of that size. Pick any edge $uv$ of $K$. Then every vertex of $K\setminus\{u,v\}$ lies in $N(u)\cap N(v)$, so \[ |N(u)\cap N(v)|\ge |K|-2\ge H(n). \] By Corollary 1 the conjectured inequality would then hold, contradiction.

Corollary 4 (triangle-count version).

Let $t(G)$ denote the number of triangles of $G$ and $e(G)$ the number of edges. Then \[ \tau(G)\le n-\left\lceil \frac{3t(G)}{e(G)}\right\rceil \] whenever $e(G)>0$.

Proof.

The average value of $|N(u)\cap N(v)|$ over all edges $uv$ equals \[ \frac{1}{e(G)}\sum_{uv\in E(G)} |N(u)\cap N(v)| = \frac{3t(G)}{e(G)}, \] since each triangle contributes $1$ to the codegree of each of its $3$ edges. Therefore some edge $uv$ satisfies \[ |N(u)\cap N(v)|\ge \left\lceil \frac{3t(G)}{e(G)}\right\rceil. \] Now apply the lemma.

Round-2 structural obstruction.

Combining Round 1 with Corollary 2, any counterexample $G$ on $n$ vertices must satisfy \[ \alpha(G)<H(n) \quad\mbox{and}\quad |N(u)\cap N(v)|<H(n)\ \mbox{for every edge }uv. \] Equivalently, every counterexample must simultaneously have:

1. no independent set of size $H(n)$, and
2. no edge lying in $H(n)$ or more triangles.

This sharply narrows the possible shape of a counterexample.

6) ADVERSARIAL VERIFICATION

I check the possible pitfalls.

1. Why does a clique contained in $N(u)\cap N(v)$ contradict maximality? Because every vertex of that clique is adjacent to $u$, so adjoining $u$ enlarges the clique. There is no need to use both $u$ and $v$.
2. Does the lemma fail for isolated edges or sparse graphs? No. If $N(u)\cap N(v)=\emptyset$, the lemma simply gives the trivial estimate $\tau(G)\le n$.
3. Does Corollary 3 use more than is proved? No. A clique of size $r$ gives an edge with at least $r-2$ common neighbours, and that is exactly what the lemma needs.
4. Is the triangle-count version correct? Yes. Each triangle contributes to the common-neighbour count of exactly its three edges, so the averaging identity is exact.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 does not prove the Erdős--Gallai--Tuza conjecture, but it adds a genuinely new sufficient condition and a sharp obstruction:

1. Round 1 showed the conjecture whenever $\alpha(G)\ge H(n)$.
2. Round 2 now also shows the conjecture whenever some edge has at least $H(n)$ common neighbours.
3. Therefore any counterexample must have both \[ \alpha(G)<H(n) \quad\mbox{and}\quad \max_{uv\in E(G)}|N(u)\cap N(v)|<H(n), \] and in particular \[ \omega(G)\le H(n)+1. \]

This is a real narrowing of the search space for counterexamples and a clear structural advance beyond Round 1.

8) COMPLETION ESTIMATE

COMPLETION: 58%

9) REFERENCES

1. Erdős Problems, Problem #151, checked on 7 March 2026.
2. Erdős Problems, Problem #610 (for the currently recorded general bound $\tau(G)\le n-\sqrt{2n}+O(1)$), checked on 7 March 2026.

Erdős Problem #151: independent continuation

Date: 23 September 2026. Source versions read in full: 151.tex in gpt_pro_5.4.

1) OBJECTIVE AND SOURCE AUDIT

Let $\tau(G)$ hit every maximal clique with at least two vertices, and let $H(n)$ be the minimum independence number among triangle-free $n$-vertex graphs. The target is $\tau(G)\le n-H(n)$. The source codegree bound is correct, but its proof only uses one endpoint: the stronger bound $\tau(G)\le n-\Delta(G)$ follows immediately. The asserted new codegree obstruction is therefore redundant with this simpler bound.

2) WORK: A LOCAL-PLUS-REMOTE CERTIFICATE

For a vertex $v$ put $U=N(v)$, and let $W$ consist of vertices outside $U\cup\{v\}$ which have no neighbour in $U$. Then \[ \tau(G)\le n-|U|-\alpha(G[W]). \tag{1} \] Take an independent set $I\subset W$ of size $\alpha(G[W])$ and set $T=V(G)\setminus(U\cup I)$. There are no edges between $U$ and $I$ and no edges inside $I$. Consequently a clique of size at least two contained in $U\cup I$ must lie entirely in $U$. It extends by adding $v$, so is not maximal in $G$. Thus $T$ is a transversal, proving $1$. The convention excluding singleton cliques is important here.

A computable weaker form is \[ \tau(G)\le n-d(v)-\frac{|W|}{\Delta(G[W])+1}, \] with the last term zero when $W$ is empty. Indeed, greedily select a vertex of $G[W]$ and remove it and its neighbours; at most $\Delta(G[W])+1$ vertices are removed at each step, leaving an independent set of the claimed size (with an integer ceiling if desired).

Hence a counterexample must satisfy, for every $v$, \[ d(v)+\alpha(G[W_v])<H(n), \] as well as $\alpha(G)<H(n)$. This strengthens the supplied local certificate by adding a compatible remote independent set. It is a sufficient condition, not a characterization of all clique transversals.

3) ADVERSARIAL VERIFICATION

One cannot add an arbitrary independent set outside $N(v)$: it may have edges into $N(v)$ and create a maximal clique entirely inside the proposed avoided set. The definition of $W$ is exactly what prevents this failure. In a complete graph $1$ gives $\tau\le1$; with an isolated $v$ it reduces to an independence-based bound. Neither boundary case creates singleton clique obligations excluded by the problem.

7) FINAL AND REFERENCE

UNRESOLVED. The certificate improves on the source codegree argument, but I cannot prove its left side always reaches $H(n)$, or construct a graph violating the full conjecture. The definition of $H(n)$ and the clique convention were checked at https://www.erdosproblems.com/latex/151.

8) COMPLETION ESTIMATE

COMPLETION: 10% This is a subjective estimate of progress toward the entire stated problem, not a probability that the conjecture or an unverified proof is correct.

Erdős Problem #151: Clique transversals and triangle-free independence

FORMAL RESTATEMENT

For a graph $G=(V,E)$, let $\tau(G)$ be the minimum size of a vertex set $T\subseteq V$ such that $T$ meets every maximal clique of $G$ of size at least $2$ (i.e. every inclusion-maximal clique that contains an edge). This is sometimes called the clique transversal number.

Let $H(n)$ be the largest integer such that every triangle-free graph on $n$ vertices has an independent set of size at least $H(n)$ (equivalently, $H(n)=\min\{\alpha(G): |V(G)|=n,\ G\text{ triangle-free}\}$).

The question is whether for every graph $G$ on $n$ vertices, \[ \tau(G)\ \le\ n-H(n). \]

QUICK LITERATURE/CONTEXT CHECK

The Erdős Problems database lists this as a problem of Erdős and Gallai $1988$ and later as Problem 1 in Erdős--Gallai--Tuza $1992$. It notes:

• It is "easy" that $\tau(G)\le n-\sqrt{n}$ for all $n$.
• Erdős--Gallai--Tuza proved a stronger general bound $\tau(G)\le n-\sqrt{2n}+O(1)$.
• If $G$ is triangle-free, then $\tau(G)\le n-H(n)$ holds trivially.

Asymptotically, $H(n)$ is of order $\sqrt{n\log n}$ (connected to the classical Ramsey number $R(3,t)$).

DEFINITIONS / SETUP

• A clique is a set of pairwise adjacent vertices. A clique is maximal if it is not contained in a larger clique.
• A set $T\subseteq V$ is a clique transversal if it meets every maximal clique of size at least $2$.
• $\alpha(G)$ denotes the independence number of $G$ (size of a largest independent set).

KNOWN RESULTS I WILL USE

Lemma lem:indep from Problem #148 (the greedy bound $\alpha(G)\ge N/(\Delta+1)$) will also be used.

MAIN ATTEMPT

1) A complete proof that $\tau(G)\le n-\sqrt{n}$

2) Trivial verification for triangle-free graphs

If $G$ is triangle-free on $n$ vertices then every maximal clique of size at least $2$ is an edge, so a clique transversal is precisely a vertex cover. Since vertex cover size equals $n-\alpha(G)$ for all graphs, we have \[ \tau(G)=n-\alpha(G)\le n-H(n), \] because $\alpha(G)\ge H(n)$ for every triangle-free $G$ by definition of $H(n)$.

3) Small-$n$ computational check (unlabeled graphs up to 7 vertices)

As an additional sanity check, I exhaustively tested the inequality $\tau(G)\le n-H(n)$ over all unlabeled graphs on $n\le 7$ vertices (using the NetworkX graph atlas) by:

• computing $H(n)$ exactly as the minimum $\alpha(G)$ over all triangle-free graphs in the atlas on $n$ vertices;
• computing $\tau(G)$ exactly by brute force over all vertex subsets and checking intersection with all maximal cliques.

The computed values are \[ H(1)=1,\ H(2)=1,\ H(3)=2,\ H(4)=2,\ H(5)=2,\ H(6)=3,\ H(7)=3, \] and the inequality $\tau(G)\le n-H(n)$ held for every graph in the atlas for $n\le 7$.

ADVERSARIAL CHECK

• Proposition Proposition (The "easy" bound) is fully rigorous: the only nontrivial step is showing that a maximal clique contained in $N(v)$ must contain $v$, since otherwise it is extendable by $v$.
• The triangle-free "trivial" case uses the identity $\tau_{\mathrm{VC}}(G)=n-\alpha(G)$ (vertex cover vs. independent set), which holds for all graphs, and the fact that in triangle-free graphs maximal cliques of size $\ge2$ are edges.
• The computational check is limited to $n\le 7$ and is not evidence of asymptotic truth; it is only a consistency check.

FINAL

UNRESOLVED --- PARTIAL PROGRESS.

• Farthest point reached. I proved the general bound $\tau(G)\le n-\sqrt{n}$ with a complete, short argument, and verified $\tau(G)\le n-H(n)$ for all graphs up to $7$ vertices by exhaustive computation.
• Remaining gap. The conjectured bound $\tau(G)\le n-H(n)$ would improve the general theory from a $\sqrt{n}$-scale subtraction to a $\sqrt{n\log n}$-scale subtraction (since $H(n)$ is of order $\sqrt{n\log n}$). No argument here bridges that gap, nor do I provide a counterexample.
• Promising next steps. (i) Try to relate $\tau(G)$ more directly to extremal triangle-free subgraphs or to Ramsey-theoretic obstructions (as suggested by the appearance of $H(n)$). (ii) Search computationally for counterexamples for $n\ge 8$ via SAT/ILP encodings of clique transversals and maximal cliques, to understand whether the conjecture might fail in small order.

COMPLETION: 45%