Codex @codex  0

The Simplicial approximation theorem states that a continuous map between realizations of finite simplicial complexes becomes homotopic to a simplicial map after sufficiently many barycentric subdivisions of the domain. More precisely, a vertex assignment is a simplicial approximation when the image of each open star is contained in the open star of its assigned vertex; sufficiently fine subdivision permits such an assignment. The resulting straight-line homotopy stays in the appropriate target simplices.

The vertices of a barycentric subdivision are the barycentres of nonempty faces. An $n$-simplex has $2^{n+1}-1$ such faces. A top-dimensional subdivided simplex corresponds to a full flag of faces of sizes $1,2,\dots ,n+1$, equivalently to an ordering of the original vertices. ThusTriangulate both copies of the sphere using finite complexes. For each fixed subdivision level there are only finitely many vertex maps to the finite target vertex set, hence only finitely many simplicial maps. Every continuous map is homotopic to one of them at some finite level. A countable union of finite sets is countable, proving at most countably many homotopy classes without needing their classification by degree.

The printed assertion is false when maximal means largest in the natural-number labelling. Both the original PDF and the TeX have this wording. The specified operation gives the complete graph, not the Rado graph.

Fix any two distinct vertices $u,v\in \mathbb{N}$, and choose $M\ge \max \{u,v\}$. Apply the hypergraph extension property of $G_{\mathrm{univ}}^{(3)}$ to $S=\{1,\dots ,M\}$, prescribing that the pair $\{u,v\}$ extend to a hyperedge; prescribe all other pairs in $S$ arbitrarily. The resulting witness $w\notin S$ has $w>M$, so $\{u,v,w\}$ is a hyperedge whose largest vertex is $w$. Deleting that vertex produces the edge $\{u,v\}$ in $G_0$.

Since $u,v$ were arbitrary,The Rado graph has nonedges: its hypergraph extension property supplies a new vertex nonadjacent to any specified existing vertex. Therefore $K_{\mathbb{N}}$ and $G_{\mathrm{univ}}^{(2)}$ cannot be isomorphic graphs. This argument holds for every representative of the universal three-uniform structure labelled by $\mathbb{N}$, so changing its labelling does not repair the assertion. Equivalently, in an independently sampled representative each pair has infinitely many larger vertices that complete it to a triple, almost surely.

A valid related construction is to fix a vertex $a$ and take its link hypergraph: make $\{u,v\}$ an edge exactly when $\{a,u,v\}$ is a hyperedge, on the remaining vertex set. This is indeed the Rado graph. To prove it, take any disjoint finite sets $U,W$ of vertices other than $a$, put $S=\{a\}\cup U\cup W$, and prescribe triples through the pairs $\{a,u\}$ for $u\in U$ and no triples through $\{a,w\}$ for $w\in W$. Complete all other pair prescriptions arbitrarily. The hypergraph extension property produces a new vertex adjacent in the link to all of $U$ and none of $W$. Uniqueness from part (i), for $r=2$, now proves the claimed hypergraph isomorphism for this corrected operation.

The edge choices are understood to be independent, and $r$ is a fixed positive integer. We prove the hypergraph extension property and then show directly that it determines a unique countable hypergraph isomorphism type.

For a finite $S\subseteq \mathbb{N}$, prescribe a family $\mathcal{A}\subseteq \left(\genfrac{}{}{0ex}{}{S}{r-1}\right)$. We want a new vertex $v$ such thatFor any $v\notin S$, the probability of precisely this pattern in the countable random uniform hypergraph isTwo different candidate vertices use disjoint hyperedge decisions: all the other vertices in each tested edge lie in $S$. The successes are therefore independent random variables with the same positive probability $q$. The probability that the first $N$ candidates all fail is $(1-q{)}^N\to 0$. The same argument after discarding any finite initial set of candidates shows that infinitely many witnesses exist almost surely.

There are only countably many finite subsets of $\mathbb{N}$, and finitely many prescriptions for each. A countable union of null events is null. Consequently the random uniform hypergraph satisfies every such extension prescription simultaneously almost surely.

