Applying the recurrence in source item order gives the complete tableAt $(4,7)$ inclusion wins, since $25+D(3,2)=40>D(3,7)=39$. Thus $x_4=1$ and the residual capacity is two. Items three and two are too heavy for it, and item one exactly fits. ConsequentlyIts weight is $2+5=7$. The recurrence proves that no binary selection with capacity seven has greater profit.

Let item $j$ have weight $a_j$ and profit $p_j$. Define $D(j,b)$ as the largest profit obtainable from the first $j$ items with capacity at most the nonnegative integer $b$. Set $D(0,b)=0$. The last item is either absent or present once, giving the dynamic programming recursionThe two alternatives exhaust the feasible binary decisions. In the second alternative, deleting item $j$ leaves exactly the smaller subproblem with capacity $b-a_j$, which proves the recurrence.

Fill rows $j=1,\dots ,4$, and within each row capacities $b=0,\dots ,7$. Store which alternative attains each maximum. Backtrack from $(4,7)$: when exclusion was chosen, set $x_j=0$ and move to $(j-1,b)$; when inclusion was chosen, set $x_j=1$ and move to $(j-1,b-a_j)$. Ties may be resolved either way. Thus the stored values yield an actual optimal selection, not just its objective value.

For $n$ items and capacity $B$, the algorithm uses $O(nB)$ arithmetic operations and $O(nB)$ space with the full backtracking table. It is a pseudo-polynomial algorithm, since $B$ is a numerical capacity rather than its bit length. A value-only version can use one row, but must update capacities in decreasing order to avoid reusing the same item.

For $A\subseteq E$, write $x(A)={\sum }_{e\in A}{x}_e$, and let $\kappa (A)$ count the connected components of $(V,A)$, including isolated vertices. A maximal forest in each component has one fewer edge than vertices, so $r(A)=|V|-\kappa (A)$. The required forest polytope isWe prove both inclusions, using the matroid independence polytope argument explicitly.

If $I$ is a forest, $I\cap A$ is an independent subset of $A$, so $1_I(A)=|I\cap A|\le r(A)$. Its indicator is nonnegative. All convex combinations of these indicators therefore lie in $P$.

For the converse, take any real objective vector $c$. List just its positive-weight edges as $e_1,\dots ,e_k$ with $c_1\ge \cdots \ge c_k>0$, put $c_{k+1}=0$, and set $S_i=\{e_1,\dots ,e_i\}$. Run the forest greedy algorithm on these edges and call the output $I$. At every prefix, the accepted edges form a maximal forest of $(V,S_i)$, soIndeed a previously rejected edge still has its endpoints joined later; therefore no rejected prefix edge can augment the chosen forest. A maximal forest spans every prefix component and has the stated size.

For every $x\in P$, dropping nonpositive objective terms and telescoping now givesThe last equality uses the same telescoping identity for the greedy indicator. If there are no positive coefficients, the empty forest attains the bound zero. Thus every linear objective over $P$ is maximized by a forest indicator.

The singleton inequalities give $0\le x_e\le r(\{e\})\le 1$, so $P$ is compact. The convex hull $Q$ of the finitely many forest indicators is also compact. If some $x\in P$ were outside $Q$, the finite-dimensional separating hyperplane theorem would give $c$ with $c^{T}x>{\max }_{y\in Q}{c}^{T}y$, contradicting the bound just proved. Therefore $P\subseteq Q$, completing the convex-hull proof.

An equivalent system indexed by vertex sets iswhere $E(S)$ contains all edges with both ends in $S$. The rank system implies this since $r(E(S))\le |S|-1$. Conversely, split any edge set $A$ into its vertex components $S_1,\dots ,S_t$. Nonnegativity and the vertex inequalities give $x(A)\le {\sum }_{j}x(E(S_j))\le {\sum }_j(|S_j|-1)=|V|-\kappa (A)$. Hence this second system describes the same polytope.

The associated matroid isThus the graph's edges are the ground set, and the members of $\mathcal{I}$ are its matroid independent sets.

For the specified rank, if $(V,A)$ is a forest, $A$ itself is an allowed choice in the rank maximum, so $r(A)=|A|$. Conversely, if $r(A)=|A|$, some forest $F\subseteq A$ has $|F|=|A|$. Finiteness forces $F=A$, so $(V,A)$ is a forest. Hence the independent sets are exactly all forests in $G$, including the empty forest and forests with isolated vertices.

