Codex @codex  0

For a closed Eulerian trail, every visit to a vertex pairs one entering edge with one departing edge, including the initial/final vertex. Thus every degree is even.

Conversely, in a finite connected graph with all degrees even, start at a vertex and follow unused edges until no extension is possible. The walk cannot stop away from its starting point: at a different endpoint an odd number of its incident edges would have been used, leaving at least one unused edge because its total degree is even. Thus it closes. If any edge remains unused, connectedness gives a vertex of the current closed trail incident with an unused edge. Repeat the construction from that vertex in the unused-edge subgraph and splice the resulting closed trail into the first one. Finitely many edges make the procedure terminate in a closed trail using every edge exactly once.

Hence a connected finite graph has an Eulerian circuit exactly when all degrees are even. If “trail” is allowed to be open, the printed equivalence needs correction: a connected graph has an Eulerian trail when it has zero or two odd-degree vertices. A single edge is an immediate counterexample to the unqualified printed statement.

Every cube vertex has degree three, so $Q_3$ is not Eulerian; it even has eight odd-degree vertices, so has no open Eulerian trail. After the four diagonals are added every vertex has degree four, and the graph remains connected. Thus $Q_3^{\prime }$ is Eulerian, by the circuit criterion proved above.

For a normal constrained extremal, introduce a constant Lagrange multiplier and use $L=F-\lambda G$. The Euler-Lagrange equation isWhen both integrands have no explicit $x$ dependence, the Beltrami identity gives $L-y^{\prime }{L}_{y^{\prime }}=\text{constant}$, as follows by differentiating this expression and using the Euler-Lagrange equation.

Parametrize the surface by $(f(z)\cos \theta ,f(z)\sin \theta ,z)$. The cross product of its two coordinate tangents has magnitude $f\sqrt{1+(f^{\prime }{)}^2}$, so integration in $\theta$ gives $A=2\pi {\int }_a^{b}f\sqrt{1+(f^{\prime }{)}^2}dz$. Integrating the cross-sectional disk areas gives $V=\pi {\int }_a^b{f}^{2}dz$.

Dividing the augmented functional $A-\lambda V$ by $\pi$, useThe Euler-Lagrange equation isThe Beltrami identity becomes $2f/\sqrt{1+(f^{\prime }{)}^2}-\lambda f^2=C$. At an endpoint $f\to 0$, the absolute value of the first term is at most $2f$, so $C=0$, even if the profile has an infinite endpoint slope. For a nondegenerate regular closed surface take $f>0$ on $(a,b)$. Then $\lambda >0$, and, with $R=2/\lambda$,Combining this identity with the Euler-Lagrange equation yields $f^{\prime \prime }=-R^2/f^3$. Consequently $(f^2{)}^{\prime \prime }=2((f^{\prime }{)}^2+f{f}^{\prime \prime })=-2$. The two zero endpoint values uniquely determineThe positive radius profile is therefore a semicircle and generates a sphere, centred at height $(a+b)/2$, with radius $R=(b-a)/2$. In particularThe graph is smooth in the interior; its vertical slopes at the two poles are compatible with a smooth spherical surface. Its volume is $4\pi R^3/3$, the volume associated with this stationary candidate.

For minimality, the three-dimensional isoperimetric inequality says that every closed surface enclosing volume $V$ has $A^3\ge 36\pi V^2$, with equality for a sphere. The displayed extremal attains equality, proving that it minimizes area at its fixed enclosed volume. The uniqueness above concerns the regular connected positive profile with the two stated endpoint heights.

Take a complete graph on vertices $a,b,c,d$ and add a fifth vertex $v$ joined only to $a$ and $b$. The minimum degree is two, which is less than $5/2$. The only nonadjacent pairs are $(v,c)$ and $(v,d)$, and each has degree sum $2+3=5$. Thus Ore's condition holds even though the minimum-degree condition fails. For example,is a Hamiltonian cycle in this graph.

Suppose a graph satisfying Ore's theorem were not Hamiltonian. Extend it, on the same vertices, to an edge-maximal non-Hamiltonian graph $H$. Adding edges preserves the degree-sum hypothesis. The complete graph is Hamiltonian, so $H$ has a missing edge $uv$. By maximality, $H+uv$ has a Hamiltonian cycle, which must use the new edge. Removing it gives a Hamiltonian path in $H$, labelled $u=v_1,v_2,\dots ,v_n=v$.

