Complexity of Maximizing Initial Odd Ears

Initial odd ears: factor-critical prefixes and a greedy counterexample

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

An ear decomposition starts with a cycle and adds paths whose internal vertices are new and endpoints lie in the previous graph. An odd ear has an odd number of edges; initial odd ears are the consecutive odd ears at the start under the source's convention.

Statement recorded in the supplied source.

What is the computational complexity of determining $\beta(G)$ for a $2$-vertex-connected graph $G$, where $\beta(G)$ is the maximum number of initial odd ears in an ear decomposition? [S2]

Source status.

The supplied catalogue labels this record partially solved. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Classify the difficulty of maximizing the initial odd ears in a decomposition of a two-vertex-connected graph.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30002726 (OWR-13353-012). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Combinatorial Optimization $2015$, Oberwolfach Reports, DOI 10.4171/owr/2014/51, pp. 2873--2932 https://doi.org/10.4171/owr/2014/51.
• S3 Benchetrit--Sebo, ear decompositions https://arxiv.org/abs/1509.05586. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

What is the computational complexity of determining $\beta(G)$ for a $2$-vertex-connected graph $G$, where $\beta(G)$ is the maximum number of initial odd ears in an ear decomposition?

Conventions and proposed route

The source, Sebo's report on printed page 2914, counts an initial odd cycle as the first odd ear and permits later one-edge ears. We use simple finite 2-vertex-connected graphs, and a full open ear decomposition covers every edge. An ear after the cycle has distinct old endpoints and distinct internal vertices outside the old graph. Its parity is the parity of its number of edges. We investigate growing an arbitrary odd cycle by available odd ears.

A necessary matching invariant, with proof.

Every graph obtained from an odd cycle by odd open ears is factor-critical: deleting any one vertex leaves a perfect matching. For an odd cycle, deletion leaves an even path, matched by consecutive pairs. Suppose this is true of $H$, and append the odd path $v_0v_1\cdots v_{2r+1}$, with $v_0,v_{2r+1}$ in $H$ and all other vertices new. If a vertex of $H$ is deleted, match the rest of $H$ and pair the $2r$ internal vertices consecutively. If $v_j$ is deleted and $j$ is odd, pair $v_1,\ldots,v_{j-1}$ consecutively, pair $v_{j+1},\ldots,v_{2r+1}$ consecutively including the old right endpoint, and use a matching of $H-v_{2r+1}$. If $j$ is even, pair $v_0,\ldots,v_{j-1}$ including the left endpoint, pair $v_{j+1},\ldots,v_{2r}$, and match $H-v_0$. All listed blocks have even size and are disjoint. A one-edge ear has no new vertices and preserves every old matching. Induction proves the invariant, including trivial ears.

For any prefix with $b$ ears, $e$ edges and $v$ vertices, \[ b=e-v+1. \] Indeed the initial cycle has $e=v$ and $b=1$; each additional path with $t$ edges introduces $t-1$ vertices and increases the right side by one. Thus maximizing prefix vertex count is not itself the desired objective. The matching invariant by itself also does not justify greedy growth.

A five-vertex obstruction to arbitrary greedy growth

Let $G=K_5-de$ on vertices $a,b,c,d,e$. It is 2-vertex-connected: after deleting a vertex, the remaining graph is complete or complete with one edge removed, and is connected. Start with triangle $abc$. There is no unused edge between its vertices. Any new odd ear must have an even positive number of internal vertices, so must use both $d,e$; they would be consecutive and would require the missing edge $de$. Hence no odd ear can be appended. A greedy procedure committed to this initial cycle stops with a prefix of one. It can complete a full decomposition, for example by the even ears $adb$ and $aeb$, then any still unused edges, but its initial odd prefix remains one.

In contrast, start with triangle $abd$, append the odd ear $aceb$, and then append the three single-edge ears $ae,bc,cd$. These paths use exactly the nine edges of $G$, satisfy all old-endpoint/new-internal requirements, and are all odd. This gives five initial odd ears. The identity above bounds the total number of ears in every full decomposition by exactly $9-5+1=5$. Consequently $\beta(G)=5$, although the first greedy choice stops at one. This checks a concrete obstruction to the proposed inference that any maximal odd prefix is maximum. It is not a hardness reduction for computing $\beta$.

What certificates and exhaustive search do provide.

For a proposed threshold $b$, a full ordered ear decomposition is a polynomial-size certificate for $\beta(G)\ge b$. Its paths together list each edge once, so there are at most $2|E|$ listed endpoint occurrences if trivial and initial-cycle conventions are accounted for by a constant-factor encoding. A verifier marks used vertices and edges, checks the first simple cycle, checks each path and the endpoint/internal restrictions, checks edge coverage, and counts the consecutive initial odd lengths. These operations are polynomial in the input and certificate length. A valid certificate implies the threshold; a witnessing decomposition provides such a certificate in the reverse direction. Thus the threshold language lies in NP under these conventions. Enumerating all finite path lists and checking them computes $\beta$, but gives no polynomial running-time bound. Our failed greedy shortcut was intended to avoid that enumeration, and the explicit graph prevents it.

Source context and model-assisted audit

The primary report discusses the $\beta\le1$ case separately. The Benchetrit--Sebo author abstract, arXiv:1509.05586, inspected on 11 October 2026, reports an efficient test for that case and fixed-parameter tractability for computing $\beta$. Those general algorithms are not rederived here; a fixed- parameter bound is not automatically a polynomial bound when the parameter is unbounded. The matching proof and greedy obstruction above are elementary auxiliary results, with no novelty claim. The audit verified every edge of $K_5-de$, the role of one-edge ears, both internal-deletion parities, and the fact that the initial prefix must be consecutive. No numerical computation or formal proof checking was used for this record.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. The coordinating Codex (GPT-6; exact serving revision not exposed) also provided a separate model-assisted written-proof review of this manuscript. This is not independent human verification. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. The unrestricted computational classification of beta is not determined; the exhibited graph rejects only the arbitrary-start greedy route.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• Oberwolfach Report 51/2014, Combinatorial Optimization; relevant original passages read in the cached primary report on 11 October 2026. https://doi.org/10.4171/owr/2014/51.
• Y. Benchetrit and A. Sebo, Ear-decompositions and the complexity of the matching polytope $2015$; abstract and stated scope inspected, general algorithms not independently checked. https://arxiv.org/abs/1509.05586.

Final status

Unresolved in this attempt. The unrestricted computational classification of beta is not determined; the exhibited graph rejects only the arbitrary-start greedy route.