Edge Ontology

FLOW ALGEBRA
TITLE: Edge Ontology
DOMAIN: Discrete Mathematics / Graph Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/graph-theory/edge-ontology.html
VERSION: 1.0
LANGUAGE: en-GB
AUTHORS: Mark Higgins — Sky (Recursive AI)
SITE: https://kirethresearch.org
STATUS: Mathematical reference model; source page not independently verified.

1. ONTOLOGY DECLARATION
flow EdgeOntology v1.0 {
  domain: GraphTheory;
  concept: Edge;
  parent: GraphOntology;
  semantics: typed, finite-or-infinite graph structures;
}

2. TYPED ENTITIES
entity Vertex { id: Identifier }
entity Edge { id: Identifier; endpoints: VertexPair; directed: Boolean; weight: Optional<Number>; label: Optional<String> }
entity Graph { vertices: Set<Vertex>; edges: Set<Edge>; kind: GraphKind }
type GraphKind = SimpleUndirected | UndirectedMultigraph | DirectedGraph | DirectedMultigraph | Pseudograph;
type VertexPair = UnorderedPair<Vertex> | OrderedPair<Vertex>;
entity Walk { vertices: Sequence<Vertex>; edges: Sequence<Edge> }
entity Incidence { edge: Edge; vertex: Vertex }

3. CORE DEFINITIONS
For an undirected graph G=(V,E), each non-loop edge joins an unordered pair {u,v} of vertices.
For a directed graph G=(V,E), each arc joins an ordered pair (u,v), with source u and target v.
A multigraph permits distinct edge identifiers with identical endpoints.
A loop is an edge with identical endpoints; whether loops are allowed depends on graph kind.
In a simple undirected graph, loops and parallel edges are disallowed.

4. FORMAL RELATIONSHIPS
Edge(e) AND belongsTo(e,G) -> endpoints(e) are vertices of G.
incident(e,v) <-> v is an endpoint of e.
adjacent(u,v) <-> EXISTS e in E with endpoints(e)={u,v} [undirected].
outgoing(e,u) <-> source(e)=u [directed].
incoming(e,v) <-> target(e)=v [directed].
parallel(e1,e2) <-> e1 != e2 AND endpoints(e1)=endpoints(e2) (respecting direction).

5. EDGE OPERATIONS
addEdge(G,e): requires endpoint membership and graph-kind constraints; returns G' with e included.
removeEdge(G,e): returns G'=(V,E\{e}); retains vertices.
reverseEdge(e): for directed e=(u,v), returns arc (v,u).
contractEdge(G,e): identifies endpoints and updates incidence; resulting loops/parallel edges depend on convention.
subdivideEdge(G,e,w): replaces e=(u,v) by (u,w),(w,v) with fresh vertex w.

6. ALGEBRAIC LAWS AND INVARIANTS
Undirected handshake lemma (loops count twice): SUM_{v in V} degree(v) = 2|E|.
Directed degree identity: SUM indegree(v) = SUM outdegree(v) = |E|.
Simple undirected graph: |E| <= |V|(|V|-1)/2 for finite V.
Simple directed graph without loops: |E| <= |V|(|V|-1) for finite V.
Edge deletion cannot create a new walk between previously disconnected vertices.
Adding an edge cannot disconnect previously connected vertices.
A bridge is an edge whose deletion increases the number of connected components in an undirected graph.
A loop cannot be a bridge.

7. INFERENCE RULES
RULE E1: edge(e,u,v) -> vertex(u) AND vertex(v).
RULE E2: undirectedEdge(e,u,v) -> adjacent(u,v) AND adjacent(v,u).
RULE E3: directedEdge(e,u,v) -> reachable(u,v) by a walk of length one.
RULE E4: incident(e,v) -> degreeContribution(e,v) >= 1 [non-loop incidence].
RULE E5: bridge(e,G) -> connectedComponents(G-e) > connectedComponents(G).
RULE E6: weightedEdge(e,w) -> weight(e)=w; no sign restriction unless separately specified.

8. VALIDATION
CHECK V1: Every endpoint belongs to the declared graph vertex set.
CHECK V2: Edge IDs are unique within the graph.
CHECK V3: Directed endpoints preserve source/target order.
CHECK V4: Simple graphs contain neither loops nor parallel edges.
CHECK V5: Undirected degree calculations count loops twice.
CHECK V6: Edge operations preserve graph-kind constraints or explicitly report a type change.
CHECK V7: Weights and labels are optional and never assumed to exist.
CHECK V8: Finite-graph cardinality laws are not applied unqualified to infinite graphs.

9. SEMANTIC_EQUIVALENCE
Edge == graph link [graph-theoretic context only].
Arc == directed edge.
Unordered endpoint pair == undirected edge endpoints [simple graph context].
Ordered endpoint pair == directed arc endpoints [simple directed graph context].
NOTE: A knowledge-graph relationship may be represented by an edge, but the terms are not universally interchangeable.

10. CONFIDENCE
formal_definitions: 1.00 [standard mathematical conventions].
conditional_claims: 1.00 when stated graph-kind and finiteness assumptions hold.
source_page_alignment: unverified.
confidence_policy: Mathematical certainty is distinct from empirical or source-document confidence.

11. FLOW_HASH
algorithm: SHA-256
input: canonical UTF-8 serialisation of ontology version, declarations, rules and constraints.
value: computed by downstream implementation; not fabricated here.

12. UPDATE_MODEL
versioning: semantic versioning.
change_detection: compare canonical flow hashes.
backwards_compatibility: preserve entity and rule identifiers where possible.
revalidation: execute all checks after edits to graph kinds, edge semantics or inference rules.

13. AI_CONSUMPTION
parse: read typed entities and relation predicates.
normalise: distinguish undirected edges, directed arcs and parallel-edge identities.
reason: apply inference rules only under their stated preconditions.
validate: reject malformed endpoints and graph-kind violations.
explain: retain provenance, rule ID, assumptions and confidence for each inference.
output: machine-readable edge facts, graph operations, invariants and validation results.

END FLOW ALGEBRA