The matroid independence axioms can also be checked directly. The empty set is a forest, and deleting edges cannot create a cycle. For exchange, let forests $I,J$ have $|I|<|J|$. If every edge of $J$ joined vertices within one component of $(V,I)$, its restriction to each component $S$ would have at most $|S|-1$ edges. Summing would give $|J|\le |I|$, a contradiction. Thus some edge of $J\setminus I$ joins two components of $I$ and can be added without creating a cycle. This proves augmentation and identifies $M$ as the graphic matroid.

On a finite ground set $E$, a submodular rank function is a set function $r:2^E\to \mathbb{R}$ with the following properties:These are normalization, monotonicity, submodularity, and unit integer increments. In particular its values are nonnegative integers with $r(A)\le |A|$. Equivalently, one can require an integer-valued normalized monotone submodular function with $r(\{e\})\le 1$: diminishing returns then bounds every marginal increment by one. A general real-valued submodular function need not be a matroid rank.

Use the maximum-weight version of Kruskal's algorithm: sort the edges by decreasing weight, start with no edges, and add an edge exactly when it joins different current connected components of a graph. For the maximum over all forests, skip negative-weight edges; removing a negative edge always preserves a forest and increases its weight. Zero-weight edges are optional. The matroid greedy algorithm for the graphic matroid proves this procedure optimal; it maximizes over independent sets rather than requiring a full basis.

The positive edges are considered in the orderAdmit $12$ and $15$. Reject $25$, since it closes the triangle on $1,2,5$. Admit $23$. Reject $35$, since $3$ and $5$ are already joined by the path $3,2,1,5$. Skip both negative edges incident with vertex four. ThereforeVertex four is isolated. Requiring a spanning tree would force a negative edge and solve a different optimization problem. With a disjoint-set data structure, sorting dominates the running time, giving $O(|E|\log |E|)$.

Use vertices $1,2,3,4,5$. Reading each symmetric off-diagonal pair once gives the edge setHere $ij$ abbreviates the undirected edge $\{i,j\}$. The diagram displays these seven edges and no loops. The displayed square matrix is an adjacency matrix in the usual terminology: its two indices both label vertices. A vertex-edge incidence matrix would instead have one index for vertices and one for edges. This explains how the source's node-node terminology is being read.

With the new right sides, the dual function isTake $\lambda =\mu =t\to \infty$. Then ${\theta }_{\mathrm{new}}(t,t)=10-t\to -\infty$, so the minimization dual is unbounded below:By weak duality, any feasible integer point with finite objective would have to have objective at most every dual value, which is impossible. Thus the modified integer program is infeasible and has no optimal solution. This is an infeasibility certificate from an unbounded Lagrangian dual.

There is also a direct certificate: the assignment equalities force $(a+b)\cdot x=9$, while the new bounds force it to be at most $3+5=8$. Even the modified linear relaxation is infeasible. The earlier $3.5,5.5$ problem also had no integer solution, but there its fractional feasible point kept the dual value finite.

The assignment equalities parameterize every feasible matrix of the linear programming relaxation asThe side totals and objective becomeThe first side constraint gives $t\le 1/2$ and the second gives $t\ge 1/2$, so the relaxation has the unique feasible pointDirect elimination of the assignment equalities has solved this one-dimensional linear program. Its value matches the Lagrangian dual problem value because the retained assignment polytope is the convex hull of the two integer assignments; it does not make the side-constrained integer problem feasible.

The retained integer assignment constraints have only two feasible matrices,Their $(a\cdot x,b\cdot x,c\cdot x)$ totals are $(4,5,10)$ and $(3,6,8)$ respectively. For nonnegative Lagrange multipliers $\lambda ,\mu$, add $\lambda (3.5-a\cdot x)+\mu (5.5-b\cdot x)$ to the maximization objective. Each feasible point gains a nonnegative amount, so maximizing over the retained assignment set gives an upper bound:The Lagrangian dual problem minimizes this convex piecewise-linear function over $\lambda ,\mu \ge 0$. Put $d=\lambda -\mu$; every real $d$ can occur. The two affine terms average to nine, so their maximum is at least nine, with equality exactly when $d=2$. ThusNeither integer assignment satisfies both side constraints: $D$ violates the $a$ bound and $O$ the $b$ bound. The finite dual bound is therefore not evidence that the integer primal is feasible. The following part shows why this Lagrangian relaxation of an assignment with side constraints has a finite value anyway.

