Generative Structural Theory v1.30 — K4-Supported Relations with One-Way Edges: Exact Counting and Minimality

For a relation on four fixed labelled nodes whose undirected support is the complete graph K_4 (each of the six edges carrying one or both of its pairs; one-way edges allowed), this manuscript counts the strongly connected spanning sub-relations (s), the inclusion-minimal ones (mu) and the least number of pairs of one (mc). Strong connectivity of any relation on the four nodes is characterized by its 14 outgoing cuts, and s is given by inclusion-exclusion over these cuts. Its 2^14 terms are grouped by the preorder that each family of cuts generates; the coefficient of a preorder is (-1)^(c - b) (b - 1)! when the order induced on its c equivalence classes is a disjoint union of b chains, and 0 otherwise, proved by two sign-reversing involutions. The inclusion-minimal strongly connected relations on four labelled nodes are classified into four kinds: directed 4-cycles (6), a directed 3-cycle with the fourth node joined to it by one two-way edge (24), two paths u -> x -> v and u -> y -> v with v -> u (12), and two-way spanning trees (16), 58 in all, with minimality, disjointness, counts and necessity proved separately; mu of a parent relation is the number of these contained in it, counted kind by kind. These parts hold for every relation on the four nodes. Using the K_4 support, every strongly connected parent relation contains a directed 4-cycle, so mc = 4, and the members with four pairs are its directed 4-cycles. For all twelve pairs s = 1606, mu = 58, mc = 4; without one pair 620, 33, 4; for a strongly connected relation with one pair on each edge, given in the text, 5, 2, 4. For all twelve pairs and one edge, the members holding a pair of that edge are counted directly by contraction and reached sets (1378); with the 228 members of K_4 with that edge removed, taken from v1.29 with the correspondence confirmed, they give 1606, in agreement with the cut inclusion-exclusion. K_4 with one edge removed lies outside the class and can have mc = 5 (v1.29). The values 58 and 1606 are listed in the literature as cited by the review side, and the existence of a Hamiltonian cycle in a strongly connected semicomplete digraph is known; v1.30 gives hand proofs for four nodes, the literature was not checked by the drafting side, and no novelty is claimed. No machine enumeration or machine numerical computation was made; the proofs and counts are given by hand. The parent relations treated concretely are those with support K_4, with K_4 with one edge removed only as the check C1; relations on five or more nodes are not treated.