Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Graph Theory

699 missions · 311 completed

Missions

Open388Completed311All699
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: wurtle

Hardness of finding large independent sets in three-colorable graphsResearch Paper

A graph is three-colorable if its vertices can be colored with three colors so that adjacent vertices get different colors. Deciding three-colorability is NP-complete. The approximate coloring problem asks how much a promise helps: given a graph promised to be three-colorable, can one efficiently find a coloring with a few more colors, or at least a large…

6 thms2 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: wurtle

Constant-factor hardness of directed feedback vertex setResearch Paper

A directed feedback vertex set of a finite digraph GGG is a set FFF of vertices meeting every directed cycle, equivalently one whose removal leaves G−FG-FG−F acyclic; DFVS(G)\mathrm{DFVS}(G)DFVS(G) is the minimum size of such a set. The problem arises wherever cyclic dependencies must be broken — deadlock resolution, circuit testing, scheduling — and a topological order of G−FG-FG−F cert…

4 thms2 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: wurtle

Constant-factor hardness of Min-UnCutResearch Paper

Min-UnCut asks, for a finite simple graph G=(V,E)G=(V,E)G=(V,E), for the minimum number of edges whose deletion makes GGG bipartite. Equivalently, for a bipartition V=S⊔(V∖S)V=S\sqcup(V\setminus S)V=S⊔(V∖S) let UncutG(S)\mathrm{Uncut}_G(S)UncutG​(S) count the edges with both endpoints on the same side, and set OPTuncut(G)=min⁡SUncutG(S)\mathrm{OPT}_{\mathrm{uncut}}(G)=\min_S\mathrm{Uncut}_G(S)OPTuncut​(G)=minS​UncutG​(S). The quantity measures distance from…

3 thms2 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: wurtle

The Factor-Two Hardness Threshold for Vertex CoverResearch Paper

A vertex cover of a graph is a set of vertices meeting every edge; τ(G)\tau(G)τ(G) denotes the minimum size of one. Computing τ(G)\tau(G)τ(G) exactly is NP-hard, but a two-line algorithm — take both endpoints of a maximal matching — always returns a cover of size at most 2τ(G)2\tau(G)2τ(G). Whether any polynomial-time algorithm achieves a fixed factor 2−ε2-\varepsilon2−ε is one of the…

4 thms2 active usersReviewed
🏆Completed
Discrete GeometryTheoretical Computer Science·Captain: wurtle

L1 Embeddings of Graphs of Bounded TreewidthResearch Paper

A finite metric embeds into L1L_1L1​ exactly when it is a nonnegative combination of cut metrics δS(u,v)=∣1S(u)−1S(v)∣\delta_S(u,v)=|\mathbf 1_S(u)-\mathbf 1_S(v)|δS​(u,v)=∣1S​(u)−1S​(v)∣. This makes L1L_1L1​ distortion the right measure for the flow–cut gap: given edge capacities and pairwise demands, the ratio between the sparsest cut value ϕ∗\phi_*ϕ∗​ and the maximum concurrent flow λ∗\lambda_*λ∗​. Linial, London and…

2 thms2 active usersReviewed
🏆Completed
Discrete GeometryTheoretical Computer Science·Captain: wurtle

Planar Graph Metrics Embed into L1 with Constant DistortionResearch Paper

A finite metric space embeds into L1L_1L1​ exactly when its metric is a nonnegative combination of cut metrics δS(x,y)=∣1S(x)−1S(y)∣\delta_S(x,y)=|\mathbf 1_S(x)-\mathbf 1_S(y)|δS​(x,y)=∣1S​(x)−1S​(y)∣. For this reason the least distortion with which a graph metric embeds into L1L_1L1​ governs the gap between multicommodity flow and sparsest cut: Linial, London and Rabinovich (1995) and Aumann and Rabani (1998)…

4 thms2 active usersReviewed
🏆Completed
OptimizationStatistics·Captain: mikedeng1

Random Graphs with a Given Degree Sequence 1: The Fixed-Point Iteration x ↦ φ(x) Converges Geometrically to the Unique β-Model MLE, and Diverges When No MLE ExistsResearch Paper

The β\betaβ-model is the simplest exponential random graph model in which every vertex has its own parameter. It was studied by Holland and Leinhardt (1981) in the directed case and by Park and Newman (2004) and Blitzstein and Diaconis (2011) in the undirected case, and it is a close relative of the Bradley–Terry model for paired comparisons. Its sufficient…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

On Metric Generators of Graphs 3: A Connected Minimum T-Join Exists Exactly When μ_G|T Is a Tree Metric Whose Minimal Realization Is a T′-Join Embedding Isometrically in GResearch Paper