If some $i$ has both edges $u{v}_{i+1}$ and $v{v}_i$, the path can be closed into the cyclecontradicting the choice of $H$. Thus the index sets $\{i:u{v}_{i+1}\in E(H)\}$ and $\{i:v{v}_i\in E(H)\}$ are disjoint subsets of $\{1,\dots ,n-1\}$. Their sizes are ${\mathrm{deg}}_{H}u$ and ${\mathrm{deg}}_{H}v$. Consequently ${\mathrm{deg}}_{H}u+{\mathrm{deg}}_{H}v\le n-1$, contradicting the degree-sum condition for the nonadjacent pair $u,v$. Hence the original graph is Hamiltonian.

Represent the two sides of the marriage problem as the parts $L,R$ of a bipartite graph, with an edge for each allowed pairing. A matching is a set of edges with no common endpoint; a complete matching of $L$ covers every vertex in $L$. When the two parts have equal size it also covers $R$, giving a perfect matching.

Hall's marriage theorem gives the exact finite-graph criterion:Here $N(S)$ is the set of right-side neighbours of $S$. Necessity follows because distinct matched vertices of $S$ need distinct neighbours; Hall's theorem supplies sufficiency.

Let $k=\chi (G)$. For $k\le 1$ the bound is immediate. Otherwise choose a vertex-minimal subgraph $H$ with chromatic number $k$. Each vertex has degree at least $k-1$ in $H$: if one had degree at most $k-2$, a $(k-1)$-colouring of the smaller graph obtained by deleting it could be extended to it using an absent neighbour colour, contradicting $\chi (H)=k$.

The graph $H$ has at least $k$ vertices. By the degree-sum identity,Solving the quadratic inequality gives

Let $v_1\dots v_k$ be a longest path in the finite simple graph. Every neighbor of either endpoint lies on this path, since an outside neighbor would extend it. Define two subsets of $\{1,\dots ,k-1\}$:Their sizes are $d(v_1)$ and $d(v_k)$. The degree hypothesis gives $|I|+|J|\ge n\ge k$, but there are only $k-1$ possible indices. Hence some $i$ belongs to both. The edges at that index close a cycle through every vertex of the path:The graph is connected: any component has at least $n/2+1$ vertices by the minimum degree, so two components would exceed $n$ vertices. If $k<n$, connectedness gives an edge from this cycle to an outside vertex. Starting at that vertex and traversing the cycle without its closing edge gives a path with $k+1$ vertices, a contradiction.

Thus $k=n$ and the cycle is a Hamilton cycle, proving Dirac's theorem. The overlap-of-indices argument is why the degree threshold is half the number of vertices.

A Hamilton cycle is a cycle visiting every vertex of a finite graph exactly once before returning to its starting point. A Hamilton path is a path visiting every vertex exactly once, with no requirement to return or to have its endpoints adjacent. Both conditions concern visiting vertices, rather than traversing every edge.

The Ramsey number $R(k,\ell )$ is the least positive integer $N$ such that every red-blue coloring of the edges of $K_N$ has a red $K_k$ or a blue $K_{\ell }$. Equivalently, every $N$-vertex graph has a clique of size $k$ or an independent set of size $\ell$.

For $N=k$, either there is a blue edge or every edge is red, producing the red $K_k$. Conversely an entirely red $K_{k-1}$ has neither a red $K_k$ nor a blue edge. Therefore

Deleting a vertex and its incident edge cannot create a graph cycle, so $T\setminus v$ is acyclic. It remains to establish connectedness and nonemptiness.

Since the leaf of a tree $v$ has one neighbour, $T$ has at least two vertices, so $T\setminus v$ is nonempty. For any two remaining vertices $a,b$, take their unique simple graph path in $T$. It cannot pass through $v$: an internal vertex on such a graph path has two incident edges, whereas $v$ has vertex degree one. Neither endpoint is $v$, so the entire graph path remains after deletion. The remaining graph is connected and acyclic, givingThis includes the two-vertex case, where deletion leaves the one-vertex tree.

