For every perfect matching $M$, each vertex occurs exactly once, so the feasibility inequalities giveIf a perfect matching $M^{\ast }$ uses only tight edges, equality holds. It therefore attains a lower bound valid for every perfect matching, proving minimum cost. In a bipartite graph this is the weak duality and complementary slackness certificate for the assignment problem. The Hungarian algorithm maintains feasible row and column potentials and seeks a perfect matching among tight edges.

Use four vertices, with lengths $a_{12}=a_{24}=0$, $a_{23}=a_{32}=-1$, and every other non-loop arc of length $100$. The two arcs between $2$ and $3$ form a negative-length cycle in a graph. For $i=1$, $j=4$, $k=3$,The recurrence would give $-2$, by concatenating $1\to 2\to 3$ and $3\to 2\to 4$. That walk repeats $2$, so it is not a simple graph path. Every simple graph path from $1$ to $4$ still has length at least zero, attained by $1\to 2\to 4$. Thusa strict inequality in part (a).

Initialize an $n\times n$ array $d$ with $d_{ii}=0$ and $d_{ij}=a_{ij}$ for $i\ne j$. For $k=1,\dots ,n$, replace every entry in place byThis is the Floyd-Warshall algorithm. At the start of stage $k$, the induction hypothesis is $d_{ij}=u_{ij}^{(k-1)}$. During that stage, row $k$ and column $k$ do not change: $d_{kk}=0$ and no negative cycle can lower it. Hence the operands $d_{ik},d_{kj}$ remain the stage-start values even with in-place updates. Part (b) proves that after the stage every entry is $u_{ij}^{(k)}$. Induction gives all shortest path lengths after stage $n$. The algorithm uses $n^2$ stored lengths and $O(n^3)$ arithmetic operations, with only a fixed number of loop counters beyond the array.

An old shortest graph path is still allowed at stage $k$, so $u_{ij}^{(k)}\le u_{ij}^{(k-1)}$. Concatenating shortest $i$--$k$ and $k$--$j$ paths gives a walk of length $u_{ik}^{(k-1)}+u_{kj}^{(k-1)}$, but it may repeat vertices. Every repeated section is a closed walk. In the absence of negative-length cycles in a graph, each such closed walk has nonnegative length: decompose it into simple cycles. Removing these sections therefore produces an allowed simple graph path of no greater length. This proves the other upper bound. Together with part (a),

Take a shortest allowed simple graph path. If it does not use $k$ as an intermediate vertex, its length is at least $u_{ij}^{(k-1)}$. If it does, simplicity makes $k$ occur only once. Splitting there gives an $i$--$k$ path and a $k$--$j$ path whose intermediate vertices are in $\{1,\dots ,k-1\}$. Their lengths are at least the respective two minima. In either case,For identical endpoints use the usual empty path of length zero.

Take a root $r$ with children $a,b$. Give $a$ the children $c,1$, give $c$ the children $2,3$, and give $b$ the children $4,5$. The root of a tree has degree two, the three vertices $a,b,c$ have degree three, and $1,\dots ,5$ are the five leaves of a graph. There are nine vertices and eight edges, as required by the handshaking lemma and the edge count for a tree.

For a fixed plane embedding, place one dual vertex in each face of a plane graph and draw a dual edge across each original edge, joining its incident faces. These dual edges can be drawn without mutual crossings, so this constructs a plane dual graph. Each original vertex corresponds to a dual face of a plane graph, while each edge gives exactly one dual edge. HenceBridges give dual loops and parallel dual edges are allowed. On the sphere the dual of the resulting embedding is the original embedding, so planarity is preserved in both directions for this dual pair. The geometric dual graph is defined using an embedding; the converse is understood in that setting, rather than as a definition for an arbitrary nonplanar drawing.

