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
CombinatoricsOperations Research·Captain: mikedeng1

An Introduction to Timetabling 2: When Every Teacher Is Available in at Most Two Periods, Limited Backtracking Finds a Timetable or Correctly Reports That None ExistsResearch Paper

School and university timetabling is one of the oldest applications of combinatorial optimization. In the class–teacher model, classes and teachers must be brought together for a prescribed number of lectures, each lecture occupies one period, and nobody can be in two places at once. With no further side constraints the model reduces to edge colouring of a…

16 thms4 active users
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Edge-Disjoint Spanning Trees of Finite Graphs: A Finite Multigraph Has k Edge-Disjoint Spanning Trees iff Every Partition P of Its Vertices Is Crossed by at Least k(|P| − 1) EdgesResearch Paper

A connected network survives the failure of any single link exactly when it has no bridge, but a stronger and more useful property is to carry several edge-disjoint spanning trees: each tree can broadcast to every node on its own, so kkk such trees give kkk independent routing or broadcast structures, and the network stays connected after any k−1k-1k−1 link failures.…

15 thms4 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research+1·Captain: mikedeng1

The Geometry of Graphs and Some of Its Algorithmic Applications 1: Every Multicommodity Flow Network with k Source-Sink Pairs Has a Cut S with Cap(S)/Dem(S) ≤ O(log k) · maxflowResearch Paper

Routing several commodities through one capacitated network at the same time is a basic problem of network optimization, with applications to communication networks, VLSI layout and divide-and-conquer graph algorithms. Its optimum is the value of a linear program, but the natural certificates of an upper bound are combinatorial: every cut of the network…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsComputational GeometryDiscrete Geometry·Captain: mikedeng1

A Combinatorial Theorem in Plane Geometry: Every n-Triangulation Can Be Partitioned into at Most ⌊n/3⌋ FansResearch Paper

In a conversation reported by Chvátal, Victor Klee asked for the smallest number f(n)f(n)f(n) such that every region bounded by a simple closed nnn-gon is dominated by f(n)f(n)f(n) points: every point of the region sees one of them along a segment inside the region. In the picturesque language that gave the problem its name, f(n)f(n)f(n) is the number of guards needed to watch any ar…

7 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Matching, Euler Tours and the Chinese Postman IV: Every Connected, Even, Symmetric Mixed Graph Has an Euler TourResearch Paper

A postman, a snowplough or a street sweeper must traverse every street of a district and return to the depot. When some streets are one-way, the street network is a mixed graph: some edges are directed and must be traversed in a prescribed direction, the others are undirected and may be traversed either way. The first question about such a route is whether…

7 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Paths, Trees, and Flowers I: Matching-Duality Theorem — the Maximum Cardinality of a Matching Equals the Minimum Capacity-Sum of an Odd-Set CoverResearch Paper

A matching in a graph is a set of edges no two of which share a vertex. Finding a matching of maximum cardinality is one of the basic problems of combinatorial optimization: it models pairing tasks (workers to shifts, kidney donors to recipients, players to rounds), it is a subroutine of algorithms for the travelling salesman and Chinese postman problems,…

16 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

The Complexity of Markov Decision Processes III: The Optimal Discounted Cost of a Deterministic Process Is the Least Discounted Cost of a SigmaResearch Paper

