Vertex Ontology

FLOW ALGEBRA
VERTEX ONTOLOGY — DISCRETE MATHEMATICS / GRAPH THEORY
Version: 1.0
Source URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/graph-theory/vertex-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)
Research: https://kirethresearch.org
Status: Formal mathematical synthesis; live source page not independently verified.

1. ONTOLOGY DECLARATION
ontology VertexOntology {
  domain: DiscreteMathematics.GraphTheory
  primary_entity: Vertex
  related_entities: [Graph, Edge, Arc, Neighbourhood, Degree, Walk, Path, Cycle, Subgraph]
  semantics: classical_graph_theory
}

2. TYPED ENTITIES
Vertex := { id: Identifier, attributes: Map<String, Value> }
Graph[V,E] := { vertices: Set<Vertex>, edges: Set<Edge> }
UndirectedEdge := UnorderedPair<Vertex>  # loops/multiedges require an explicit graph model
DirectedArc := OrderedPair<Vertex,Vertex>
Neighbourhood := Set<Vertex>
Degree := NonNegativeInteger

3. FORMAL DEFINITIONS
G = (V,E)
v isVertexOf G iff v in V
For a simple undirected graph: E subseteq {{u,v} | u,v in V and u != v}
For a simple directed graph: E subseteq V x V
adjacent(u,v,G) iff {u,v} in E (undirected)
outAdjacent(u,v,G) iff (u,v) in E (directed)
N_G(v) = {u in V | adjacent(u,v,G)}
deg_G(v) = |N_G(v)| for simple undirected graphs
indeg_G(v) = |{u in V | (u,v) in E}| for simple directed graphs
outdeg_G(v) = |{u in V | (v,u) in E}| for simple directed graphs
isolated(v,G) iff deg_G(v) = 0 (undirected)
pendant(v,G) iff deg_G(v) = 1 (undirected)

4. GRAPH TRANSFORMATIONS
addVertex(G,v): precondition v notin V; result (V union {v},E)
removeVertex(G,v): precondition v in V; result (V minus {v}, {e in E | v not incident to e})
inducedSubgraph(G,S): precondition S subseteq V; result (S,{e in E | endpoints(e) subseteq S})
relabelVertices(G,f): precondition f is a bijection on V; preserve edge incidence

5. ALGEBRAIC INVARIANTS AND LAWS
For finite undirected graphs (loops counted twice in degree):
  sum_{v in V} deg(v) = 2|E|
For finite directed graphs:
  sum_{v in V} indeg(v) = |E| = sum_{v in V} outdeg(v)
For simple undirected graphs with n = |V|:
  0 <= deg(v) <= n-1
For any graph isomorphism f: G -> H:
  adjacency(u,v,G) iff adjacency(f(u),f(v),H)
  corresponding vertex degrees are preserved

6. RELATIONSHIP FLOW
Vertex --belongsTo--> Graph
Vertex --incidentTo--> Edge
Vertex --adjacentTo--> Vertex
Vertex --hasDegree--> Degree
Vertex --participatesIn--> Walk | Path | Cycle
Vertex --includedIn--> Subgraph
Vertex --mappedBy--> GraphIsomorphism

7. INFERENCE RULES
R1: (u,v) in E_directed => u in V and v in V
R2: {u,v} in E_undirected => adjacent(u,v) and adjacent(v,u)
R3: adjacent(u,v) and adjacent(v,w) does NOT generally imply adjacent(u,w)
R4: deg(v) = 0 => v is isolated (undirected)
R5: deg(v) = 1 => v is pendant (undirected)
R6: isomorphism(G,H,f) => deg_G(v) = deg_H(f(v))

8. SEMANTIC_EQUIVALENCE
Vertex ~= Node (graph-theoretic context)
Neighbour ~= Neighbor (orthographic variant)
Vertex != Edge
Vertex != Graph
Graph vertex != geometric corner in every context; disambiguate by domain

9. VALIDATION
assert unique_vertex_ids(G)
assert all_edge_endpoints_belong_to_vertices(G)
assert graph_model_explicit(simple|directed|multigraph|pseudograph)
assert degrees_are_nonnegative(G)
assert handshake_lemma(G) when finite_undirected(G)
assert directed_degree_sums(G) when finite_directed(G)
reject undefined degree conventions for loops or parallel edges

10. CONFIDENCE
formal_definitions: 1.00 (under declared graph models)
standard_theorems: 1.00 (under stated assumptions)
source_page_alignment: unverified
semantic_aliases: context_dependent

11. FLOW_HASH
algorithm: SHA-256
input: canonical UTF-8 serialization of ontology content excluding FLOW_HASH value
value: compute_on_publication

12. UPDATE_MODEL
versioning: semantic
trigger: source_revision | theorem_correction | schema_change | terminology_change
process: validate -> compare -> increment_version -> recompute_hash -> publish
provenance: retain previous version and change log

13. AI_CONSUMPTION
representation: typed graph entities and validated inference rules
retrieval_keys: [vertex, node, graph, adjacency, degree, neighbourhood, incidence]
reasoning_constraints: distinguish directed/undirected and simple/multigraph cases
output_contract: definitions + assumptions + provenance + confidence
avoid: inferring adjacency from shared neighbours without an explicit edge

END FLOW ALGEBRA