The Petersen graph has ten vertices, fifteen edges, and girth five. One way to verify the girth is its description by the two-element subsets of a five-element set, with adjacency meaning disjointness. A triangle would require three pairwise disjoint two-element subsets, which is impossible. Two distinct vertices have at most one common neighbor: the only possible common neighbor is a two-element subset of the complement of their union. Therefore a four-cycle is impossible. A five-cycle exists in its standard pentagon drawing.

If it were a planar graph, part (i) would give $15\le (5/3)(10-2)=40/3$, a contradiction. Thus the Petersen graph is nonplanar. The held source has blank space where its drawing is mentioned; the named graph determines this argument without that missing illustration.

Every facial boundary walk has length at least five. Bridge excursions can repeat an edge, but deleting those excursions leaves a boundary containing a cycle in a graph; the finite girth assumption ensures the graph is not a tree. Thus the shortest-cycle condition still gives the lower bound five even when bridges occur. Summing boundary lengths counts each edge twice, so $5f\le 2m$. Using Euler formula for a connected planar graph,Hence

The claimed endpoint bounds with radius $ϵ$ are false for positive corner perturbations. For example, take $n=3$, $ϵ=1/1000$ and $\delta =9/10<1-ϵ$. The characteristic polynomial isThroughout $|\lambda -1|\le 1/1000$, the absolute value of the sum of its first two terms is below $0.003$, whereas $9/160=0.05625$. Hence this interval contains no root, contradicting the first requested bound. The actual eigenvalues are approximately $1.029144,1.943599,3.027257$, which also violate the last requested bound.

There is a valid real-eigenvalue conclusion with wider endpoint bounds. For $0<ϵ<1/4$ and $\delta <(n-1)/2-ϵ$, the Gershgorin discs from rows have one enlarged component on the left; the Gershgorin discs from columns have one enlarged component on the right. Each has an enlarged radius $r=\delta +ϵ<(n-1)/2$. A small disc that meets the enlarged left disc has index $j$ satisfying $j-1\le r+q<n/2$. A small disc meeting the enlarged right disc satisfies $n-j<n/2$. Thus, when $n=2m$, every disc with index at most $m$ is isolated in the column family and every disc with index at least $m+1$ is isolated in the row family. Their counts give all $n$ eigenvalues, one in each disjoint small disc, so all are real.

When $n=2m+1$, the same argument isolates the first $m$ discs in the column family and the last $m$ in the row family. It accounts for $2m$ real eigenvalues. The one remaining eigenvalue is real by conjugation, and belongs to the central small disc: the enlarged left and right discs are disjoint, and their two components can intersect only within the disc centered at $m+1$. Therefore the valid uniform bounds areThe sharper endpoint radii $ϵ$ hold in part (d) when $\delta =0$, and cannot simply be carried over to the perturbed matrix.

Assume $n\ge 3$, so the corner entry is separate from the superdiagonal. For $A(\delta )$, the row radii areThus every eigenvalue lies in the union ${\bigcup }_{i}D(i,r_i)$. The discs with centers $2,\dots ,n$ remain mutually disjoint. The expanding disc centered at one meets the disc centered at $j$ exactly when $j-1\le \delta +ϵ+r_j$.

Let $I_{\delta }=\{1\}\cup \{j\ge 2:j-1\le \delta +ϵ+r_j\}$. Then the union of discs indexed by $I_{\delta }$ contains exactly $|I_{\delta }|$ eigenvalues; every other disc contains exactly one. Every isolated eigenvalue is real by conjugation and obeys $|\lambda -j|\le r_j$. Once discs merge, the second Gershgorin circle theorem gives a bound and count for their whole component, rather than one eigenvalue per original disc. Eigenvalue branches coming from that component stay in its union, but may no longer be distinguished by individual discs. These statements describe the bounds through all merger thresholds as $\delta$ increases.

The Gershgorin discs of $A^{\mathsf{T}}$ have radii $1/4,q,\dots ,q,ϵ$. They too are disjoint and have one eigenvalue each. The disc centered at $n$ therefore improves the final bound toIt selects the same eigenvalue as before because all other discs lie a fixed positive distance from the disc centered at $n$.