A Markov decision process with finitely many states and decisions, a discount factor β∈(0,1)\beta\in(0,1)β∈(0,1) and the objective of minimizing expected discounted cost is the basic model of sequential decision making in operations research and reinforcement learning. It is solvable in polynomial time by linear programming. Papadimitriou and Tsitsiklis (Math. Oper. Res.…

7 thms4 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Send-and-Split Method for Minimum-Concave-Cost Network Flows II: Subproblem Minimum Costs Are the Greatest Solution of the Send-and-Split Equations, Unique if Circulations Cost Positively (Theorem 2)Research Paper

Many network-design and production-planning problems ask for a cheapest way to route a commodity from supply points to demand points when the cost of an arc grows less than proportionally with the amount sent: setup charges, economies of scale, and fixed-plus-linear costs all give concave arc costs. Minimizing a concave function over the flow polytope is…

15 thms4 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: mikedeng1

The Chromatic Number of Random Graphs: For Fixed 0 < p < 1, Almost Every G(n,p) Has n/s₀ ≤ χ(G) ≤ (n/s₀)(1 + 3 log log n / log n), where s₀ ≈ 2 log_d n and d = 1/(1−p)Research Paper

The chromatic number χ(G)\chi(G)χ(G) of a graph is the least number of colours in a proper vertex colouring. Determining it for a typical graph was, in the words of the paper, "one of the best known and most studied unsolved problems in the theory of random graphs". For the dense random graph Gn,pG_{n,p}Gn,p​ with fixed edge probability ppp, the clique number had been known…

15 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

On the Graph Structure of Convex Polyhedra in n-Space II: Whitney's Theorem, a Graph Is n-Tuply Connected iff Any Two Points Are Joined by n Disjoint PathsResearch Paper

Vertex connectivity measures how robust a network is against the failure of nodes. It can be measured in two ways that look different. One way counts the fewest nodes whose removal disconnects the network. The other counts the routes between two nodes that share no intermediate node. Whitney's theorem (1932) says that the two measures agree for every pair…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsLinear algebraTheoretical Computer Science·Captain: mikedeng1

Explicit Expanders of Every Degree and Size 2: Attaching New Vertices to a (p+1)-Regular Ramanujan Graph and Adding Loops Keeps Every Nontrivial Eigenvalue at Most √(2(p+1)) + √p + o(1)Research Paper

Sparse graphs whose adjacency spectrum is concentrated near zero, expanders, are used throughout theoretical computer science: in error-correcting codes, derandomization, sorting and routing networks, and the construction of pseudorandom objects (Hoory, Linial and Wigderson, survey). The best possible spectral expansion for a ddd-regular graph is governed by…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Maximal Flow Through a Network II: In an ab-Planar Network Some Chain from Source to Sink Meets Every Cut Exactly OnceResearch Paper

The maximum flow problem asks how much of a commodity can be shipped from a source to a sink through a network whose arcs have limited capacities. L. R. Ford, Jr. and D. R. Fulkerson's 1956 paper Maximal Flow Through a Network proved the minimal cut theorem: the largest flow value equals the smallest total capacity of a set of arcs that separates source…

10 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Maximal Flow Through a Network I: The Minimal Cut Theorem — the Maximal Flow Value Equals the Minimum Value of a Disconnecting SetResearch Paper

The question behind this mission was posed by T. E. Harris to L. R. Ford, Jr. and D. R. Fulkerson at RAND, in the setting of rail transport: given a rail network linking two cities, with a capacity on every link, find the largest steady flow from one city to the other. Ford and Fulkerson's answer, the minimal cut theorem, published in the Canadian Journal…

13 thms4 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research+1·Captain: mikedeng1

Maximum Matching and a Polyhedron With 0,1-Vertices: The Vertices of the Matching Polyhedron Are Exactly the Matching VectorsResearch Paper

A matching in a graph is a set of edges no two of which share a node. Given a real weight on every edge, the maximum-weight matching problem asks for a matching of largest total weight. It is one of the basic problems of combinatorial optimization: assignment, pairing and scheduling problems reduce to it, and it is the standard example of a combinatorial…

13 thms4 active usersReviewed
CombinatoricsOperations Research·Captain: mikedeng1

The Strong Perfect Graph Theorem I: A Graph Is Perfect If and Only If It Is BergeResearch Paper

A perfect graph is one whose coloring problem has a particularly sharp answer on every induced subgraph: the fewest colors needed is exactly the size of its largest clique. This makes a local obstruction, a clique, certify the optimum number of colors throughout the graph. Claude Berge proposed in 1961 that perfection could be recognized by the absence of…

22 thms4 active usersReviewed
Captain: LG

Hadwiger's ConjectureOpen Problem

Hadwiger's conjecture (1943) asserts that for every integer t≥0t\ge 0t≥0, every graph with no Kt+1K_{t+1}Kt+1​ minor is ttt-colourable. It is a far-reaching strengthening of the four-colour theorem, and it is widely described as one of the central open problems of graph theory (Bollobás, Catlin and Erdős called it "one of the deepest unsolved problems in graph theory"). The…

16 thms4 active usersReviewed
CombinatoricsLinear OptimizationOperations Research·Captain: mikedeng1

The Matroids with the Max-Flow Min-Cut Property: Binary Mengerian Clutters and the Q6 MinorResearch Paper

Several classical theorems of combinatorial optimization say that a family of sets arising from a graph packs: the maximum number of pairwise disjoint members equals the minimum size of a set meeting every member. König's theorem on bipartite graphs, Menger's theorem, the max-flow min-cut theorem of Ford and Fulkerson, Edmonds' branching theorem and the…

30 thms4 active usersReviewed
🏆Completed
Convex OptimizationLinear algebraOperations Research+1·Captain: mikedeng1

Lifts of Convex Sets and Cone Factorizations III: Stable Set Polytopes Have No Small Semidefinite LiftsResearch Paper

Many polytopes of combinatorial optimization have exponentially many facets, yet linear optimization over them is tractable because they are projections of simpler convex sets: affine slices of a nonnegative orthant (linear programming) or of the cone of positive semidefinite matrices (semidefinite programming). The size of such a representation, the number…

19 thms4 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research·Captain: mikedeng1

Cones of Matrices and Set-Functions and 0–1 Optimization II: One Round of N on the Stable Set Polytope Gives Exactly the Odd Hole ConstraintsResearch Paper

The stable set problem (vertex packing) asks for a largest set of pairwise non-adjacent nodes of a graph. It is NP-hard, and its polyhedral study, the description of the stable set polytope STAB(G)\mathrm{STAB}(G)STAB(G) by linear inequalities, is one of the most studied topics of polyhedral combinatorics. Classes of valid inequalities (clique, odd hole, odd antihole,…

13 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems 2: The Augmentation Bound for Maximum-Augmentation PathsResearch Paper

The maximum flow problem asks how much of a commodity can be sent from a source to a sink through a network whose arcs have capacities. It underlies bipartite matching, transportation, scheduling and many reductions in combinatorial optimization. The classical method for it, the labeling method of Ford and Fulkerson (Flows in Networks, 1962), repeatedly…

11 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

An Analysis of Several Heuristics for the Traveling Salesman Problem I: Nearest Neighbor Tours Can Be Far from OptimalResearch Paper

The traveling salesman problem with the triangle inequality asks for a shortest closed tour through nnn points whose distances form a metric. It is NP-hard, so in practice tours are built by fast construction heuristics, and the natural question is how far such a tour can be from optimal in the worst case. Rosenkrantz, Stearns and Lewis (SIAM J. Comput. 6(3),…

12 thms4 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research·Captain: mikedeng1

Optimum Branchings: The Vertices of the Branching Polyhedron Are Exactly the BranchingsResearch Paper

A branching in a directed graph is a set of edges that contains no cycle (even ignoring directions) and in which no two edges point to the same node; a connected branching is an arborescence, a tree rooted at one node with all edges directed away from the root. The optimum branching problem asks, for real weights on the edges, for a branching of maximum…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research·Captain: mikedeng1

On Certain Polytopes Associated with Graphs V: Zero-One Optima of the Odd-Cycle Relaxation on Series-Parallel GraphsResearch Paper

The stable set problem asks for a largest set of pairwise non-adjacent vertices in a graph; its size is the stability number α(G)\alpha(G)α(G). It is NP-hard in general, and a standard way to attack it in integer programming is to write down linear inequalities valid for all stable sets and solve the resulting linear program. The weakest such relaxation uses only…

8 thms4 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

The Design of Competitive Online Algorithms via a Primal-Dual Approach VII: Online Group Steiner TreesTextbook

The group Steiner tree problem generalizes the ordinary Steiner tree problem: given a rooted tree and several groups of vertices, find a minimum-cost subtree that connects at least one vertex of each group to the root. It is a canonical instance of the generalized-connectivity family this survey studies in Chapter 11 — a family that also contains the online…

11 thms4 active usersReviewed
Computational GeometryDiscrete Geometry·Captain: hao jia

Uniform Obstacle Bounds for Planar Graphs (OPG-37357)Open Problem

An obstacle representation turns a graph into a visibility system: vertices are points in the plane, and nonedges are blocked by polygonal obstacles. The obstacle number asks for the minimum number of obstacles needed. OPG-37357 records two different questions for planar graphs. The first asks whether one obstacle can ever be insufficient. The second asks…

6 thms4 active usersReviewed
PreviousPage 5 of 28Next

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