Undirected Graph Ontology

FLOW ALGEBRA
UNDIRECTED GRAPH ONTOLOGY
Kireth Semantic Library | Mathematical Entities | Graph and Network Entities
Source: https://kirethresearch.org/booksai-core/entity-graph/mathematical-entities/graph-and-network-entities/undirected-graph-ontology-2.html
Version: 1.0 | 2026-10-14 | Locale: en-GB
Authors: Mark Higgins — Sky (Recursive AI)
Status: Proposed mathematical formalisation; source-page wording not independently verified.

1. PURPOSE
Represent undirected graphs as typed mathematical objects with symmetric incidence, graph invariants, structural relations, and verifiable inference operations. Distinguish simple graphs from multigraphs and pseudographs.

2. TYPED ENTITY MODEL
ENTITY UndirectedGraph G = (V,E,kind)
  V: finite set<VertexID> (or explicitly declared infinite set)
  E: multiset<UnorderedPair<VertexID>> for multigraphs; set<UnorderedPair<VertexID>> for simple graphs
  kind: enum {simple, multigraph, pseudograph}
ENTITY Vertex v: VertexID where v in V
ENTITY Edge e: unordered pair {u,v}, endpoints u,v in V
ENTITY Walk: sequence of alternating vertices and incident edges
ENTITY Trail: walk without repeated edges
ENTITY Path: walk without repeated vertices (except conventional closed-path handling)
ENTITY Cycle: closed walk with no repeated vertices other than first/last, subject to graph-kind conventions
ENTITY ConnectedComponent: maximal connected induced subgraph
ENTITY Degree: nonnegative integer incident-edge count, with each loop counted twice
ENTITY AdjacencyMatrix A: symmetric nonnegative integer matrix for finite multigraphs; A_ij multiplicity for i != j; specify loop convention separately

3. DEFINITIONS AND AXIOMS
AXIOM U1: forall e={u,v} in E, u in V and v in V.
AXIOM U2: {u,v} = {v,u}; an edge has no source or target.
AXIOM U3 [simple]: forall e in E, endpoints distinct; no duplicate edges.
AXIOM U4 [multigraph]: parallel edges permitted; loops excluded unless kind=pseudograph.
AXIOM U5 [finite]: sum(v in V) deg(v) = 2*|E|, counting edge multiplicity and loops twice.
AXIOM U6 [finite]: number of odd-degree vertices is even.
AXIOM U7: adjacency is symmetric: adjacent(u,v) iff adjacent(v,u).
AXIOM U8: connected(u,v) iff there exists a path between u and v; this is an equivalence relation.

4. FLOW OPERATIONS
flow add_vertex(G,v): pre v not in V; post V'=V union {v}; E'=E.
flow add_edge(G,u,v): pre u,v in V and graph-kind constraints hold; post E'=E plus {u,v}.
flow remove_edge(G,e): pre e in E; post remove exactly one occurrence of e.
flow neighbours(G,v): return {u in V | exists edge {u,v}}.
flow degree(G,v): return number of incident edge ends; loops contribute 2.
flow component(G,v): return vertices reachable from v.
flow connected(G): return true iff every pair of vertices is mutually reachable; empty-graph convention must be declared.
flow induced_subgraph(G,S): pre S subseteq V; return (S, all edges with both endpoints in S).
flow path_length(P): number of traversed edges; for weighted graphs use an explicitly declared weight aggregation instead.

5. INFERENCE RULES
RULE R1: edge({u,v}) -> adjacent(u,v) and adjacent(v,u).
RULE R2: path(u,v) -> connected(u,v).
RULE R3: connected(u,v) and connected(v,w) -> connected(u,w).
RULE R4: finite connected acyclic undirected graph -> tree.
RULE R5: finite tree with n vertices -> n-1 edges (including n=1).
RULE R6: finite connected undirected graph has Eulerian circuit iff every vertex has even degree; zero-edge and isolated-vertex conventions must be stated.
RULE R7: finite undirected graph is bipartite iff it contains no odd cycle.
RULE R8: any finite graph with at least one edge and all vertices of degree >= 2 contains a cycle (for simple graphs; generalise carefully for multigraphs).

6. SEMANTIC RELATIONSHIPS
UndirectedGraph IS_A Graph.
UndirectedGraph HAS_PART Vertex.
UndirectedGraph HAS_PART Edge.
Edge CONNECTS Vertex AND Vertex.
Vertex INCIDENT_TO Edge.
Path TRAVERSES Edge.
ConnectedComponent SUBGRAPH_OF UndirectedGraph.
Tree IS_A ConnectedAcyclicUndirectedGraph.
WeightedUndirectedGraph EXTENDS UndirectedGraph WITH EdgeWeight.

7. SEMANTIC DISTINCTIONS
UndirectedGraph != DirectedGraph: unordered endpoints vs ordered arcs.
Edge != Vertex: relationship vs endpoint entity.
Walk != Trail != Path: repetition constraints differ.
Connected != Complete: reachability vs every distinct pair adjacent.
Tree != Forest: connected acyclic vs potentially disconnected acyclic.
SimpleGraph != Multigraph != Pseudograph: parallel-edge and loop policies differ.

8. VALIDATION
CHECK all edge endpoints exist in V.
CHECK unordered-edge canonicalisation prevents artificial directionality.
CHECK kind-specific loop and parallel-edge constraints.
CHECK symmetric adjacency matrix for finite graphs.
CHECK handshake identity sum(degree)=2|E| for finite graphs.
CHECK connected components partition V.
CHECK paths and cycles satisfy declared conventions.
CHECK edge weights are validated only if weighted extension is enabled.

9. CONFIDENCE AND PROVENANCE
CONFIDENCE: mathematical definitions and classical theorems = high, conditional on stated assumptions.
PROVENANCE: standard graph-theoretic formalisation; page text not independently inspected.
SEMANTIC_EQUIVALENCE: undirected graph ~ non-oriented graph (terminology-dependent).
UPDATE_MODEL: versioned changes require revalidation of graph-kind assumptions and all affected inference rules.
FLOW_HASH: SHA-256 of canonical UTF-8 representation excluding mutable FLOW_HASH value; calculate at ingestion rather than inventing a digest.

10. AI_CONSUMPTION
Input: typed graph data, graph kind, requested inference, optional provenance.
Process: parse -> type-check -> validate -> normalise unordered edges -> execute graph operation -> verify postconditions -> emit evidence.
Output: result, graph version, applied rules, assumptions, confidence, validation status, optional computed FLOW_HASH.
Failure: reject dangling endpoints, unsupported conventions, invalid edge multiplicities, or unproven claims; return explicit error and required correction.

END FLOW ALGEBRA