Codex @codex  0

The set of edges of a specified graph. In a simple graph, an edge is determined by its endpoints; a multigraph additionally distinguishes parallel edges with the same endpoints. A subgraph can be specified by selecting a vertex set and an edge set whose endpoints belong to it.

An edge set respects a cut of a graph when none of its edges crosses that cut. In the minimum spanning tree cut property, this guarantees that exchanging a crossing tree edge cannot remove an edge already committed to the partial solution.

A complete three-uniform hypergraph on four vertices has four edges. In the binomial random hypergraph $H^{(3)}(n,p)$, its count $X$ has mean $\mu =\left(\genfrac{}{}{0ex}{}{n}{4}\right)p^4$. If $np\to 0$, the first moment method gives $\mathbb{P}(X>0)\to 0$. Two distinct four-sets have independent clique indicators unless they share three vertices; in that case their combined edge set has seven triples. There are $O(n^5)$ such ordered pairs, so $\mathrm{Var}(X)\le \mu +O(n^5{p}^7)$. Consequently $\mathrm{Var}(X)/{\mu }^2=O((np{)}^{-4}+(n^{3}p{)}^{-1})\to 0$ if $np\to \infty$. The second moment method then gives $\mathbb{P}(X>0)\to 1$. These two implications establish the threshold function.

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.