# Question 12496: Conjoin Bijectivity with the Complete Adjacency-Iff Audit [Return to catalogue page 63](https://ocme.evemisslab.com/en/questions/page/63/) [← Question derivation index](https://ocme.evemisslab.com/en/questions/) · [Original question batch](https://ocme.evemisslab.com/en/practice/batch-20261013-advance-20261026-r06-graph-isomorphism-foundations/#q-20261013-advance-20261026-r06-graph-isomorphism-0071) This teaching derivation has second-context AI mathematical and bilingual semantic review, limited to the model and assumptions stated in this question. It has no human review or new Lean proof and does not promote the original question or MKO to Canonical truth. R0023-12496 · q-20261013-advance-20261026-r06-graph-isomorphism-0071 ## Original question and givens Use complete simple undirected graphs on Fin(6)={0,…,5} with source edges=[[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]], target edges=[[0, 1], [1, 5], [3, 5], [2, 3], [2, 4], [0, 2]] and complete vertex map=[0, 1, 5, 3, 2, 4] in source-label order. Loops and duplicate undirected edges are forbidden. Isomorphism requires both bijectivity and adjacency iff on every unordered pair, including nonedges; neither obligation replaces the other. Give (n,mapping,bijective?,bad [a,b,source adjacent?,mapped target adjacent?] records,isomorphism?). - G001 — Use complete simple undirected graphs on Fin(6)={0,…,5} with source edges=[[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]], target edges=[[0, 1], [1, 5], [3, 5], [2, 3], [2, 4], [0, 2]] and complete vertex map=[0, 1, 5, 3, 2, 4] in source-label order. Loops and duplicate undirected edges are forbidden. Isomorphism requires both bijectivity and adjacency iff on every unordered pair, including nonedges; neither obligation replaces the other. Give (n,mapping,bijective?,bad [a,b,source adjacent?,mapped target adjacent?] records,isomorphism?). ## Definition and scope Use the original question domain, assumptions and cited MKO definitions. This item has second-context mathematical and bilingual review, with the model, answer and every arithmetic step independently recomputed from the original parameters; the source question remains a candidate. - [mko-graph-isomorphism](https://ocme.evemisslab.com/en/mko/mko-graph-isomorphism/) ## Step-by-step derivation S001 · impliesBefore source graph:carrier Fin(6);raw undirected edges=[[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]] After canonical simple edges=[[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]];loops and repeated undirected edges absent Conditions: none Normalize each edge with its smaller endpoint first,then sort.Reversed duplicates remain invalid rather than being silently removed.Preserve every isolated vertex. Step identifiers and dependenciesRule: complete_simple_graph_canonical_edges · Uses: G001 S002 · impliesBefore target graph:carrier Fin(6);raw undirected edges=[[0, 1], [1, 5], [3, 5], [2, 3], [2, 4], [0, 2]] After canonical simple edges=[[0, 1], [0, 2], [1, 5], [2, 3], [2, 4], [3, 5]];loops and repeated undirected edges absent Conditions: none Normalize each edge with its smaller endpoint first,then sort.Reversed duplicates remain invalid rather than being silently removed.Preserve every isolated vertex. Step identifiers and dependenciesRule: complete_simple_graph_canonical_edges · Uses: G001, S001 S003 · impliesBefore complete mapping=[0, 1, 5, 3, 2, 4];target label=0 After source fiber=[0];exactly one=Yes Conditions: none For a complete total map between equally sized finite carriers,every target needs exactly one preimage.Typedness alone is not bijectivity. Step identifiers and dependenciesRule: finite_vertex_map_each_target_fiber · Uses: G001, S002 S004 · impliesBefore complete mapping=[0, 1, 5, 3, 2, 4];target label=1 After source fiber=[1];exactly one=Yes Conditions: none For a complete total map between equally sized finite carriers,every target needs exactly one preimage.Typedness alone is not bijectivity. Step identifiers and dependenciesRule: finite_vertex_map_each_target_fiber · Uses: G001, S003 S005 · impliesBefore complete mapping=[0, 1, 5, 3, 2, 4];target label=2 After source fiber=[4];exactly one=Yes Conditions: none For a complete total map between equally sized finite carriers,every target needs exactly one preimage.Typedness alone is not bijectivity. Step identifiers and dependenciesRule: finite_vertex_map_each_target_fiber · Uses: G001, S004 S006 · impliesBefore complete mapping=[0, 1, 5, 3, 2, 4];target label=3 After source fiber=[3];exactly one=Yes Conditions: none For a complete total map between equally sized finite carriers,every target needs exactly one preimage.Typedness alone is not bijectivity. Step identifiers and dependenciesRule: finite_vertex_map_each_target_fiber · Uses: G001, S005 S007 · impliesBefore complete mapping=[0, 1, 5, 3, 2, 4];target label=4 After source fiber=[5];exactly one=Yes Conditions: none For a complete total map between equally sized finite carriers,every target needs exactly one preimage.Typedness alone is not bijectivity. Step identifiers and dependenciesRule: finite_vertex_map_each_target_fiber · Uses: G001, S006 S008 · impliesBefore complete mapping=[0, 1, 5, 3, 2, 4];target label=5 After source fiber=[2];exactly one=Yes Conditions: none For a complete total map between equally sized finite carriers,every target needs exactly one preimage.Typedness alone is not bijectivity. Step identifiers and dependenciesRule: finite_vertex_map_each_target_fiber · Uses: G001, S007 S009 · impliesBefore n=6;all target fibers=[[0], [1], [4], [3], [5], [2]] After bijective=Yes;empty carrier uses unique empty map Conditions: none The unique empty map is bijective on empty carriers.This checks the mapping obligation only,not adjacency. Step identifiers and dependenciesRule: whole_bijection_including_empty_carrier · Uses: G001, S008 S010 · impliesBefore source unordered pair=[0, 1];mapped pair=[0, 1] After source adjacent=Yes;target adjacent=Yes;iff=Yes Conditions: none Compare both truth values on every unordered source pair,including source nonedges.A collision maps to a target diagonal,which is not an edge in a simple graph.Retain the full adjacency failure list even if bijectivity fails. Step identifiers and dependenciesRule: graph_every_edge_and_nonedge_iff · Uses: G001, S009 S011 · impliesBefore source unordered pair=[0, 2];mapped pair=[0, 5] After source adjacent=No;target adjacent=No;iff=Yes Conditions: none Compare both truth values on every unordered source pair,including source nonedges.A collision maps to a target diagonal,which is not an edge in a simple graph.Retain the full adjacency failure list even if bijectivity fails. Step identifiers and dependenciesRule: graph_every_edge_and_nonedge_iff · Uses: G001, S010 S012 · impliesBefore source unordered pair=[0, 3];mapped pair=[0, 3] After source adjacent=No;target adjacent=No;iff=Yes Conditions: none Compare both truth values on every unordered source pair,including source nonedges.A collision maps to a target diagonal,which is not an edge in a simple graph.Retain the full adjacency failure list even if bijectivity fails. Step identifiers and dependenciesRule: graph_every_edge_and_nonedge_iff · Uses: G001, S011 S013 · impliesBefore source unordered pair=[0, 4];mapped pair=[0, 2] After source adjacent=No;target adjacent=Yes;iff=No Conditions: none Compare both truth values on every unordered source pair,including source nonedges.A collision maps to a target diagonal,which is not an edge in a simple graph.Retain the full adjacency failure list even if bijectivity fails. Step identifiers and dependenciesRule: graph_every_edge_and_nonedge_iff · Uses: G001, S012 S014 · impliesBefore source unordered pair=[0, 5];mapped pair=[0, 4] After source adjacent=No;target adjacent=No;iff=Yes Conditions: none Compare both truth values on every unordered source pair,including source nonedges.A collision maps to a target diagonal,which is not an edge in a simple graph.Retain the full adjacency failure list even if bijectivity fails. Step identifiers and dependenciesRule: graph_every_edge_and_nonedge_iff · Uses: G001, S013 S015 · impliesBefore source unordered pair=[1, 2];mapped pair=[1, 5] After source adjacent=Yes;target adjacent=Yes;iff=Yes Conditions: none Compare both truth values on every unordered source pair,including source nonedges.A collision maps to a target diagonal,which is not an edge in a simple graph.Retain the full adjacency failure list even if bijectivity fails. Step identifiers and dependenciesRule: graph_every_edge_and_nonedge_iff · Uses: G001, S014 S016 · impliesBefore source unordered pair=[1, 3];mapped pair=[1, 3] After source adjacent=No;target adjacent=No;iff=Yes Conditions: none Compare both truth values on every unordered source pair,including source nonedges.A collision maps to a target diagonal,which is not an edge in a simple graph.Retain the full adjacency failure list even if bijectivity fails. Step identifiers and dependenciesRule: graph_every_edge_and_nonedge_iff · Uses: G001, S015 S017 · impliesBefore source unordered pair=[1, 4];mapped pair=[1, 2] After source adjacent=No;target adjacent=No;iff=Yes Conditions: none Compare both truth values on every unordered source pair,including source nonedges.A collision maps to a target diagonal,which is not an edge in a simple graph.Retain the full adjacency failure list even if bijectivity fails. Step identifiers and dependenciesRule: graph_every_edge_and_nonedge_iff · Uses: G001, S016 S018 · impliesBefore source unordered pair=[1, 5];mapped pair=[1, 4] After source adjacent=No;target adjacent=No;iff=Yes Conditions: none Compare both truth values on every unordered source pair,including source nonedges.A collision maps to a target diagonal,which is not an edge in a simple graph.Retain the full adjacency failure list even if bijectivity fails. Step identifiers and dependenciesRule: graph_every_edge_and_nonedge_iff · Uses: G001, S017 S019 · impliesBefore source unordered pair=[2, 3];mapped pair=[5, 3] After source adjacent=Yes;target adjacent=Yes;iff=Yes Conditions: none Compare both truth values on every unordered source pair,including source nonedges.A collision maps to a target diagonal,which is not an edge in a simple graph.Retain the full adjacency failure list even if bijectivity fails. Step identifiers and dependenciesRule: graph_every_edge_and_nonedge_iff · Uses: G001, S018 S020 · impliesBefore source unordered pair=[2, 4];mapped pair=[5, 2] After source adjacent=No;target adjacent=No;iff=Yes Conditions: none Compare both truth values on every unordered source pair,including source nonedges.A collision maps to a target diagonal,which is not an edge in a simple graph.Retain the full adjacency failure list even if bijectivity fails. Step identifiers and dependenciesRule: graph_every_edge_and_nonedge_iff · Uses: G001, S019 S021 · impliesBefore source unordered pair=[2, 5];mapped pair=[5, 4] After source adjacent=No;target adjacent=No;iff=Yes Conditions: none Compare both truth values on every unordered source pair,including source nonedges.A collision maps to a target diagonal,which is not an edge in a simple graph.Retain the full adjacency failure list even if bijectivity fails. Step identifiers and dependenciesRule: graph_every_edge_and_nonedge_iff · Uses: G001, S020 S022 · impliesBefore source unordered pair=[3, 4];mapped pair=[3, 2] After source adjacent=Yes;target adjacent=Yes;iff=Yes Conditions: none Compare both truth values on every unordered source pair,including source nonedges.A collision maps to a target diagonal,which is not an edge in a simple graph.Retain the full adjacency failure list even if bijectivity fails. Step identifiers and dependenciesRule: graph_every_edge_and_nonedge_iff · Uses: G001, S021 S023 · impliesBefore source unordered pair=[3, 5];mapped pair=[3, 4] After source adjacent=No;target adjacent=No;iff=Yes Conditions: none Compare both truth values on every unordered source pair,including source nonedges.A collision maps to a target diagonal,which is not an edge in a simple graph.Retain the full adjacency failure list even if bijectivity fails. Step identifiers and dependenciesRule: graph_every_edge_and_nonedge_iff · Uses: G001, S022 S024 · impliesBefore source unordered pair=[4, 5];mapped pair=[2, 4] After source adjacent=Yes;target adjacent=Yes;iff=Yes Conditions: none Compare both truth values on every unordered source pair,including source nonedges.A collision maps to a target diagonal,which is not an edge in a simple graph.Retain the full adjacency failure list even if bijectivity fails. Step identifiers and dependenciesRule: graph_every_edge_and_nonedge_iff · Uses: G001, S023 S025 · impliesBefore mapping bijective=Yes;all bad adjacency pairs=[[0, 4, No, Yes]] After adjacency iff=No;specified map isomorphism=No Conditions: none Bijectivity and complete adjacency iff are separate obligations.Neither alone certifies isomorphism.This audits the declared map rather than searching all maps. Step identifiers and dependenciesRule: graph_bijection_and_adjacency_separate_conjunction · Uses: G001, S024 ## Reverse checks - S025 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S024 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S023 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S022 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S021 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S020 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S019 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S018 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S017 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S016 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S015 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S014 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S013 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S012 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S011 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S010 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S009 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S008 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S007 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S006 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S005 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S004 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S003 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S002 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S001 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. ## Result (6, [0, 1, 5, 3, 2, 4], Yes, [[0, 4, No, Yes]], No) The full substitutions and premise checks give the original answer; source identity,format and status are unchanged. ## This question review and source binding Review date: 2026-10-26 Original questions, answers, step expressions, numeric ASTs and historical records are retained. Source candidate labels remain historical and are not overwritten as formal proof. Source hashes and review receipts - input commit: 0f7be61e2c22317a4075561dc822c87d881a50db - original question SHA-256: 89f315bd129ed9b44c555ed0d2cb11c5e3087f1fb817d8e8312471b5054ce889 - candidate record SHA-256: 22c55187cd233bd195e3934ca37af0e54e9020392250cb75e431206820a0e331 - semantic review receipt SHA-256: f783e81f44ff0faa13dbf948657e9187244a59a809ebdf96f22cca24966649ff - question-first witness SHA-256: 49a50ed0550be55124d6562260c2ccf4fa6d3f316d7ad9d0d32174400e362e18 - Lean: NOT_RUN · human review: NOT_PERFORMED [Same-source full JSON](https://ocme.evemisslab.com/data/question-derivations/questions/q-20261013-advance-20261026-r06-graph-isomorphism-0071.json)