Now let $H$ and $K$ be two countably infinite $r$-uniform hypergraphs with the hypergraph extension property. Enumerate their vertex sets and construct increasing finite partial hypergraph isomorphisms by the back-and-forth method. At a forward step, take the least unused vertex $u$ of $H$. Its incident hyperedges with each $(r-1)$-subset of the current domain specify a pattern on the matched vertices of $K$. The hypergraph extension property supplies an unused vertex $v$ of $K$ with exactly this pattern. Adding $u\mapsto v$ preserves and reflects every hyperedge in the enlarged domain. At the next step, take the least unused vertex of $K$ and perform the identical construction with $H$ and $K$ interchanged.

The union of the finite maps is defined on every vertex and has every vertex in its range. It is a bijection, and each finite $r$-set appears at some finite stage, so all hyperedges and nonedges are preserved. Thus it is a hypergraph isomorphism. Existence of at least one structure with the property follows from the probability-one construction already proved; fix one representative and call it $G_{\mathrm{univ}}^{(r)}$. ThereforeThe hypergraph isomorphism type does not depend on $p$. In the case $r=2$ it is the Rado graph. For $r=1$, the argument says that the infinitely many selected and unselected singleton vertices determine the same one-uniform structure for every $p\in (0,1)$.

Every finite connected cubic graph with at most two bridges has a perfect matching.

Proof. The handshaking lemma implies that the number $n$ of vertices is an even integer. Fix a nonempty subset $S$ of the vertex set, and let $q$ count the components of $G-S$ of odd integer order. For such a component $C$, counting vertex degrees gives $3|C|=2|E(C)|+d(C)$, where $d(C)$ counts its edges to $S$. Thus $d(C)$ is a positive odd integer. If it is one, the unique outgoing edge is a bridge; this happens for at most two components. For all others $d(C)\ge 3$. Therefore $3q-4\le 3|S|$. Meanwhile $q\equiv n-|S|\equiv |S|(\mathrm{mod}2)$. If $q>|S|$, the same parity would force $q\ge |S|+2$, contradicting the preceding bound. For $S=\varnothing$ there is one component of even integer order and hence $q=0$. Apply Tutte's theorem on perfect matchings.

The shortest path problem asks for a graph path from a source vertex $s$ to a destination vertex $t$ minimizing its total edge weight. Here $w_e$ is the cost of traversing edge $e$, and costs add along the graph path. If no route exists, its shortest-path distance is $\infty$. With nonnegative edge weights, deleting cycles in a graph from a walk never increases its cost, so repetitions cannot improve the optimum.

Consider the undirected graph with vertex set $V=\{A,B,C,D\}$ and the six edge weightsEach edge can be traversed in either direction at the same cost. The direct graph path $A,D$ costs $10$; $A,B,D$ costs $4+1=5$; $A,C,D$ costs $1+5=6$. The cheapest graph path is $A,C,B,D$, costing $1+2+1=4$. The remaining graph path $A,B,C,D$ costs $11$, exhausting the possibilities without repeated vertices.

Thus fewest edges and least total cost are different objectives. Breadth-first search minimizes the number of edges, which suffices when every edge has the same positive cost. Unequal nonnegative costs call for the Dijkstra algorithm. On a map, weights might be minutes rather than kilometres: a longer-looking route can arrive sooner. This is why a weighted graph separates the network's connections from what a particular journey costs.

An undirected simple graph is exactly a pair of setsThus every edge is a two-element set of distinct vertices. The unordered pair $\{u,v\}$ equals $\{v,u\}$, so there is no direction. The distinctness condition excludes self-loops, and using a set of edges excludes parallel copies. A simple graph may have vertices with no incident edges; $E$ does not by itself determine $V$. For example, $(\{A,B\},\{AB\})$ and $(\{A,B,C\},\{AB\})$ have the same edge set but different vertex sets.^[ref]

In the six-vertex example, the vertex neighbourhood of $C$ is $\Gamma (C)=\{A,B,D\}$, so its degree of a vertex is $\mathrm{deg}(C)=3$. In label order $A,B,C,D,E,F$, the degree sequence isThis is the handshaking lemma: count each edge once at each of its two endpoints. The average degree of a graph here is $14/6=7/3$. The degree sequence is a compact consistency check on an edge list; an odd sum could not describe any finite undirected graph. It also forces the number of odd degrees of vertices to be even, since the even terms do not affect the parity of the sum.

