519:
271:
Most direct proofs consider a more general statement to allow proving it by induction. It is also convenient to use definitions that include some degenerate cases. The following proof for undirected graphs works without change for directed graphs or multi-graphs, provided we take
943:. The directed versions of the theorem immediately imply undirected versions: it suffices to replace each edge of an undirected graph with a pair of directed edges (a digon).
897:
The directed edge version of the theorem easily implies the other versions. To infer the directed graph vertex version, it suffices to split each vertex
1182:
Menger's theorem holds for infinite graphs, and in that context it applies to the minimum cut between any two elements that are either vertices or
1005:
1495:
48:
263:
All these statements in both edge and vertex versions remain true in directed graphs (when considering directed paths).
1485:
52:
954:
are often correctness proofs for max flow algorithms. It is also a special case of the still more general (strong)
1256:
951:
947:
236:
56:
1490:
1261:
136:
40:
1402:
212:
112:
1447:
1418:
1392:
1183:
955:
60:
1195:
518:
1465:
1439:
1410:
1369:
1332:
1299:
1266:
1009:
1406:
1219:
978:
959:
39:
is equal to the maximum number of disjoint paths that can be found between any pair of
1337:
1320:
1304:
1287:
1479:
1451:
1199:
1422:
1430:
Halin, R. (1974). "A note on Menger's theorem for infinite locally finite graphs".
1237:-paths and a separating set which consists of exactly one vertex from each path in
32:
24:
20:
965:
A formulation that for finite digraphs is equivalent to the above formulation is:
1191:
180:
59:, which is a weighted, edge version, and which in turn is a special case of the
44:
1414:
184:
1470:
1055:. This results in a bipartite graph, whose one side consists of the vertices
1374:
1357:
1383:
Aharoni, Ron; Berger, Eli (2008). "Menger's theorem for infinite graphs".
1012:, the minimal size of a cover is equal to the maximal size of a matching.
946:
The directed edge version in turn follows from its weighted variant, the
92:
770:. Because of its size, the endpoints of the paths in it must be exactly
1443:
1251:
36:
1074:
of the same size. In particular, exactly one endpoint of each edge of
996:-separating set that consists of exactly one vertex from each path in
1397:
402:. This variant implies the above vertex-connectivity statement: for
1432:
517:
438:-separator, and removing the end vertices in a set of independent
1206:. It is equivalent to Menger's theorem when the graph is finite.
250:
vertices) if and only if every pair of vertices has at least
246:
vertices and it remains connected after removing fewer than
1321:"Menger's theorem for graphs containing no infinite paths"
1004:
In this version the theorem follows in fairly easily from
483:, we may assume by induction that the Theorem holds for
103:(the minimum number of edges whose removal disconnects
406:
in the previous section, apply the current theorem to
91:
two distinct vertices. Then the size of the minimum
146:edges) if and only if every pair of vertices has
142:(it remains connected after removing fewer than
1158:-separating set, that every path in the family
823:, with paths whose starting points are exactly
195:(the minimum number of vertices, distinct from
1134:in the original graph consist of all vertices
1066:Applying Kőnig's theorem we obtain a matching
1015:This is done as follows: replace every vertex
472:-connector consisting of single-vertex paths.
370:-separator is equal to the maximum size of an
1218:be sets of vertices in a (possibly infinite)
211:) is equal to the maximum number of pairwise
163:statement of Menger's theorem is as follows:
111:) is equal to the maximum number of pairwise
8:
1202:, and before being proved was known as the
851:is internally disjoint from every path in
75:version of Menger's theorem is as follows:
307:. We allow a path with a single vertex in
1396:
1373:
1336:
1303:
1198:was originally a conjecture proposed by
426:. Then a set of vertices disconnecting
1278:
183:vertices. Then the size of the minimum
1471:Menger's Theorems and Max-Flow-Min-Cut
1150:. It is straightforward to check that
299:, and no internal vertices neither in
1187:
254:internally disjoint paths in between.
55:of a graph. It is generalized by the
7:
452:Induction on the number of edges in
1162:contains precisely one vertex from
227:A consequence for the entire graph
1039:; additionally, include the edges
915:, with all ingoing edges going to
14:
1325:European Journal of Combinatorics
1288:"Short proof of Menger's theorem"
570:together with either endpoint of
171:be a finite undirected graph and
83:be a finite undirected graph and
1059:, and the other of the vertices
977:be sets of vertices in a finite
922:, all outgoing edges going from
1358:"Zur allgemeinen Kurventheorie"
283:(not necessarily disjoint), an
150:edge-disjoint paths in between.
929:, and an additional edge from
744:). Hence it has size at least
522:An illustration for the proof.
422:, the neighboring vertices of
327:vertices (which may intersect
127:The implication for the graph
1:
1338:10.1016/S0195-6698(83)80012-2
1305:10.1016/S0012-365X(00)00088-1
1225:. Then there exists a family
984:. Then there exists a family
598:alone is too small to be an
203:, whose removal disconnects
1466:A Proof of Menger's Theorem
1190:). The following result of
878:and one path going through
460:with no edges, the minimum
1512:
291:with a starting vertex in
131:is the following version:
1415:10.1007/s00222-008-0157-3
1118:-paths composed of edges
673:, and consider a minimum
213:internally disjoint paths
1496:Theorems in graph theory
1385:Inventiones Mathematicae
1257:k-vertex-connected graph
1019:in the original digraph
948:max-flow min-cut theorem
870:by concatenating paths (
566:, since if it was less,
434:is the same thing as an
57:max-flow min-cut theorem
35:, the size of a minimum
1204:Erdős–Menger conjecture
858:, and we can define an
620:be the later vertex of
382:−1 vertices disconnect
366:The minimum size of an
276:to mean directed path.
16:Theorem in graph theory
1375:10.4064/fm-10-1-96-115
1286:Göring, Frank (2000).
1262:k-edge-connected graph
1166:, and every vertex in
695:is not reachable from
523:
378:In other words, if no
61:strong duality theorem
1356:Menger, Karl (1927).
1319:Aharoni, Ron (1983).
624:on such a path. Then
550:contains a vertex of
521:
468:, which is itself an
450:Proof of the Theorem:
279:For sets of vertices
63:for linear programs.
1292:Discrete Mathematics
1170:lies on a path from
800:-separator has size
394:disjoint paths from
295:, a final vertex in
1407:2009InMat.176....1A
1047:that is neither in
862:-connector of size
833:Furthermore, since
804:, and there is an
780:Similarly, letting
613:be the earlier and
503:-connector of size
499:, then there is an
495:-separator of size
390:, then there exist
311:and zero edges. An
161:vertex-connectivity
155:Vertex connectivity
113:edge-disjoint paths
1486:Graph connectivity
1444:10.1007/BF02993589
1130:belongs to M. Let
1114:be the set of all
901:into two vertices
650:is reachable from
631:is reachable from
574:would be a better
538:of size less than
524:
242:(it has more than
1098:and all vertices
1043:for every vertex
1031:, and every edge
737:-path intersects
240:-vertex-connected
231:is this version:
73:edge-connectivity
67:Edge connectivity
1503:
1455:
1426:
1400:
1379:
1377:
1343:
1342:
1340:
1316:
1310:
1309:
1307:
1298:(1–3): 295–296.
1283:
1267:Vertex separator
1023:by two vertices
844:, every path in
748:. By induction,
542:, so that every
442:-paths gives an
355:vertex-disjoint
29:Menger's theorem
1511:
1510:
1506:
1505:
1504:
1502:
1501:
1500:
1476:
1475:
1462:
1429:
1382:
1355:
1352:
1350:Further reading
1347:
1346:
1318:
1317:
1313:
1285:
1284:
1280:
1275:
1248:
1180:
1178:Infinite graphs
1138:such that both
1010:bipartite graph
1006:Kőnig's theorem
960:linear programs
956:duality theorem
941:
934:
927:
920:
913:
906:
895:
887:
883:
856:
849:
838:
828:
817:
809:
797:
789:
785:
775:
764:
757:
742:
733:(because every
715:
704:
693:
678:
670:
666:
648:
629:
618:
611:
526:Otherwise, let
511:, and hence in
479:having an edge
269:
261:
259:Directed graphs
157:
140:-edge-connected
69:
31:says that in a
17:
12:
11:
5:
1509:
1507:
1499:
1498:
1493:
1491:Network theory
1488:
1478:
1477:
1474:
1473:
1468:
1461:
1460:External links
1458:
1457:
1456:
1427:
1380:
1351:
1348:
1345:
1344:
1311:
1277:
1276:
1274:
1271:
1270:
1269:
1264:
1259:
1254:
1247:
1244:
1243:
1242:
1186:of the graph (
1179:
1176:
1174:, as desired.
1002:
1001:
992:-paths and an
939:
932:
925:
918:
911:
904:
894:
891:
885:
881:
874:paths through
854:
847:
836:
826:
815:
807:
795:
787:
783:
773:
762:
755:
740:
729:-separator in
717:-separator in
713:
702:
691:
676:
668:
664:
646:
627:
616:
609:
602:-separator of
590:-path through
578:-separator of
558:. The size of
534:-separator of
491:has a minimal
464:-separator is
376:
375:
351:is a union of
268:
265:
260:
257:
256:
255:
225:
224:
156:
153:
152:
151:
125:
124:
68:
65:
23:discipline of
15:
13:
10:
9:
6:
4:
3:
2:
1508:
1497:
1494:
1492:
1489:
1487:
1484:
1483:
1481:
1472:
1469:
1467:
1464:
1463:
1459:
1453:
1449:
1445:
1441:
1437:
1433:
1428:
1424:
1420:
1416:
1412:
1408:
1404:
1399:
1394:
1390:
1386:
1381:
1376:
1371:
1367:
1363:
1359:
1354:
1353:
1349:
1339:
1334:
1330:
1326:
1322:
1315:
1312:
1306:
1301:
1297:
1293:
1289:
1282:
1279:
1272:
1268:
1265:
1263:
1260:
1258:
1255:
1253:
1250:
1249:
1245:
1240:
1236:
1232:
1228:
1224:
1221:
1217:
1213:
1209:
1208:
1207:
1205:
1201:
1197:
1193:
1189:
1185:
1177:
1175:
1173:
1169:
1165:
1161:
1157:
1153:
1149:
1145:
1141:
1137:
1133:
1129:
1125:
1121:
1117:
1113:
1109:
1105:
1101:
1097:
1093:
1089:
1086:all vertices
1085:
1081:
1077:
1073:
1069:
1064:
1062:
1058:
1054:
1050:
1046:
1042:
1038:
1034:
1030:
1026:
1022:
1018:
1013:
1011:
1007:
999:
995:
991:
987:
983:
980:
976:
972:
968:
967:
966:
963:
961:
957:
953:
949:
944:
942:
935:
928:
921:
914:
907:
900:
892:
890:
888:
877:
873:
869:
865:
861:
857:
850:
843:
839:
831:
829:
822:
818:
811:
803:
799:
791:
778:
776:
769:
765:
758:
751:
747:
743:
736:
732:
728:
724:
720:
716:
709:
705:
698:
694:
687:
683:
679:
672:
659:
657:
654:but not from
653:
649:
642:
638:
635:but not from
634:
630:
623:
619:
612:
605:
601:
597:
593:
589:
585:
581:
577:
573:
569:
565:
561:
557:
553:
549:
545:
541:
537:
533:
529:
520:
516:
514:
510:
506:
502:
498:
494:
490:
486:
482:
478:
473:
471:
467:
463:
459:
455:
451:
447:
445:
441:
437:
433:
429:
425:
421:
417:
413:
409:
405:
401:
397:
393:
389:
385:
381:
373:
369:
365:
362:
361:
360:
358:
354:
350:
346:
342:
338:
334:
330:
326:
322:
318:
314:
310:
306:
302:
298:
294:
290:
287:is a path in
286:
282:
277:
275:
266:
264:
258:
253:
249:
245:
241:
239:
234:
233:
232:
230:
222:
218:
214:
210:
206:
202:
198:
194:
190:
186:
182:
178:
174:
170:
166:
165:
164:
162:
154:
149:
145:
141:
139:
134:
133:
132:
130:
122:
118:
114:
110:
106:
102:
98:
94:
90:
86:
82:
78:
77:
76:
74:
66:
64:
62:
58:
54:
50:
49:characterizes
46:
42:
38:
34:
30:
26:
22:
1435:
1431:
1398:math/0509397
1388:
1384:
1365:
1361:
1331:(3): 201–4.
1328:
1324:
1314:
1295:
1291:
1281:
1238:
1234:
1230:
1229:of disjoint
1226:
1222:
1215:
1211:
1203:
1181:
1171:
1167:
1163:
1159:
1155:
1151:
1147:
1143:
1139:
1135:
1131:
1127:
1123:
1119:
1115:
1111:
1107:
1103:
1099:
1095:
1091:
1087:
1083:
1079:
1075:
1071:
1070:and a cover
1067:
1065:
1060:
1056:
1052:
1048:
1044:
1040:
1036:
1035:by the edge
1032:
1028:
1024:
1020:
1016:
1014:
1003:
997:
993:
989:
988:of disjoint
985:
981:
974:
970:
964:
945:
937:
930:
923:
916:
909:
902:
898:
896:
893:Other proofs
879:
875:
871:
867:
863:
859:
852:
845:
841:
840:disconnects
834:
832:
824:
820:
813:
805:
801:
793:
792:, a minimum
781:
779:
771:
767:
760:
753:
752:contains an
749:
745:
738:
734:
730:
726:
722:
718:
711:
707:
700:
696:
689:
685:
681:
674:
662:
660:
655:
651:
644:
640:
636:
632:
625:
621:
614:
607:
603:
599:
595:
591:
587:
586:there is an
583:
579:
575:
571:
567:
563:
559:
555:
554:or the edge
551:
547:
543:
539:
535:
531:
527:
525:
512:
508:
504:
500:
496:
492:
488:
484:
480:
476:
474:
469:
465:
461:
457:
453:
449:
448:
446:-connector.
443:
439:
435:
431:
427:
423:
419:
415:
411:
407:
403:
399:
395:
391:
387:
383:
379:
377:
371:
367:
363:
356:
352:
348:
345:AB-connector
344:
340:
339:contains no
336:
335:) such that
332:
328:
324:
320:
316:
313:AB-separator
312:
308:
304:
300:
296:
292:
288:
284:
280:
278:
273:
270:
262:
251:
247:
243:
237:
228:
226:
220:
216:
208:
204:
200:
196:
192:
188:
176:
172:
168:
160:
158:
147:
143:
137:
128:
126:
120:
116:
108:
104:
100:
96:
88:
84:
80:
72:
70:
53:connectivity
47:in 1927, it
43:. Proved by
33:finite graph
28:
25:graph theory
21:mathematical
18:
1438:: 111–114.
1391:(1): 1–62.
1192:Ron Aharoni
812:-connector
759:-connector
725:is also an
710:is also an
680:-separator
374:-connector.
267:Short proof
235:A graph is
181:nonadjacent
135:A graph is
45:Karl Menger
1480:Categories
1368:: 96–115.
1362:Fund. Math
1273:References
1200:Paul Erdős
1196:Eli Berger
1188:Halin 1974
1146:belong to
1126:such that
889:). Q.E.D.
343:-path. An
185:vertex cut
1452:120915644
1082:. Add to
786:= S ∪ {v
661:Now, let
546:-path in
319:is a set
1423:15355399
1246:See also
819:of size
766:of size
688:. Since
667:= S ∪ {v
643:, while
594:, since
562:must be
420:B = N(y)
416:A = N(x)
364:Theorem:
359:-paths.
347:of size
315:of size
93:edge cut
41:vertices
1403:Bibcode
1252:Gammoid
1220:digraph
1008:: in a
979:digraph
721:. Then
414:} with
404:x,y ∈ G
303:nor in
285:AB-path
281:A,B ⊂ G
37:cut set
19:In the
1450:
1421:
1154:is an
1110:. Let
1102:, for
1090:, for
1078:is in
952:proofs
950:. Its
606:. Let
456:. For
1448:S2CID
1419:S2CID
1393:arXiv
1128:u'v''
1041:v'v''
1037:u'v''
641:G−S−e
582:. In
530:be a
487:. If
466:A ∩ B
386:from
309:A ∩ B
215:from
115:from
1214:and
1210:Let
1194:and
1184:ends
1142:and
1051:nor
973:and
969:Let
958:for
475:For
430:and
331:and
274:path
207:and
199:and
191:and
187:for
179:two
175:and
167:Let
159:The
107:and
99:and
95:for
87:and
79:Let
71:The
51:the
1440:doi
1411:doi
1389:176
1370:doi
1333:doi
1300:doi
1296:219
1144:v''
1140:v'
1122:in
1106:in
1100:b'
1094:in
1088:a''
1061:v''
1057:v'
1029:v''
1025:v'
936:to
880:e=v
872:k−1
866:in
750:G−e
701:G−S
699:in
686:G−e
684:in
639:in
584:G−S
564:k-1
536:G−e
509:G−e
507:in
489:G−e
485:G−e
424:x,y
412:x,y
398:to
337:G−S
323:of
219:to
119:to
1482::
1446:.
1436:40
1434:.
1417:.
1409:.
1401:.
1387:.
1366:10
1364:.
1360:.
1327:.
1323:.
1294:.
1290:.
1156:AB
1120:uv
1116:AB
1096:A,
1063:.
1033:uv
1027:,
994:AB
990:AB
962:.
908:,
860:AB
830:.
777:.
754:AS
735:AB
727:AB
712:AS
706:,
675:AS
658:.
600:AB
588:AB
576:AB
544:AB
532:AB
515:.
501:AB
493:AB
470:AB
462:AB
444:AB
440:xy
436:AB
418:,
410:−{
372:AB
368:AB
357:AB
341:AB
27:,
1454:.
1442::
1425:.
1413::
1405::
1395::
1378:.
1372::
1341:.
1335::
1329:4
1308:.
1302::
1241:.
1239:P
1235:B
1233:-
1231:A
1227:P
1223:G
1216:B
1212:A
1172:P
1168:Q
1164:Q
1160:P
1152:Q
1148:C
1136:v
1132:Q
1124:D
1112:P
1108:B
1104:b
1092:a
1084:C
1080:C
1076:M
1072:C
1068:M
1053:B
1049:A
1045:v
1021:D
1017:v
1000:.
998:P
986:P
982:G
975:B
971:A
940:2
938:v
933:1
931:v
926:2
924:v
919:1
917:v
912:2
910:v
905:1
903:v
899:v
886:2
884:v
882:1
876:S
868:G
864:k
855:2
853:C
848:1
846:C
842:G
837:1
835:S
827:2
825:S
821:k
816:2
814:C
810:B
808:2
806:S
802:k
798:B
796:2
794:S
790:}
788:2
784:2
782:S
774:1
772:S
768:k
763:1
761:C
756:1
746:k
741:1
739:S
731:G
723:T
719:G
714:1
708:T
703:1
697:A
692:2
690:v
682:T
677:1
671:}
669:1
665:1
663:S
656:A
652:B
647:2
645:v
637:B
633:A
628:1
626:v
622:e
617:2
615:v
610:1
608:v
604:G
596:S
592:e
580:G
572:e
568:S
560:S
556:e
552:S
548:G
540:k
528:S
513:G
505:k
497:k
481:e
477:G
458:G
454:G
432:y
428:x
408:G
400:B
396:A
392:k
388:B
384:A
380:k
353:k
349:k
333:B
329:A
325:k
321:S
317:k
305:B
301:A
297:B
293:A
289:G
252:k
248:k
244:k
238:k
229:G
223:.
221:y
217:x
209:y
205:x
201:y
197:x
193:y
189:x
177:y
173:x
169:G
148:k
144:k
138:k
129:G
123:.
121:y
117:x
109:y
105:x
101:y
97:x
89:y
85:x
81:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