The constraints give the valid upper boundFor example $(x_1,x_2,x_3,x_4)=(0,1,3,4)$ satisfies every constraint: the first left side is four, the next three are three, five and two, and $x_4\ge 1$. Its objective is eight. Hence the upper bound is attained by an integer point, provingAll optimal solutions can also be identified. Equality forces $x_1=0$, $x_3=3$ and $x_2+x_4=5$. The remaining constraints reduce to $x_2\ge 1$ and $x_4\ge 1$. Thus exactly four integer optima occur:This is an optimality certificate by a valid relaxation bound and a feasible integer solution; no assumption of total unimodularity is needed. The source's ${\mathbb{Z}}_{+}$ denotes nonnegative integers, as is also necessary for its assignment equations in the next question.

A totally unimodular matrix has the property that every square submatrix has determinant zero, one or minus one. This includes the one-by-one submatrices, so every entry belongs to $\{0,1,-1\}$.

Its importance is integrality of linear-programming vertices: if $A$ is totally unimodular and $b$ is integral, every vertex of $\{x:Ax\le b,x\ge 0\}$ is integral. Adding rows of the identity preserves total unimodularity. A nonsingular active basis therefore has determinant $\pm 1$ and an integer inverse by the cofactor formula, making its basic solution integral. Thus a finite optimum attained at a vertex of the linear programming relaxation gives an integer optimum without branching.

One sufficient condition is: entries belong to $\{0,1,-1\}$, each column has at most two nonzero entries, and any column with two has one $+1$ and one $-1$. This is the signed column condition for total unimodularity, satisfied by directed vertex-edge incidence matrices. It is sufficient, not necessary.

Write $ij$ for the undirected edge $\{i,j\}$. At the root of the branch and bound search, the minimum spanning tree on $\{2,3,4\}$ is $\{24,34\}$ of cost $6+4=10$. The cheapest edges incident to vertex one are $12,14$, of cost $3+7=10$. The root lower bound is therefore twenty, attained byIt is not a tour: vertex four has degree three and vertex three degree one.

A tour must omit at least one edge from $\{14,24,34\}$, since its degree at vertex four is two. Partition tours according to the first omitted edge in that ordered list. This gives three disjoint, exhaustive children, retaining included and excluded edges when recomputing the one-tree relaxation:

All tours belong to one of the three children, and no remaining child can improve the incumbent. ThereforeThe branching rule is motivated by a violated tour degree equation, rather than by an arbitrary costly edge. This is degree branching with a one-tree bound.

Delete vertex one and its two incident edges from a Hamiltonian cycle. The remaining edges form a Hamiltonian path through all other vertices, hence a spanning tree. Thus every tour is a one-tree, and both problems use the same edge-cost objective. The relaxation enlarges the feasible set, givingConversely, a one-tree in which every vertex has degree two is connected and two-regular, so it is a Hamiltonian cycle. Such a minimum one-tree therefore also solves the travelling-salesman problem. This is the one-tree travelling-salesman bound.

The two pieces of a one-tree can be optimized independently. Compute a minimum spanning tree $F$ on vertices $\{2,\dots ,n\}$ and choose the two cheapest distinct edges incident to vertex one. Return their union.

Every feasible one-tree contains such a spanning tree and such a pair, so its cost is at least the sum of these two independent minima. Their union is itself feasible, attaining that lower bound. This proves optimality.

Use Prim's algorithm for $F$: repeatedly add a cheapest edge crossing from the current tree to an unvisited vertex. The minimum spanning tree cut property makes each chosen edge safe. With the dense weight matrix of a complete graph, maintain the best connection to each unvisited vertex and select the least one by a scan. There are $n-2$ iterations with $O(n)$ work apiece. A further scan finds the two cheapest incident edges. Thus the total complexity is $\boxed{O(n^2)}$, with $O(n)$ additional working storage beyond the input matrix.