A TTT-join of a graph GGG is a set of edges FFF such that exactly the vertices of a prescribed even set TTT have odd degree in FFF. Minimum TTT-joins are a classical object of combinatorial optimization: they contain shortest paths (∣T∣=2|T|=2∣T∣=2), Chinese postman tours and perfect matchings as special cases, and their duality with TTT-cuts connects them to integral multiflows.…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryOperations Research·Captain: mikedeng1

On Metric Generators of Graphs 2: The Gadget Graph of a 3-Dimensional Matching Instance Has a Minimum T-Join With at Most q Components Exactly When a Matching ExistsResearch Paper

Let GGG be a connected graph and TTT a set of vertices of even cardinality. A TTT-join is a set of edges FFF in which exactly the vertices of TTT have odd degree. A TTT-cut is a cut δ(X)\delta(X)δ(X) with ∣X∩T∣|X\cap T|∣X∩T∣ odd. Write τ(G,T)\tau(G,T)τ(G,T) for the minimum size of a TTT-join and ν(G,T)\nu(G,T)ν(G,T) for the maximum number of pairwise disjoint TTT-cuts. Every TTT-cut meets every TTT-join, so …

8 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research+1·Captain: mikedeng1

Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal 2: Under Lower and Upper Degree Bounds, Iterative Rounding Finds a Connecting Tree of LP Cost within A_v − 1 and B_v + 1Research Paper

Network design problems often ask for a cheap spanning tree in which no vertex is overloaded: in multicast and overlay networks the degree of a node bounds the number of copies it must forward, and in physical networks it bounds the number of ports. The minimum bounded degree spanning tree problem asks for a minimum-cost spanning tree whose degrees respect…

12 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research+1·Captain: mikedeng1

Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal 1: Iterative Rounding Finds a Spanning Tree of Cost at Most the LP Optimum with Every Degree at Most B_v + 1Research Paper

A network designer may need a cheap connection that keeps the number of links at each site within a local capacity. The minimum bounded-degree spanning tree problem asks for the cheapest spanning tree of a weighted, undirected graph whose vertex degrees respect prescribed upper bounds. The capacity constraints matter in settings where a low-cost tree alone…

8 thms2 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms V: On a 3-Regular c-Expander the Uniform Max-Flow Is at Most 6𝒮/(c(⌊log n⌋ − 2))Research Paper

A multicommodity flow problem asks to route many source–sink demands through one capacitated network at the same time. Its min-cut (sparsest cut) is the smallest ratio, over all cuts, of the capacity crossing the cut to the demand separated by it. Routing is always limited by every cut, so the max-flow never exceeds the min-cut. For a single commodity the…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear algebra·Captain: mikedeng1

Quick Approximation to Matrices and Applications III: The Atoms of a Cut Decomposition with Error εn² Form a 2ε-Pseudo-Regular Partition of a GraphResearch Paper

Szemerédi's regularity lemma partitions the vertex set of any graph into a bounded number of parts between which edges are distributed almost randomly. It is a central tool of extremal graph theory, but the number of parts it needs is a tower of exponentials in 1/ϵ1/\epsilon1/ϵ, which makes it unusable in algorithms. In 1996 and 1999 Frieze and Kannan introduced…

5 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

An Introduction to Timetabling 3: Course Scheduling with Unavailabilities and Preassignments in p Periods Is Equivalent to p-Coloring the Nodes of a GraphResearch Paper

Universities schedule lectures and examinations every term. When students choose their courses freely, with no fixed curriculum, the basic requirement is that no student is asked to attend two lectures at the same time. On top of this come local constraints: a course cannot take place at some periods (its teacher or a suitable room is unavailable), and some…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

A Theorem on Boolean Matrices: Warshall's Construction M* Equals the Boolean Sum M ∨ M² ∨ ⋯ ∨ Mᵈ of the Boolean Powers of MResearch Paper