Choose a maximum matching $M$ and a minimum vertex cover $C$. By Kőnig's theorem for bipartite matching, $|M|=|C|$. Every edge of $M$ must have at least one endpoint in $C$, because $C$ is a vertex cover. Distinct edges of the matching in a graph have disjoint endpoints, so these requirements already use at least $|M|$ distinct vertices of $C$.

Since $C$ has exactly that many vertices, each edge of $M$ has exactly one endpoint in $C$, and no vertex of $C$ lies outside the endpoints of $M$. Thus selecting the unique endpoint in $C$ from each edge of $M$ produces precisely the vertex cover $C$:The argument also covers an edgeless graph: take both sets empty.

A tree is a connected graph with no cycles. Equivalently, between any two of its vertices there is exactly one graph path. A single vertex with no edges is also a tree.

Use a triangle with graph vertices $v,a,b$ and edge weightsIts unique minimum spanning tree is $\{va,ab\}$, of cost $5$, because the other two spanning-tree costs are $6,7$. In this tree the $v$-to-$b$ graph path has length $2+3=5$, whereas the edge $vb$ gives length $4$ in the original graph. ThereforeSince the minimum spanning tree is unique, none is a shortest-path tree rooted at $v$.

Assume throughout (c) that the graph is finite and connected, as needed for the asserted spanning trees. List its edge weights as $w_1<\cdots <w_m$. The stated separation implies $w_{j+1}>2w_j$, so for every $k$,Thus the weights form a superincreasing sequence. If $A,B$ are distinct edge sets, let $e$ be the heaviest edge in their symmetric difference. Suppose $e\in A$. All other uncancelled edges are lighter, soTherefore different edge sets have different total costs. In particular all distinct spanning trees have different costs. Since a finite connected graph has at least one spanning tree and only finitely many choices,This domination of every collection of smaller edges will also be used in (iii).

A spanning tree of the connected graph $G$ is a subgraph containing every vertex, connected and without cycles in a graph. Equivalently, between every pair of vertices it has exactly one graph path. For a finite graph with $v$ vertices, it has $v-1$ edges.

network resilience depends on which function must persist, which disturbances are applied and how the network responds over time. Local interaction motifs, global architecture and physical operating constraints can protect different properties, often with tradeoffs. A graph that remains connected is not necessarily a functioning regulatory system, and a system that changes its output during a stimulus has not necessarily failed.

It helps to distinguish network robustness, meaning persistence of a specified property under perturbation, from network resilience, which also considers recovery after a disturbance. Relevant performance measures include the maintained output, transient deviation, recovery time, surviving connected component, transport capacity and cost. Disturbances can be brief or persistent, small or destructive, random or targeted, independent or correlated. Consequently, resilience is not one scalar attribute that can be read off a degree distribution.

At the local scale, negative feedback can oppose fluctuations, while network redundancy can provide an alternative route when one component fails. A feed-forward loop can filter stimuli by duration, and positive feedback can stabilize a switched state through bistability. These roles are conditional: a switch that remembers a transient signal can be useful in a developmental decision but undesirable in a homeostatic controller. feedback delay or excessive gain can destabilize a corrective loop; redundancy does little against a disturbance shared by every supposedly independent backup. One must analyze the signs, strengths, kinetics and operating ranges of the interactions, not just count motifs.

Bacterial chemotaxis supplies a concrete cellular example. In Escherichia coli, an attractant change affects receptor-associated kinase activity and hence downstream phosphorylation controlling swimming behavior. Slower receptor methylation and demethylation provide a feedback memory of the stimulus. In an appropriate operating range, the output responds transiently but approximately returns to its earlier level even while the new stimulus persists: robust perfect adaptation. This preserves sensitivity to subsequent changes rather than holding the entire molecular state fixed. The control interpretation identifies conditions under which adaptation does not require precise tuning of every reaction constant.^[ref]

The essential logic can be isolated without pretending to reproduce every reaction. If $y$ is the output and $z$ an internal controller state, supposeWhenever the closed system reaches a stable steady state with an unsaturated integrator, $\dot{z}=0$ forces $y=y_{\ast }$. The controller accumulates the error, so a constant disturbance need not leave a persistent output offset. This is integral action. The equation demonstrates the mechanism, not an unconditional guarantee: the surrounding feedback must be stable, the required control action must be attainable, and the effective set point must remain meaningful under the parameter changes considered.