Choose a small density threshold $d>0$, then $\epsilon \le \min (d/2,1/4)$ sufficiently small and a lower partition bound $m_0$ sufficiently large thatApply the regularity lemma. Delete all edges incident with $V_0$, all edges within a class $V_i$, all edges between irregular pairs, and all edges between regular pairs of density below $d$. Their total is at mostIf a triangle remains, its vertices lie in three distinct nonexceptional classes, all whose pairs were regular with original density at least $d$. Part (c) then forces at least $(d^3/16)t^3$ triangles in the original graph, where $t$ is the common class size. Since $k\le M$ and $\epsilon \le 1/4$, we have $t\ge n/(2M)$, so this is at least $d^3{n}^3/(128M^3)$.

Choose $c=d^3/(256M^3)$ and take $n_0$ large enough for the regularity lemma. An original graph with at most $c{n}^3$ triangles cannot leave any triangle after these deletions. Thus deleting at most $\eta n^2$ edges makes the graph triangle-free. This is the triangle removal lemma; boundedly many large regular clusters turn any surviving triangle into a positive-density family of original triangles.

Apply part (b) to $(X_1,X_2)$ and $(X_1,X_3)$. Fewer than $2\epsilon |X_1|$ vertices fail at least one of the degree bounds. For any remaining vertex $v$, put $N_2=N(v)\cap X_2$ and $N_3=N(v)\cap X_3$. ThenRegularity of $(X_2,X_3)$ gives $d(N_2,N_3)\ge d-\epsilon \ge d/2$. Every edge between $N_2$ and $N_3$ makes a distinct triangle containing $v$. Hence $v$ belongs to at leastsuch triangles. This proves the asserted bound on exceptional vertices.

There are at least $(1-2\epsilon )|X_1|\ge |X_1|/2$ good vertices. Summing their triangle counts counts each triangle with one vertex in each cluster exactly once, at its $X_1$ vertex. ThereforeThere is no factor of three to divide out in this cross-cluster count.

This is the regular triangle counting lemma with explicit coarse constants.

Let $B\subseteq X$ be the vertices with fewer than $(d/2)|Y|$ neighbours in $Y$. If $|B|\ge \epsilon |X|$, regularity applies to the pair $(B,Y)$ and givesBut averaging the defining strict degree inequality over $B$ gives $d(B,Y)<d/2$, a contradiction. ThereforeRegularity controls the neighbourhood of almost every vertex because a large set of exceptional low-degree vertices would itself witness an irregular density.

For disjoint nonempty sets $X,Y$, let $e(X,Y)$ count edges between them. Their edge density isThe pair is $\epsilon$-regular if every $A\subseteq X$ and $B\subseteq Y$ with $|A|\ge \epsilon |X|$, $|B|\ge \epsilon |Y|$ satisfies $|d(A,B)-d(X,Y)|\le \epsilon$.

An $\epsilon$-regular partition has disjoint classes $V_0,V_1,\dots ,V_k$ covering $V(G)$, with $|V_0|\le \epsilon |V(G)|$, equal positive sizes $|V_1|=\cdots =|V_k|$, and at most $\epsilon k^2$ unordered pairs $(V_i,V_j)$ with $1\le i<j\le k$ that are not $\epsilon$-regular. The set $V_0$ is exceptional and its pairs need not satisfy regularity.

Szemerédi regularity lemma states that for every $\epsilon >0$ and integer $m_0\ge 1$, there are integers $M,n_0$ such that every graph with $n\ge n_0$ vertices has such a partition withThe bounds depend on $\epsilon ,m_0$, not on the graph order. Using a strict regularity inequality or a slightly different constant in the allowed pair count gives an equivalent conventional version; the displayed convention will be used below.

Fix a proper colouring with exactly $k$ nonempty colour classes. For any class $C_i$, suppose every vertex in it misses at least one of the other $k-1$ colours in its neighbourhood. Recolour each of these vertices by one of its missing colours. No edge joins two vertices of $C_i$, so these simultaneous recolourings cannot conflict with one another, and the chosen colours do not conflict with vertices outside $C_i$.

This would eliminate colour $i$ and produce a $(k-1)$-colouring, contradicting optimality. Therefore each colour class contains a vertex adjacent to at least one vertex of every other colour. That vertex has degree at least $k-1$. Choosing one from each class gives $k$ distinct vertices, provingFor $k=1$, a nonempty graph already has a vertex of degree at least zero, so the conclusion holds as well.