Write $q=1/4+ϵ$ and take $0<ϵ<1/4$, as intended by the small-parameter assumption. The row discs have centers $1,\dots ,n$ and radii $ϵ,q,\dots ,q,1/4$. They are pairwise disjoint because the sum of neighboring radii is below one. The second Gershgorin circle theorem places one eigenvalue in each disc. Since $A$ is real, nonreal eigenvalues occur in conjugate pairs; a disc centered on the real axis would have to contain both members, contradicting its count of one. Thus all eigenvalues are real andAlternatively, a positive diagonal change of basis symmetrizes the tridiagonal matrix, with transformed off-diagonal entries $\sqrt{ϵ}/2$, also proving reality.

The second part of the Gershgorin circle theorem states that if a union of $k$ of the discs is disjoint from every remaining disc, that union contains exactly $k$ eigenvalues, counted with algebraic multiplicity. In particular, a single isolated disc contains precisely one eigenvalue. Connected components of the full union therefore carry the corresponding disc counts.

The Gershgorin circle theorem states that every complex eigenvalue of a square matrix $A$ lies in at least one closed disc $D_i=\{z:|z-a_{ii}|\le {\sum }_{j\ne i}|a_{ij}|\}$. To prove it, take a nonzero eigenvector $v$ for $\lambda$ and choose $i$ with $|v_i|$ maximal. The $i$th row of $Av=\lambda v$ givesDivision by $|v_i|>0$ proves the claim. The proof applies to real and complex matrices alike.

For nodes $0,1$ and $f(x)=e^x$, the cubic Hermite interpolating polynomial isIndeed its values at zero and one are $1,e$, and its derivatives there are also $1,e$. The Hermite interpolation error formula givessince $0\le \xi \le 1$ and $x(1-x)\le 1/4$ on $[0,1]$.

Use the corrected Hermite interpolating polynomial from part (a). The auxiliary function $\phi$ vanishes at all $n+1$ nodes and at the additional point $x$. Its derivative vanishes at all nodes, because both $e^{\prime }(x_i)$ and the derivative of ${\pi }^2$ vanish there. Rolle's theorem between the $n+2$ ordered zeros of $\phi$ gives $n+1$ further, distinct zeros of ${\phi }^{\prime }$. Thus ${\phi }^{\prime }$ has $2n+2$ distinct zeros on the closed interval. The printed phrase that these include $x$ is not generally true; the extra zeros lie in intervals between zeros of $\phi$, and ${\phi }^{\prime }(x)$ need not vanish.

Repeated application of Rolle's theorem gives ${\phi }^{(2n+2)}(\xi )=0$ for some interior $\xi$. Since $h$ has degree at most $2n+1$ and ${\pi }^2$ is monic of degree $2n+2$,Rearranging givesAt an interpolation node, both sides are zero, so the error formula extends to the whole closed interval. The false location claim about one zero is unnecessary for this result.

For $d=p-q$, all $d(x_i)$ and $d^{\prime }(x_i)$ vanish. Between each consecutive pair of nodes, Rolle's theorem gives one additional zero of $d^{\prime }$. Along with the $n+1$ nodal zeros, this supplies $2n+1$ distinct zeros on the closed interval. Since $d^{\prime }$ is a polynomial of degree at most $2n$, it must be the zero polynomial. Thus $d$ is constant, and $d(x_0)=0$ makes it zero. Hence the interpolating polynomial is unique.

The direct zero count includes the two endpoints; its guaranteed interior count before the degree argument is $2n-1$. After $d^{\prime }=0$ is proved, $d^{\prime }$ vanishes at every point of the open interval, so the stronger interior-zero assertion in the source follows as well. Another immediate uniqueness proof is that $d$ has a double zero at every node, so is divisible by ${\prod }_i(x-x_i{)}^2$ of degree $2n+2$, although its own degree is at most $2n+1$.