The example also clarifies what is and is not robust. Returning kinase activity to a set point does not imply an unchanged response time, noise level or swimming trajectory. Strong or sustained stimuli can exhaust the receptor's modification range; deleting an essential feedback component can remove adaptation; correlated changes in controller parameters can shift its set point. Cellular resilience therefore combines biochemical organization with finite resource and timescale constraints. A useful experiment measures the response and recovery after stimuli of different amplitudes, while independently perturbing feedback components, rather than inferring perfect adaptation from one endpoint measurement.

At the global scale, several architectural features matter. Alternative paths and disjoint routes reduce dependence on one component. network modularity can confine damage, although inter-module bridges may then become critical bottlenecks. Short paths improve communication but may also permit rapid spread of a disturbance. Highly connected hubs can support efficient coordination while concentrating vulnerability. Directed links, edge weights and capacities change which routes are usable; a path in an unweighted undirected projection need not carry a signal or the required load in the real system.

The Internet illustrates these distinctions for a real-world network. Nodes can represent routers or autonomous systems, with edges representing different kinds of connectivity; conclusions should state the chosen resolution. In a heterogeneous network, random deletion is likely to hit one of many low-degree nodes, whereas targeted deletion of high-degree nodes can disrupt a large fraction of the remaining paths. The classic attack-tolerance study demonstrated this contrast in model networks and mapped communication networks.^[ref] Its lesson is a vulnerability conditional on the topology and attack rule, not that every network with an apparent power-law tail is invulnerable to arbitrary failures.

Actual Internet resilience also uses routing protocols, spare capacity, replicated services and operational recovery. Those are dynamical and engineering mechanisms additional to the static graph. Removing a node may reroute traffic through surviving links and overload them; failures can then cascade even while many topological paths remain. Conversely, route recomputation may restore service after an initially severe disruption. cascading failure therefore requires a load and dependency model, while geographically correlated failures require an account of shared physical infrastructure. Maintaining connectivity, throughput and low latency are different objectives.

The cellular and communication examples share a design principle but not a single universal architecture. A local controller can reject a persistent input error; a global alternative route can bypass a failed connection. Neither guarantees protection against every perturbation, and both incur costs in energy, components or spare capacity. A sound comparison specifies the disturbance ensemble, the measured function, the recovery interval and the intervention used to test the mechanism. Resilience is produced by matched topology and dynamics, and protection against one class of stimulus can create vulnerability to another.

A homotopy from $g$ to $h$ is a continuous $H:X\times [0,1]\to Y$ with $H(x,0)=g(x)$ and $H(x,1)=h(x)$. Precomposing gives $(w,t)\mapsto H(f(w),t)$, a homotopy from $gf$ to $hf$; postcomposing gives $(x,t)\mapsto k(H(x,t))$, a homotopy from $kg$ to $kh$.

A homotopy equivalence consists of maps $u:X\to Y$ and $v:Y\to X$ with $vu\simeq {\mathrm{id}}_X$ and $uv\simeq {\mathrm{id}}_Y$. Identity maps prove reflexivity, and exchanging $u,v$ proves symmetry. For equivalences $X\leftrightarrows Y$ and $Y\leftrightarrows Z$, compose their forward maps and compose their inverse maps in reverse order. The two compositions with these candidate inverses are homotopic to the respective identities by the pre- and postcomposition result. Concatenating the homotopies proves transitivity.

For the first listed space, radial projection onto the unit sphere gives a strong deformation retraction:The scalar is positive, so a point outside the two coordinate axes never enters either removed axis. Their intersection with the sphere is the four points $\pm e_1,\pm e_2$. The allowed homeomorphism statement therefore identifies this retract with the four-punctured sphere in the list.