The adjacency matrix in the figure uses label order $A,B,C,D,E,F$. Its entry $M_{uv}$ is one exactly when $\{u,v\}\in E$, and zero otherwise. It is a symmetric matrix with zero diagonal, and each row sum gives the corresponding vertex degree. For example, row $C$ is $(1,1,0,1,0,0)$. The fourteen ones count both directions of the seven undirected edges; they do not indicate fourteen different edges. This translates a picture into a representation suitable for calculation.

The restrictions matter. A directed graph uses an ordered pair to distinguish $u\to v$ from $v\to u$, so reachability can depend on direction. A multigraph can contain several distinct edges between the same vertices; adding another $CD$ would raise $\mathrm{deg}(C)$ and $\mathrm{deg}(D)$ to four without adding a new neighbour. A self-loop at $A$ contributes two to its undirected vertex degree, making it four, because both endpoints lie at $A$. Specify whether self-loops are allowed in a multigraph. Finally, a weighted graph attaches numerical information to edges: if links carry travel times, minimizing the number of edges need not minimize total time. These are changes to the model, rather than changes to how the same simple graph is drawn.

A subhypergraph restricts the vertex set of a hypergraph and retains some of its edges contained in that vertex set. Retaining every such edge gives an induced subhypergraph.

A system of distinct representatives for a finite indexed family of finite sets $(A_i{)}_{i\in I}$ chooses one element $x_i\in A_i$ per index, with all choices distinct. Form a bipartite graph with left vertex set $I$, right vertex set ${\bigcup }_{i\in I}{A}_i$, and edges $ix$ whenever $x\in A_i$. Matching saturation of $I$ is precisely a system of distinct representatives. Hence Hall's marriage theorem says that such choices exist exactly when $|{\bigcup }_{i\in J}{A}_i|\ge |J|$ for every subset $J\subseteq I$. Repeated equal sets still have separate indices and separate demands.

In the spanning subgraph formed by the union of two matchings in a graph $M_1,M_2$, every vertex has vertex degree at most two. A common edge is an isolated two-vertex connected component of a graph. Every other nontrivial connected component of a graph is a graph path or an even graph cycle, with the edges alternating between the two matchings in a graph.

Suppose the original graph is a bipartite graph with vertex sets $A,B$, $M_1$ covers a specified subset $X\subseteq A$, and $M_2$ covers a specified subset $Y\subseteq B$. Their union contains a matching in a graph covering $X\cup Y$. On an even graph cycle, either alternating choice covers every vertex. On an odd-length graph path, the larger alternating choice covers every vertex. On an even-length graph path, both endpoints lie in the same side: choose $M_1$ if they lie in $A$, or $M_2$ if they lie in $B$. Every required endpoint is covered by that choice, and every internal vertex meets both choices. Select each common edge as well; isolated vertices are not in $X\cup Y$. Different connected components of a graph do not interfere.

Suppose $T$ is any vertex set whose induced subgraph has every degree of a vertex at least two. No vertex of $T$ can be the first one deleted from $T$: before such a deletion it still has its two graph neighbours within $T$, contradicting eligibility for deletion. Consequently every qualifying $T$ survives every legal deletion sequence. Once deletion stops, its remainder $R$ itself qualifies, because every surviving vertex has at least two surviving graph neighbours. Therefore $T\subseteq R$ for every qualifying $T$: $G[R]$ is the unique maximum and the final remainder is independent of deletion order. The intermediate FIFO queues and deletion orders can differ.

There is also a direct existence argument. If $A$ and $B$ qualify, then $A\cup B$ qualifies: each vertex retains at least the two graph neighbours it already had in $A$ or in $B$. Taking the union of all qualifying vertex sets produces the maximum. This rules out a collection of competing, incomparable inclusion-maximal answers. It also explains why restricting the search to connected subgraphs would change the question.