Connected Graph Ontology

FLOW ALGEBRA
CONNECTED GRAPH ONTOLOGY
Kireth Semantic Library | Discrete Mathematics | Graph Theory
Source: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/graph-theory/connected-graph-ontology.html
Version: 1.0 | Date: 2026-10-11 | Locale: en-GB
Authors: Mark Higgins — Sky (Recursive AI)

1. ONTOLOGY DEFINITION
ontology ConnectedGraphOntology extends GraphTheoryOntology
  describes: Connectivity and connected components in graph structures.
  scope: finite undirected graphs by default; directed variants explicitly typed.
  graph G = (V,E), E subset {{u,v} | u,v in V, u != v} for simple undirected graphs.
  connected(G) iff V != empty AND forall u,v in V: exists a u-v path.
  convention: a single-vertex graph is connected; the null graph is not connected here.

2. TYPED ENTITIES
entity Graph {vertices:Set<Vertex>, edges:Set<Edge>, directed:Boolean}
entity Vertex {id:Identifier, graph:Graph}
entity Edge {endpoints:Pair<Vertex>, graph:Graph}
entity Path {vertices:Sequence<Vertex>, edges:Sequence<Edge>}
entity ConnectedComponent {vertices:Set<Vertex>, inducedEdges:Set<Edge>}
entity CutVertex {vertex:Vertex, graph:Graph}
entity Bridge {edge:Edge, graph:Graph}
entity SpanningTree {graph:Graph, edges:Set<Edge>}
entity DirectedGraph {vertices:Set<Vertex>, arcs:Set<OrderedPair<Vertex,Vertex>>}
entity ConnectivityCertificate {kind:Enum[spanning_tree,component_partition,reachability], evidence:Data}

3. TYPED RELATIONSHIPS
relationship INCIDENT_TO(Edge,Vertex)
relationship ADJACENT_TO(Vertex,Vertex) symmetric for undirected graphs
relationship REACHABLE_FROM(Vertex,Vertex) reflexive and transitive
relationship BELONGS_TO(Vertex,ConnectedComponent)
relationship CONNECTED_BY(Path,Vertex,Vertex)
relationship SPANS(SpanningTree,Graph)
relationship REMOVAL_DISCONNECTS(CutVertex|Bridge,Graph)
relationship STRONGLY_REACHABLE_FROM(Vertex,Vertex) for directed graphs

4. CORE OPERATIONS
operation neighbours(G,v) -> Set<Vertex>
operation reachable(G,u,v) -> Boolean
operation connected(G) -> Boolean
operation components(G) -> Set<ConnectedComponent>
operation component_of(G,v) -> ConnectedComponent
operation add_edge(G,u,v) -> Graph
operation remove_edge(G,e) -> Graph
operation remove_vertex(G,v) -> Graph
operation spanning_tree(G) -> SpanningTree? // only when G connected
operation bridges(G) -> Set<Edge>
operation articulation_points(G) -> Set<Vertex>
operation strongly_connected_components(D) -> Set<Set<Vertex>>

5. FORMAL RULES AND ALGEBRA
R1: connected(G) <=> forall u,v in V, reachable(G,u,v), for nonempty undirected G.
R2: reachable(G,u,u) = true for all u in V (zero-length path).
R3: reachable(G,u,v) AND reachable(G,v,w) => reachable(G,u,w).
R4: For undirected G, reachable(G,u,v) => reachable(G,v,u).
R5: Components(G) partition V into maximal nonempty connected vertex sets.
R6: For a finite nonempty undirected G, connected(G) <=> |components(G)| = 1.
R7: For finite undirected G with n >= 1, connected(G) <=> G has a spanning tree.
R8: For finite simple undirected connected G, |E| >= |V|-1.
R9: Adding an edge to a connected undirected graph preserves connectivity.
R10: Removing an edge may increase the component count by at most one.
R11: e is a bridge iff components(G-e) > components(G).
R12: v is an articulation point iff components(G-v) > components(G), with component count computed on the remaining vertices.
R13: Every tree with at least one vertex is connected and acyclic.
R14: Every connected finite undirected graph has a spanning tree.
R15: For a directed graph, strong connectivity means each ordered vertex pair is mutually reachable by directed paths.
R16: Weak connectivity of a directed graph means its underlying undirected graph is connected.

