A formal approach to Menger's theorem
A formal approach to Menger's theorem
Author(s): Roberta Bonacina, Daniel Misselbeck-WesselSubject(s): Logic, Philosophy of Science
Published by: Wydawnictwo Uniwersytetu Jagiellońskiego
Keywords: Disjoint paths; separating set; inductive definition; entailment;
Summary/Abstract: 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.
Journal: Reports on Mathematical Logic
- Issue Year: 2022
- Issue No: 57
- Page Range: 45-51
- Page Count: 7
- Language: English