Degree-Utility Optimization in Graphs

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$. Specialized notation and index ranges follow the cited source and the definitions below.

$[n]=\{1,\ldots,n\}$ and $d_i$ is the number of edges incident to vertex $i$. The objective assigns a separate scalar utility to each vertex's degree.

Record scope and qualifications.

The catalogue title is retained as metadata. Named certificates, contracts, bounds or frameworks in that title are not asserted as results of the original source extract. The supplied registry flags this extraction as unrecoverable. It is displayed as a literal source fragment; the definitions provide context rather than a replacement formal statement.

Source-record limitation: Source flags the statement as unrecoverable: This record repeats the graph-complexity question represented canonically and with its objective by OWR-16633-017. No separate clean statement is promoted; the original record remains publicly visible and retained for provenance.

Related catalogue records: 30004000. Separate source IDs are preserved for their provenance. The source text below is rendered literally where necessary; damaged formulas and composite extracts are not silently repaired into a new mathematical claim. The supplied catalogue marks this record as unrecoverable. Its extract and terminology are documented, but a complete original problem has not been reconstructed.

Statement recorded in the supplied source.

For graphs, given n,m and vertex functions f_1,

\textbackslash{}

ldots,f_n, what is the complexity of finding an m-edge graph maximizing

\textbackslash{}

sum_{i=1}^n f_i$d\_i$ when the functions are not necessarily identical? [S2]

Source status.

The supplied catalogue labels this source record partially solved; that metadata was checked against the supplied snapshot on 2026-10-11. The label is preserved for provenance and is not an independent verification of present open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

The supplied fragment concerns duplicate Degree-Utility Graph Optimization Problem. Its complete mathematical target is not recovered.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30004001 (OWR-16633-018). Catalogue curation and metadata: CC BY 4.0. The source extract is retained; definitions, English summaries and qualifications are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Combinatorial Optimization $2019$, Oberwolfach Reports, DOI 10.4171/owr/2018/50, pp. 2969--3023 https://doi.org/10.4171/owr/2018/50.
• S3 Optimization over Degree Sequences of Graphs https://arxiv.org/abs/1908.09278.
• S4 Optimization over Degree Sequences https://arxiv.org/abs/1706.03951.
• Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.

Preparation and review.

The original source and UnsolvedMath contributors retain attribution for the source extract. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, scope notes and formatting. No new human mathematical authorship or independently verified solution is asserted. Permanent source ID 30004001 and code OWR-16633-018 checked against the complete supplied registry and current repository. Distinct upstream records, including repeated questions and broad or damaged extracts, are retained for complete coverage of the source CS category. A repeated record is not a new independent conjecture. Complete mathematical-equivalence and current-literature review has not been performed. Related canonical identities: 30004000. Preparation and final review follow contribution prompts C and D, with source gaps disclosed. Structural and rendering checks do not establish a new theorem or open status.

Literature and context check

This is the retained duplicate of the unequal degree-utility question. The original report and the two listed degree-optimization abstracts were consulted. A different failed algorithmic route is investigated here, without presenting the duplicate as a new problem.

Research attempt: Independent degree optimization can choose a nongraphical vector

One might optimize degrees independently subject only to $0\le d_i\le n-1$ and $\sum_i d_i=2m$, then realize the resulting sequence. Those necessary constraints are insufficient. For $n=4,m=3$, the vector $(3,3,0,0)$ satisfies both, yet is not the degree vector of a simple graph: a degree-three vertex must be adjacent to all other vertices, contradicting either vertex of degree zero.

This obstruction can be forced as the unique optimizer of the relaxed utility problem. Give vertices 1 and 2 utility one exactly at degree three and zero at other degrees; give vertices 3 and 4 utility one exactly at degree zero and zero at other degrees. The relaxed vector $(3,3,0,0)$ has objective four, and any different vector loses at least one of the four indicator rewards, so it is uniquely optimal in the relaxation. No graph attains value four by the preceding contradiction.

The exact graph optimum is one. To prove an upper bound, suppose a graph has a degree-three vertex among 1 and 2. All other vertices then have positive degree, so neither zero-degree reward can occur. If both vertices 1 and 2 had degree three, their incident edges would include their common edge and four further distinct edges, at least five edges, impossible with $m=3$. Thus this case yields at most one reward. If neither distinguished vertex has degree three, only vertices 3 and 4 can give rewards. They cannot both be isolated, since the remaining two vertices support at most one simple edge, fewer than three. Again there is at most one reward. A three-edge star centered at vertex 1 gives one reward, proving attainability.

The gap four versus one is not an integrality gap for a claimed sophisticated polyhedral formulation; it belongs to the explicitly weakened degree-sum relaxation. Adding a realization oracle after optimization detects the failure but does not by itself find the best realizable sequence. The first missing algorithmic step is how to enforce joint graphicality while optimizing all unequal utility tables, rather than assuming the handshake constraint is enough.

Verification and adversarial audit

The degree-sum and degree-bound checks are explicit, the relaxed optimum is unique, and the graph optimum is proved by exhausting the reward possibilities. Both the five-edge obstruction and the isolated-pair obstruction use the simple-graph convention.

Audit corrections.

The relaxation is named precisely, and nongraphical degree vectors are not treated as feasible graph certificates. The explicit optimum comparison avoids an unsupported hardness inference.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