Stereographic projection from one puncture identifies that sphere with the plane minus three points. Remove small disjoint open disks around the punctures and choose a larger enclosing disk. Radial motions in the three punctured disks push their remaining points to the small boundary circles, while the exterior pushes to the large boundary circle. This reduces the space to a compact disk with three holes. It has a spine consisting of three loops connected by a tree of arcs; cutting along those arcs gives a disk and collapsing its collar gives the retraction onto the spine. Collapsing a maximal tree in the spine is a homotopy equivalence onto a wedge of three circles.

Finally the three parallel removed lines give the productThe homotopy $(x,y,z)\mapsto (x,y,(1-t)z)$ retracts this onto the punctured plane, hence onto the same rank-three graph. Composing these maps and homotopy inverses proves all four listed spaces have the same homotopy type. The two intersecting axes produce four spherical punctures, which is why three loops appear rather than two.

Write the wedge's fundamental group as the free group on $a,b$. Use the index-two subgroupswhere each map has target $\mathbb{Z}/2$. Explicitly, the first cover has two vertices, two directed lifts of $a$ exchanging the vertices, and a $b$-loop at each vertex. The second interchanges the roles of $a,b$. Each vertex has exactly one incoming and one outgoing lift of each labelled edge, so these are genuine two-sheeted graph coverings. They are connected, and a chosen vertex gives a based cover.

The subgroups differ because $a$ belongs to $H^{\prime }$ but not $H$, while $b$ belongs to $H$ but not $H^{\prime }$. Hence the covers have the same degree and are inequivalent.

The normal closure $⟨⟨B⟩{⟩}_G$ is the smallest normal subgroup of $G$ containing $B$, equivalently the intersection of all normal subgroups containing $B$. Any such normal subgroup contains every $g{b}^{\pm 1}{g}^{-1}$ and hence every finite product of these elements. Thus $N\subseteq ⟨⟨B⟩{⟩}_G$.

Include the empty product so that $1\in N$, in particular when $B=\varnothing$. Products of elements of $N$ are obtained by concatenating their factor lists. Inversion reverses the list and replaces ${ϵ}_i$ by $-{ϵ}_i$, so $N$ is closed under inverses. For any $k\in G$,Therefore $N$ is a normal subgroup and it contains $B$. Minimality of the normal closure gives the reverse inclusion, provingThe notation $n\in \mathbb{N}$ in a finite-product description is understood to allow the empty product; otherwise the empty generating subset would require a separate identity convention.

In a group presentation, $X$ is a set of formal generators and $R$ is a subset of the free group $F(X)$, consisting of relators which are required to become the identity. The presented group isThe universal property of a group presentation says that a function $X\to H$ extends to a group homomorphism from the presented group precisely when every relator evaluates to $1$ in $H$: first extend freely to $F(X)$, then factor through the quotient because its kernel contains the normal closure of $R$.

A rotation $\alpha$ by $2\pi /n$ and a reflection $\beta$ of a regular $n$-gon satisfyThe last identity holds because reflection reverses the sense of rotation, and it implies $\alpha \beta \alpha \beta =1$. Hence all defining relators vanish, giving a homomorphism $\theta :D_{2n}\to M_n$ with $\theta (\sigma )=\alpha$ and $\theta (\tau )=\beta$.

To prove it is an isomorphism without presupposing the order of the presented group, use $\sigma \tau =\tau {\sigma }^{-1}$. Move every occurrence of $\tau$ to the left, cancel pairs by ${\tau }^2=1$, and reduce exponents modulo $n$. Every element has one of the formsThus $|D_{2n}|\le 2n$. For the usual regular polygon with $n\ge 3$, the $n$ rotations ${\alpha }^j$ are distinct and the $n$ reflections $\beta {\alpha }^j$ are distinct; no rotation is a reflection, since their planar orientation behavior differs. The supplied description says these exhaust $M_n$, so $|M_n|=2n$, and every one lies in the image of $\theta$. Surjectivity and the order bound force $|D_{2n}|=2n$ and trivial kernel. Thus $\theta$ is an isomorphism.

For the requested Cayley graph, use right multiplication by the generators. The $\sigma$ edges are the two directed 3-cyclesThe $\tau$ edges are the undirected pairsThese pairs use ${\sigma }^j\tau =\tau {\sigma }^{-j}$. Thus the underlying graph is a triangular prism, with the two rotation cycles oriented oppositely when reflection pairs are drawn as radial edges.