Bipartite Graph Ontology

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

1. PURPOSE
Represent, validate and reason about bipartite graphs, two-part vertex partitions, 2-colourability, odd-cycle exclusion and matchings. This is a formal mathematical model, not a verified transcription of the live source page.

2. TYPED ENTITIES
Graph := (V: FiniteSet[Vertex], E: Set[UnorderedPair[Vertex]])
Bipartition := (L: Set[Vertex], R: Set[Vertex])
Colouring := Map[Vertex, {0,1}]
Matching := Set[Edge]
VertexCover := Set[Vertex]
Path := Sequence[Vertex]
Cycle := ClosedSimplePath
Certificate := Bipartition | OddCycle
Assumption: graphs are finite, simple and undirected unless otherwise declared.

3. CORE PREDICATES
DISJOINT(L,R) := L ∩ R = ∅
PARTITION(V,L,R) := DISJOINT(L,R) ∧ L ∪ R = V
CROSS_EDGE({u,v},L,R) := (u∈L ∧ v∈R) ∨ (u∈R ∧ v∈L)
BIPARTITE(G) := ∃L,R: PARTITION(V,L,R) ∧ ∀e∈E CROSS_EDGE(e,L,R)
PROPER_2_COLOUR(G,c) := ∀{u,v}∈E: c(u) ≠ c(v)
MATCHING(G,M) := M⊆E ∧ ∀e,f∈M: e≠f ⇒ e∩f=∅
COVER(G,C) := C⊆V ∧ ∀{u,v}∈E: u∈C ∨ v∈C

4. EQUIVALENCES AND LAWS
BIPARTITE(G) ⇔ G admits a proper 2-colouring.
BIPARTITE(G) ⇔ G has no odd-length cycle.
Every tree and forest is bipartite.
Every subgraph of a bipartite graph is bipartite.
For a connected bipartite graph containing at least one vertex, its bipartition is unique up to swapping L and R.
For disconnected graphs, each connected component can be swapped independently.
A graph with no edges is bipartite.
For a simple bipartite graph, |E| ≤ |L|·|R|.
Complete bipartite graph K_(m,n): |V|=m+n; |E|=mn.
Every cycle in a bipartite graph has even length.
Kőnig's theorem (finite bipartite graphs): maximum matching size = minimum vertex-cover size.
Hall's marriage theorem: a matching saturating L exists iff ∀S⊆L, |N(S)|≥|S|.

5. OPERATIONS
TWO_COLOUR(G): BFS/DFS each component; assign opposite colours across edges; return partition or an odd-cycle witness on conflict.
CHECK_BIPARTITION(G,L,R): verify partition and all edges cross parts.
NEIGHBOURS(G,S): {v∈V | ∃u∈S, {u,v}∈E}.
MAXIMUM_MATCHING(G): return a matching of maximum cardinality using a suitable bipartite matching algorithm.
MINIMUM_VERTEX_COVER(G): compute cover of size equal to maximum matching cardinality for bipartite G.
INDUCED_SUBGRAPH(G,S): retain vertices S and edges whose endpoints are in S.

6. INFERENCE RULES
R1: PARTITION(V,L,R) ∧ ALL_CROSS(E,L,R) ⇒ BIPARTITE(G).
R2: ODD_CYCLE(G,C) ⇒ ¬BIPARTITE(G).
R3: BIPARTITE(G) ∧ H⊆G (subgraph) ⇒ BIPARTITE(H).
R4: TREE(G) ⇒ BIPARTITE(G).
R5: PROPER_2_COLOUR(G,c) ⇒ BIPARTITE(G).
R6: BIPARTITE(G) ∧ MATCHING(G,M) ⇒ |M| ≤ min(|L|,|R|).
R7: BIPARTITE(G) ⇒ MAX_MATCHING_SIZE(G)=MIN_VERTEX_COVER_SIZE(G).

7. VALIDATION AND COUNTEREXAMPLES
Validate all vertices and edge endpoints are declared; reject loops for bipartite graphs because a loop cannot cross two disjoint parts.
Triangle K3: odd cycle, therefore not bipartite.
Four-cycle C4: bipartite with alternating vertex classes.
Path P4: bipartite; partition by alternating distance parity.
Disconnected graph: colour every component, including isolated vertices.
Do not confuse 2-colourability with requiring both colour classes to be non-empty.
Do not infer that a bipartite graph is necessarily connected, complete or a tree.

8. SEMANTIC RELATIONSHIPS
BipartiteGraph IS_A UndirectedGraph.
BipartiteGraph HAS_PARTITION Bipartition.
Bipartition HAS_PART LeftVertexSet; RightVertexSet.
Edge CONNECTS VertexInLeftSet TO VertexInRightSet.
BipartiteGraph EQUIVALENT_TO TwoColourableGraph (under stated graph assumptions).
OddCycle OBSTRUCTS Bipartiteness.
Matching SELECTS PairwiseVertexDisjointEdges.
VertexCover INTERSECTS EveryEdge.
BipartiteGraph SUPPORTS MatchingAlgorithms; Scheduling; AssignmentModels.

9. SEMANTIC_EQUIVALENCE
"bipartite graph" ≡ "two-partite graph" (standard mathematical usage).
"proper 2-colouring" ≡ "bipartition by colours" for finite undirected graphs.
"complete bipartite graph" ≠ "bipartite graph" (special case, not synonym).
"two-colourable" refers to chromatic number at most 2, not necessarily exactly 2.

10. CONFIDENCE
Established definitions and theorems: 1.00 (mathematical statements under explicit assumptions).
Source-page textual alignment: unverified; do not assign a fabricated numeric confidence.
Application-specific inferences: require independent evidence and stated assumptions.

11. FLOW_HASH
Canonicalise ontology name, source URL, version, typed schema, predicates and rules as UTF-8; compute SHA-256 over canonical serialisation at ingestion. No hash is asserted without performing this operation.

12. UPDATE_MODEL
On update: increment version; preserve provenance; revalidate formal rules and examples; regenerate hash; record change log; invalidate dependent assertions when assumptions change.

13. AI_CONSUMPTION
INPUT: graph G, optional proposed partition (L,R), query.
PROCESS: validate schema -> test 2-colouring -> generate certificate -> apply relevant rules -> report evidence.
OUTPUT: {bipartite: boolean, partition?: (L,R), odd_cycle_witness?: Cycle, matching?: Matching, provenance, assumptions, confidence}.
Never claim a valid bipartition and an odd-cycle obstruction for the same well-formed graph.

END FLOW ALGEBRA