# A bipartition certificate with an isolated vertex

[← Guide index](https://ocme.evemisslab.com/en/derivations/) · [Original MKO](https://ocme.evemisslab.com/en/mko/mko-bipartite-graph/)

This is an owner-adopted natural-language teaching guide. Finite/arithmetic checks are not universal proofs; no Lean was run, and review scope is recorded per revision. Original source status labels are retained as historical data. Formulas retain exact TeX; no new semantic AST is invented.

derivation-mko-bipartite-graph-01 · ocme-new142-reader-adoption-20261021



## Goal and scope

Audit every bipartition obligation and distinguish one failed partition from nonbipartiteness.

Finite simple undirected graphs; empty parts are allowed but coverage remains required.





## Givens and symbols


- work


- G1 — V={0,1,2,3}, E={{0,1},{1,2}}; candidate A={0,2,3}, B={1}.


- V,E — complete vertex and edge sets
- A,B — the two parts





## Rules and sources


- mko_definition · cited — Check complete vertex coverage, disjointness of the two parts and every edge crossing. A failed proposed partition does not prove nonbipartiteness; an odd cycle can certify it. Isolated vertices may belong to either part, and whether empty parts are allowed must be explicit. · mko-bipartite-graph
- work · prerequisite — A finite simple undirected graph has loop-free duplicate-free unordered edges; graph properties are audited on all declared V and E. A bipartition certificate has disjoint parts with union V and every edge crossing.





## Main derivation

S01 · impliesBefore

V,E

After

E\subseteq\{\{u,v\}:u,v\in V,\ u\ne v\}

Conditions: none

Rule: work · Uses: G1, work

Leaf basis: work

Both edges have distinct legal endpoints;3 is isolated.



S02 · impliesBefore

A=\{0,2,3\},\quad B=\{1\}

After

A\cap B=\varnothing

Conditions: none

Rule: work · Uses: G1, S01, work

Leaf basis: work

No vertex appears in both parts.



S03 · impliesBefore

A\cup B=\{0,1,2,3\}

After

A\cup B=V

Conditions: none

Rule: work · Uses: G1, S02, work

Leaf basis: work

The isolated vertex 3 is included, giving complete coverage.



S04 · impliesBefore

\{0,1\}\in E

After

0\in A,\quad1\in B

Conditions: none

Rule: work · Uses: G1, S03, work

Leaf basis: work

The first edge crosses the parts.



S05 · impliesBefore

\{1,2\}\in E

After

1\in B,\quad2\in A

Conditions: none

Rule: work · Uses: G1, S04, work

Leaf basis: work

The second edge crosses, exhausting all edges.



S06 · impliesBefore

A'=\{0,1\},\quad B'=\{2,3\}

After

\{0,1\}\subseteq A'\implies(A',B')\text{ invalid}

Conditions: none

Rule: work · Uses: G1, S05, work

Leaf basis: work

Another candidate fails while the original graph retains the valid certificate above.



S07 · impliesBefore

H:0-1-2-0\quad\text{(separate triangle)}

After

c(0)\ne c(1)\ne c(2)\implies c(2)=c(0),\ c(2)\ne c(0)

Conditions: none

Rule: work · Uses: G1, S06, work

Leaf basis: work

With two parts on a triangle, the first two edges force0 and 2 together, contradicting the last edge.



S08 · impliesBefore

A\cap B=\varnothing,\quad A\cup B=V,\quad\text{all edges cross}

After

G\text{ is bipartite}

Conditions: none

Rule: mko_definition · Uses: G1, S07, mko_definition

Leaf basis: mko_definition

Combine every obligation to certify the original graph bipartite.







## Substeps and lemmas

No substeps in this guide.





## Reverse audits


- S08 · premise_audit · G1, S07, mko_definition — An edgeless graph may use(V,empty), but may not omit vertices.
- S07 · premise_audit · G1, S06, work — This odd-cycle refutation concerns the separate complete triangle, not the original graph.
- S06 · premise_audit · G1, S05, work — One invalid candidate cannot refute existence of a valid one.
- S05 · premise_audit · G1, S04, work — 0 and 2 may share a part because they are not adjacent.
- S04 · premise_audit · G1, S03, work — Vertex counts alone do not prove this edge obligation.
- S03 · premise_audit · G1, S02, work — Omitting an isolate would still invalidate the partition.
- S02 · premise_audit · G1, S01, work — A vertex cannot belong to both parts.
- S01 · premise_audit · G1, work — These are the only edges; no0-to 2 edge is implicit.





## Error controls and negative controls

All verticesAssign isolated 3 to a part.

Existential quantifierA valid witness proves existence; one failure does not prove nonexistence.


- Isolated 3 may be omitted. → reject — The union would no longer equal V.
- Failure of A' proves nonbipartiteness. → reject — A,B already form a valid partition.
- A triangle admits two parts. → reject — Alternation around three edges forces adjacent endpoints into the same part.





## Result and limitations

A={0,2,3}, B={1} certify the graph bipartite.







## Verification and source binding

2 declared checks for this guide; only the listed expressions are covered.


- source commit: b1b2f1dcf8c50d67a93fe52d95f8eef7b3abba9f
- adopted source SHA-256: bd3b9a767549e7cefb60cebc2278fb332f5bac033b84321bd0c2eb7004197c3c
- original source SHA-256: b94470821c9e899e02832a1b63f4ceaf9869bac586a0967c66175e03ad73bf37
- Lean: NOT_RUN · independent AI: SCOPED_LEAD_AND_BILINGUAL_CONTEXT_REVIEW

[Same-source full JSON (formulas, ASTs, controls and revision log)](https://ocme.evemisslab.com/data/derivations/coverage-20261021/guides/derivation-mko-bipartite-graph-01.json)