6. INFERENCE FLOW
flow CheckConnectivity(G:Graph) -> Result
  require well_formed(G)
  if |G.vertices| = 0: return {connected:false, components:0, convention:"nonempty"}
  select start from G.vertices
  visited := BFS_or_DFS(G,start,edge_direction="ignore" if undirected else "respect")
  if not G.directed:
    return {connected:(visited=G.vertices), evidence:visited}
  else:
    return {reachable_from_start:visited, strong_connected:all_vertices_reachable_in_G_and_reverse_G_from_start}
end

flow ExtractComponents(G:UndirectedGraph) -> Set<ConnectedComponent>
  unseen := G.vertices
  output := empty_set
  while unseen != empty_set:
    choose v in unseen
    C := BFS_or_DFS(G,v)
    output.add(induced_subgraph(G,C))
    unseen := unseen - C
  return output
end

7. SEMANTIC_EQUIVALENCE
SEMANTIC_EQUIVALENCE:
  "connected undirected graph" <=> "undirected graph with a path between every pair of vertices"
  "connected component" <=> "maximal connected subgraph" (vertex-induced interpretation)
  "weakly connected digraph" <=> "digraph whose underlying undirected graph is connected"
  "strongly connected digraph" <=> "digraph with directed paths in both directions for each vertex pair"
SEMANTIC_DIFFERENCE:
  connected != complete
  connected != biconnected
  weakly_connected != strongly_connected
  path != edge
  reachability != adjacency

8. VALIDATION AND COUNTEREXAMPLES
validate vertices and endpoints are typed and every edge endpoint belongs to V.
validate BFS/DFS reachability against component partition.
validate each component is connected and no edge joins different components.
validate a reported spanning tree has all vertices, is connected, acyclic and has |V|-1 edges.
counterexample: two disjoint edges on four vertices form a disconnected graph.
counterexample: a three-vertex path is connected but not complete.
counterexample: a directed chain a->b->c is weakly connected but not strongly connected.
edge_case: one vertex, zero edges => connected by this convention.
edge_case: zero vertices => not connected by this convention.

9. CONFIDENCE AND PROVENANCE
CONFIDENCE:
  formal_definitions: 1.00
  graph_theory_laws: 1.00 under declared assumptions
  computed_results: 1.00 only after validated exact computation
  unverified_external_assertions: null
PROVENANCE:
  origin: established mathematical graph theory
  page_alignment: topic inferred from supplied URL; live page not independently verified
  assumptions: finite graphs; simple undirected unless otherwise declared

10. FLOW_HASH AND UPDATE_MODEL
FLOW_HASH:
  method: SHA-256
  input: canonical_utf8(ontology_name,version,entities,relationships,rules,validation)
  value: COMPUTE_ON_INGEST (not precomputed)
UPDATE_MODEL:
  trigger: source_revision OR definition_change OR new_validated_rule
  process: validate -> version_increment -> recompute_hash -> archive_prior -> publish
  preserve: provenance, semantic_distinctions, formal_assumptions

11. AI_CONSUMPTION
AI_CONSUMPTION:
  machine_readable: true
  reasoning_modes: [deductive, graph_traversal, component_analysis, proof_validation]
  retrieval_keys: [connected_graph, connectivity, connected_component, bridge, articulation_point, spanning_tree]
  input_types: [Graph,DirectedGraph]
  output_types: [Boolean,ConnectedComponent,ConnectivityCertificate]
  safety: distinguish directed and undirected connectivity; disclose empty-graph convention
  inference_policy: assert connectivity only with valid path proof, traversal certificate, or verified theorem
  semantic_links: [GraphOntology,VertexOntology,EdgeOntology,PathOntology,TreeOntology,DirectedGraphOntology,UndirectedGraphOntology]

END FLOW ALGEBRA