TY - JOUR
TI - A formal approach to Menger's theorem
AU - Bonacina, Roberta
AU - Misselbeck-Wessel, Daniel
TI - A formal approach to Menger's theorem
AB - Menger's graph theorem equates the minimum size of a separating set for non-adjacent vertices a and b with the maximum number of disjoint paths between a and b. By capturing separating sets as models of an entailment relation, we take a formal approach to Menger's result. Upon showing that inconsistency is characterised by the existence of suficiently many disjoint paths, we recover Menger's theorem by way of completeness.
VL - 2022
IS - Number 57
PY - 2022
SN - 0137-2904
C1 - 2084-2589
SP - 45
EP - 51
DO - 10.4467/20842589RM.22.003.16660
UR - https://ejournals.eu/en/journal/reports-on-mathematical-logic/article/a-formal-approach-to-mengers-theorem
KW - Disjoint paths
KW - separating set
KW - inductive definition
KW - entailment