Complete Bipartite Subgraphs and Connected Matchings at $\alpha=2$

Definitions and mathematical statement

Under the customary convention, let $G=(V,E)$ be a finite simple undirected graph, and put $n=|V|$. An independent set is a subset of $V$ containing no adjacent pair, and the independence number is \[ \alpha(G)=\max\{|S|:S\subseteq V\text{ is independent}\}. \] Thus $\alpha(G)=2$ requires an independent pair and excludes independent sets of size three. For positive integers $a,b$, a complete bipartite subgraph $K_{a,b}$ consists of disjoint vertex sets $A,B$ with $|A|=a$, $|B|=b$, and every edge between $A$ and $B$ present in $G$. This uses the usual, noninduced subgraph convention; edges within either part are permitted in the ambient graph. A matching $M\subseteq E$ is a set of edges with pairwise disjoint endpoints, and its size is $|M|$.

Supplied conjectural question. Does there exist an absolute real constant $c>0$ such that, for every positive integer $n$ and every $n$-vertex graph $G$ satisfying $\alpha(G)=2$, both of the following hold?

1. $G$ contains a complete bipartite subgraph $K_{n^c,n^c}$.
2. $G$ contains a connected matching of size $cn$.

The same constant $c$ occurs in both clauses in the supplied statement.

Unresolved qualifications. The source record does not define "connected matching." Possible meanings include: a matching whose edges lie in one connected component of $G$; a matching for which the subgraph induced by all its endpoints is connected; or a matching such that, for every two distinct matching edges, an edge of $G$ joins an endpoint of one to an endpoint of the other. These conditions differ, and the intended one must be confirmed.

The expressions $K_{n^c,n^c}$ and "size $cn$" require integer conventions. The record does not specify rounding, or whether matching size means equality or a lower bound. It also supplies no sufficiently-large-$n$ qualification or exceptional small orders. Consequently the displayed question preserves the supplied universal wording, but its integer thresholds, boundary conditions, and connectedness requirement remain unresolved; no repaired formulation is asserted here. The finite simple undirected graph convention and the noninduced interpretation of containment also require confirmation from the source.

Short English statement

The supplied question asks whether every graph with independence number exactly two must contain both a complete bipartite subgraph with polynomially large parts and a matching of size proportional to its number of vertices, subject to an unspecified connectedness condition. The record uses one positive constant for both requirements. Connectedness, integer thresholds, and the treatment of small graphs require clarification before this becomes a fully precise conjecture.

Sources

• Local UnsolvedMath registry: supplied complete record for permanent ID $30006146$, source problem code catalogue entry, titled "Complete Bipartite Subgraphs and Connected Matchings at $\alpha=2$." The registry supplies the conjectural wording and labels its status as open. Its statement-status label is corrected_verified; the accompanying verification note reports only repairs to formula delimiters, notation, grammar, and typography, with mathematical content and scope preserved. These are supplied registry assertions, not independent verification.
• Supplied report citation: Graph Theory (2025), Oberwolfach Reports, DOI 10.4171/owr/2025/1, pp. 5--74. https://doi.org/10.4171/owr/2025/1.
• Supplied attribution context: Jacob Fox, "Extremal graph theory methods for forbidden induced subgraphs," joint work with Matija Bucić and Huy Tuan Pham. The supplied original excerpt discusses structural questions for induced $H$-free graphs and introduces two conjectures, but does not reproduce their formulas. No separate proposer is supplied.
• Supplied literature source: "OWR 2025/1, conjectures." https://ems.press/content/serial-article-files/51346.
• Literature assessment dated exactly 2026-08-22: the supplied curation states that the two $\alpha(G)=2$ conjectures concerning large complete bipartite subgraphs and connected matchings remain unresolved, and that related minor results prove neither stated conjecture. This is supplied dated curation derived from the OWR record, not an independently verified literature assessment. The record explicitly calls for independent verification of time-sensitive status and cited claims.