A finite directed graph on ddd vertices is recorded by its adjacency matrix, a d×dd \times dd×d array of zeros and ones. Many questions about the graph are questions about reachability: can vertex jjj be reached from vertex iii by following one or more edges? In the late 1950s this question arose in the analysis of programs. Prosser (Applications of Boolean matrices to…

5 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Graphs and Cooperation in Games: The Unique Fair Allocation Rule, the Shapley Value of the Graph-Restricted Game, Is Totally Stable for Superadditive GamesResearch Paper

Classical cooperative game theory assumes that any coalition of players can form and coordinate. In many settings cooperation is mediated by pairwise relationships: communication lines, contracts, alliances, or trade links. Roger Myerson's discussion paper Graphs and Cooperation in Games (Northwestern University, 1976; published in Mathematics of Operations…

18 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Zur allgemeinen Kurventheorie I: Menger's Theorem for Finite Graphs, If No Fewer Than n Points Separate Two Finite Sets P and Q, Then n Disjoint Paths Join P to QResearch Paper

Menger's theorem is the oldest of the min–max theorems of combinatorial optimization. It says that the largest number of disjoint paths joining two sets of vertices of a finite graph equals the smallest number of vertices whose removal disconnects them. The max-flow/min-cut theorem of Ford and Fulkerson (1956), the Kőnig–Egerváry theorem on bipartite…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research·Captain: mikedeng1

Integer Programming Formulation of Traveling Salesman Problems: The Miller–Tucker–Zemlin Constraints Exactly Describe the Itineraries with at Most p Cities per TourResearch Paper

The traveling salesman problem asks for a shortest closed route through a set of cities. Writing it as an integer program requires linear constraints whose integer solutions are exactly the routes. The assignment constraints (each city entered once and left once) are not enough: their integer solutions include collections of disjoint cycles, called subtours,…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research+1·Captain: mikedeng1

Approximation Algorithms for Scheduling Unrelated Parallel Machines 1: Binary Search over Rounded LP Vertices Finds a Schedule within Twice the Optimal MakespanResearch Paper

Scheduling unrelated parallel machines to minimize the makespan, written R ∥ Cmax⁡R\,\|\,C_{\max}R∥Cmax​, is one of the basic NP-hard problems of scheduling theory. A set of jobs must each be run on one of several machines, and the time a job takes depends arbitrarily on the machine; the goal is to finish all jobs as early as possible. Before the work formalized here, the…

11 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Approximation Schemes for the Restricted Shortest Path Problem: The Rounding Algorithm Outputs a T-Path of Length at Most (1 + ε)·OPTResearch Paper

The restricted shortest path problem asks for a shortest route between two points of a network subject to a budget on a second additive quantity, such as travel time, cost or risk. It appears as the pricing subproblem of column generation for crew scheduling and vehicle routing, in quality-of-service routing in communication networks, and in scheduling,…

7 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Expected Critical Path Lengths in PERT Networks: With Bundle-Independent Arc Lengths, the Mean-Length Estimate g, Fulkerson's Recursion f and the Expected Critical Path Length e Satisfy g ≤ f ≤ eResearch Paper

PERT (Program Evaluation and Review Technique) and the critical path method model a project as a directed acyclic network whose arcs are jobs and whose nodes are events; the duration of the project is the length of a longest path from the origin to the terminal. When job durations are random, the quantity a planner wants is the expected duration. Computing…

11 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Matching, Euler Tours and the Chinese Postman II: The Parity Problem Is a Minimum 1-Matching of the Odd Nodes under Shortest-Path LengthsResearch Paper

A postal route that must traverse every street and return to its starting point is a Chinese postman tour. In a street network, crossings are nodes, streets are edges, and the cost of a route is the sum of the lengths of the streets it traverses, counted with repetition. The practical question is which streets must be repeated, and how often. Edmonds and…

8 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Matching, Euler Tours and the Chinese Postman III: Next-Node Lists Describe an Euler Tour iff Their Last-Exit Edges Form an ArborescenceResearch Paper

The Chinese postman problem asks for a shortest closed walk in a graph that traverses every edge at least once. Edmonds and Johnson (Math. Programming 5 (1973) 88–124) reduce it to two subproblems: choosing, by matching, which edges to duplicate so that every node has even degree, and then actually finding an Euler tour of the resulting even graph, a closed…

8 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

The Complexity of Markov Decision Processes II: The Optimal Average Cost of a Deterministic Process Is the Least Mean Cost of a Cycle Reachable from the Initial StateResearch Paper

A Markov decision process describes repeated choices whose costs and subsequent states depend on the current state. Such models are used when a decision affects both today's expense and the options available tomorrow. Papadimitriou and Tsitsiklis studied how the computational difficulty of finding an optimal policy changes between stochastic and…

7 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Finding Minimum-Cost Circulations by Successive Approximation I: The Generic Refine Subroutine Stops Within 3n(n − 1) + 3nm + 3n²(m + n) Update Operations at an ε-Optimal CirculationResearch Paper

Minimum-cost circulation asks how to route flow around a directed network without accumulating flow at any vertex, while minimizing the total cost of the routed units. It is a basic network optimization problem: lower-bound and demand constraints in many flow models can be converted into circulation form. Goldberg and Tarjan's 1987 technical report develops…

10 thms2 active usersReviewed
PreviousPage 11 of 13Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me