The duplicate source target remains unresolved in its full generality. The manuscript supplies an exact counterexample to an independent-degree route, not a complexity classification or a new duplicate conjecture.

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 calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://ems.press/content/serial-article-files/46772 (consulted 2026-10-11).
• https://arxiv.org/abs/1908.09278 (consulted 2026-10-11).
• https://arxiv.org/abs/1706.03951 (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration, repository-format review, and adversarial mathematical review of the written argument; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved as a new research contribution. This is a concrete route investigation, not a claim of new complete resolution or a current-status certification. A known answer reproduced for context does not become a new contribution. The catalogue's source-status label is preserved; this attempt status does not assert that a source-labelled solved question is open.

Research-attempt provenance

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.

$[n]=\{1,\ldots,n\}$ and $d_i$ is the number of edges incident to vertex $i$. The objective assigns a separate scalar utility to each vertex's degree.

Statement recorded in the supplied source.

Given $n,m$ and univariate functions $f_1,\ldots,f_n$, what is the complexity of finding an $m$-edge graph on $[n]$ that maximizes

$$\sum_{i=1}^nf_i(d_i),$$

where $d_i$ is the degree of vertex $i$ and the functions need not be identical? [S2]

Scope qualification.

The graph is taken in the source's simple-graph convention; the representation and evaluation cost of the functions $f_i$ are not specified.

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

Optimize a sum of vertex-dependent degree utilities over graphs with a prescribed edge count.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30004000 (OWR-16633-017). 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 $2019$, Oberwolfach Reports, DOI 10.4171/owr/2018/50, pp. 2969--3023 https://doi.org/10.4171/owr/2018/50.
• S3 Optimization over Degree Sequences of Graphs https://arxiv.org/abs/1908.09278.
• S4 Optimization over Degree Sequences https://arxiv.org/abs/1706.03951. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Preparation and review.

Original question attributed to the cited source and UnsolvedMath contributors. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, source inspection and formatting. No new human mathematical authorship or independent proof verification is asserted. Canonical ID 30004000 and source code OWR-16633-017 checked against the complete supplied registry and existing repository statements; known flagged repetitions and obvious identical conjectures excluded. Full mathematical-equivalence/literature review has not been performed. Statement preparation and final review followed contribution prompts C and D; automated checks verify structure and identity, not open status.

Literature and context check

The report asks about different vertex functions. The consulted 2017/2018 paper abstract treats identical functions and other special cases; the 2019 Deza--Onn abstract explicitly leaves arbitrary functions over complete graphs broadly unresolved there. Those abstracts do not establish a complete present-day classification, and no current-status certification is claimed. Here functions are supplied as finite rational tables on degrees 0 through n-1.

Research attempt: Linear utilities are easy but greedy nonlinear gains can be arbitrarily bad

For the linear subclass $f_i(d)=a_i d+b_i$, the objective for a simple graph $E$ is \[ \sum_i b_i+\sum_{\{i,j\}\in E}(a_i+a_j). \] This follows by counting the contribution $a_i$ once for each edge incident to $i$. Thus, for $0\le m\le\binom n2$, choosing the $m$ largest edge weights $a_i+a_j$ is optimal. If a proposed set omits a larger weight than one it contains, exchanging the two improves the sum; repeating exchanges yields the top-$m$ set. This provides an exact polynomial-time subclass under the stated table/arithmetic model.

A natural attempted extension adds the currently highest marginal-gain edge repeatedly for nonlinear utilities. It can fail by an unbounded factor. Let $n=4,m=2$, set $f_1(0)=f_1(1)=0$, $f_1(2)=M$ for $M>2$, and set $f_i(d)=d$ for $i=2,3,4$. Values at unused degrees can be chosen arbitrarily, for example $f_1(3)=2M$. Initially each edge among vertices 2,3,4 has gain two, while each edge incident to vertex 1 has gain one. After selecting any edge among 2,3,4, every remaining edge among those three still has gain two and every edge incident to 1 still has gain one. The greedy rule therefore chooses two edges avoiding vertex 1 and obtains objective four.

Two distinct edges incident to vertex 1 instead give it degree two and the other vertices total degree two, for objective $M+2$. This is optimal: if vertex 1 has degree zero the value is four; if it has degree one the remaining vertices' degree sum is three, giving value three; if it has degree two the value is $M+2$. These exhaust its possible degrees when $m=2$. The ratio $(M+2)/4$ diverges with $M$, although the integer M has a short binary encoding. Thus local marginal choice does not extend the linear solution, even for a nondecreasing convex table at the distinguished vertex.

Verification and adversarial audit

The greedy choices are forced by strict gain inequalities, not adverse tie-breaking. Every possible degree of vertex 1 is checked to prove the exact optimum, and all graphs are simple with precisely two edges.

Audit corrections.

A bad greedy approximation is not used as a proof of NP-hardness. Results stated in consulted abstracts are not generalized beyond their hypotheses.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

The linear subclass and greedy obstruction do not classify optimization for arbitrary unequal functions. Input representation, general graphicality constraints, and the original full complexity question remain unresolved here.

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 calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://ems.press/content/serial-article-files/46772 (consulted 2026-10-11).
• https://arxiv.org/abs/1908.09278 (consulted 2026-10-11).
• https://arxiv.org/abs/1706.03951 (consulted 2026-10-11).

Model and contributor disclosure

OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration, repository-format review, and adversarial mathematical review of the written argument; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved as a new research contribution. This is a concrete route investigation, not a claim of new complete resolution or a current-status certification. A known answer reproduced for context does not become a new contribution. The catalogue's source-status label is preserved; this attempt status does not assert that a source-labelled solved question is open.