1258:
896:
1095:
733:
1271:
whose surplus equals the surplus of the entire graph (i.e., equals the minimum). The intersection and union of tight sets with non-empty intersection are tight; this follows from properties of lower-bounded submodular set functions.
335:
937:
if def(G) = |V| - 2 ν(G). Obviously, the strong Hall property implies the Hall property. Bipartite graphs have both of these properties, however there are classes of non-bipartite graphs that have these properties.
909:
whose deficiency equals the deficiency of the entire graph (i.e., equals the maximum). The intersection and union of tight sets are tight; this follows from properties of upper-bounded supermodular set functions.
653:
204:
1253:{\displaystyle \operatorname {sur} _{G}(X_{1}\cup X_{2})+\operatorname {sur} _{G}(X_{1}\cap X_{2})\leq \operatorname {sur} _{G}(X_{1})+\operatorname {sur} _{G}(X_{2})}
891:{\displaystyle \operatorname {def} _{G}(X_{1}\cup X_{2})+\operatorname {def} _{G}(X_{1}\cap X_{2})\geq \operatorname {def} _{G}(X_{1})+\operatorname {def} _{G}(X_{2})}
251:
1461:
1368:
1489:
70:
586:
117:
1526:
1043:
Note the restriction to non-empty subsets: without it, the surplus of all graphs would always be 0. Note also that:
404:
31:
452:. Moreover, using the notion of deficiency, it is possible to state a quantitative version of Hall's theorem:
372:
1068:
1487:
Beckenbach, Isabel; Borndörfer, Ralf (2018-10-01). "Hall's and Kőnig's theorem in graphs and hypergraphs".
1445:
1575:
706:
99:, which is formed by all vertices from 'V' that are connected by an edge to one or more vertices of
946:
1551:
1449:
1367:
Graphs with a positive surplus play an important role in the theory of graph structures; see the
1543:
1506:
1457:
1412:
1535:
1498:
1404:
449:
412:
27:
1471:
1467:
933:
has either a perfect matching or a vertex set with a positive deficiency. A graph has the
687:
214:
561:|. By Hall's marriage theorem, the new graph admits a matching in which all vertices of
35:
1569:
1555:
368:
913:
In a non-bipartite graph, the deficiency function is, in general, not supermodular.
23:
1408:
1392:
1502:
1374:
In a non-bipartite graph, the surplus function is, in general, not submodular.
1329:
is a bipartite graph with a positive surplus, such that deleting any edge from
330:{\displaystyle \mathrm {def} (G;X):=\max _{U\subseteq X}\mathrm {def} _{G}(U)}
1547:
1510:
1416:
941:
In particular, a graph has the strong Hall property if-and-only-if it is
1539:
1524:
Lovász, L. (1970-09-01). "A generalization of Kónig's theorem".
1456:, Annals of Discrete Mathematics, vol. 29, North-Holland,
565:
are matched. Now, restore the original graph by removing the
929:
if Hall's marriage theorem holds for that graph, namely, if
81:
in which no two vertices are connected by an edge. Let
648:{\displaystyle \nu (G)=|X|-\operatorname {def} (G;X),}
1098:
736:
589:
254:
199:{\displaystyle \mathrm {def} _{G}(U):=|U|-|N_{G}(U)|}
120:
535:, and connect every dummy vertex to all vertices of
1322:), the resulting graph has a non-negative surplus.
1295:satisfying the following property for every vertex
26:that is used to refine various theorems related to
1252:
890:
647:
329:
198:
1527:Acta Mathematica Academiae Scientiarum Hungaricae
1348:A bipartite graph has a positive surplus (w.r.t.
285:
945:- its maximum matching size equals its maximum
501:= def(G;X). This means that, for every subset
580:This theorem can be equivalently stated as:
8:
241:), is the maximum deficiency of a subset of
456:
422:X) > 0, it means that for some subsets
1241:
1225:
1209:
1193:
1177:
1164:
1148:
1132:
1119:
1103:
1097:
879:
863:
847:
831:
815:
802:
786:
770:
757:
741:
735:
613:
605:
588:
478:) admits a matching in which at most def(
312:
301:
288:
255:
253:
191:
176:
167:
159:
151:
133:
122:
119:
1383:
666:) is the size of a maximum matching in
539:. After the addition, for every subset
16:Refinement of perfect matching theorems
1352:) if-and-only-if it contains a forest
381:X) = 0, it means that for all subsets
340:Sometimes this quantity is called the
237:with respect to one of its parts (say
1015:is defined by the minimum surplus of
682:Properties of the deficiency function
7:
1482:
1480:
1440:
1438:
1436:
1434:
1432:
1430:
1428:
1426:
1311:and connect them to the vertices in
569:dummy vertices; this leaves at most
308:
305:
302:
262:
259:
256:
129:
126:
123:
14:
355:of the empty subset is 0, so def(
705:), the deficiency function is a
444:|. Hence, by the same theorem,
95:denote the set of neighbors of
1393:"Graphs and matching theorems"
1247:
1234:
1215:
1202:
1183:
1157:
1138:
1112:
885:
872:
853:
840:
821:
795:
776:
750:
639:
627:
614:
606:
599:
593:
324:
318:
278:
266:
192:
188:
182:
168:
160:
152:
145:
139:
1:
1409:10.1215/S0012-7094-55-02268-7
1067:), the surplus function is a
1369:Gallai–Edmonds decomposition
34:. This was first studied by
1391:Ore, Oystein (1955-12-01).
1291:;X) is the largest integer
1592:
1503:10.1016/j.disc.2018.06.013
1356:such that every vertex in
366:
1397:Duke Mathematical Journal
1337:X), then every vertex in
707:supermodular set function
1071:: for every two subsets
709:: for every two subsets
363:Deficiency and matchings
46:Definition of deficiency
38:. A related property is
1069:submodular set function
1007:The surplus of a graph
405:Hall's marriage theorem
32:Hall's marriage theorem
1287:) = 0, the number sur(
1275:For a bipartite graph
1267:subset is a subset of
1261:
1254:
1049:
1041:
1005:
905:subset is a subset of
899:
892:
649:
462:Every bipartite graph
331:
200:
73:of vertices, that is,
1255:
1091:
1051:In a bipartite graph
1045:
1025:
971:
893:
729:
650:
332:
201:
1490:Discrete Mathematics
1096:
935:strong Hall property
917:Strong Hall property
734:
587:
418:In contrast, if def(
252:
118:
65:be a graph, and let
1345:;X) + 1.
1031:X) := min sur
947:fractional matching
460: —
373:Tutte–Berge formula
342:critical difference
217:, with bipartition
30:in graphs, such as
1540:10.1007/BF01894789
1250:
888:
645:
531:dummy vertices to
458:
327:
299:
196:
1497:(10): 2753–2761.
448:does not admit a
284:
1583:
1560:
1559:
1521:
1515:
1514:
1484:
1475:
1474:
1442:
1421:
1420:
1388:
1360:has degree 2 in
1307:new vertices to
1259:
1257:
1256:
1251:
1246:
1245:
1230:
1229:
1214:
1213:
1198:
1197:
1182:
1181:
1169:
1168:
1153:
1152:
1137:
1136:
1124:
1123:
1108:
1107:
1011:w.r.t. a subset
897:
895:
894:
889:
884:
883:
868:
867:
852:
851:
836:
835:
820:
819:
807:
806:
791:
790:
775:
774:
762:
761:
746:
745:
654:
652:
651:
646:
617:
609:
461:
450:perfect matching
413:perfect matching
336:
334:
333:
328:
317:
316:
311:
298:
265:
205:
203:
202:
197:
195:
181:
180:
171:
163:
155:
138:
137:
132:
94:
64:
28:perfect matching
22:is a concept in
1591:
1590:
1586:
1585:
1584:
1582:
1581:
1580:
1566:
1565:
1564:
1563:
1523:
1522:
1518:
1486:
1485:
1478:
1464:
1454:Matching Theory
1444:
1443:
1424:
1390:
1389:
1385:
1380:
1341:has degree sur(
1317:
1237:
1221:
1205:
1189:
1173:
1160:
1144:
1128:
1115:
1099:
1094:
1093:
1084:
1077:
1034:
998:
986:
976:
955:
919:
875:
859:
843:
827:
811:
798:
782:
766:
753:
737:
732:
731:
722:
715:
688:bipartite graph
684:
672:matching number
585:
584:
552:
514:
492:
490:are unmatched.
459:
435:
394:
375:
365:
354:
300:
250:
249:
215:bipartite graph
172:
121:
116:
115:
111:is defined by:
87:
82:
77:is a subset of
71:independent set
51:
48:
17:
12:
11:
5:
1589:
1587:
1579:
1578:
1568:
1567:
1562:
1561:
1534:(3): 443–446.
1516:
1476:
1462:
1450:Plummer, M. D.
1446:Lovász, László
1422:
1403:(4): 625–639.
1382:
1381:
1379:
1376:
1333:decreases sur(
1315:
1249:
1244:
1240:
1236:
1233:
1228:
1224:
1220:
1217:
1212:
1208:
1204:
1201:
1196:
1192:
1188:
1185:
1180:
1176:
1172:
1167:
1163:
1159:
1156:
1151:
1147:
1143:
1140:
1135:
1131:
1127:
1122:
1118:
1114:
1111:
1106:
1102:
1082:
1075:
1047:def(G;X) = max
1032:
996:
982:
974:
969:is defined by:
954:
951:
918:
915:
887:
882:
878:
874:
871:
866:
862:
858:
855:
850:
846:
842:
839:
834:
830:
826:
823:
818:
814:
810:
805:
801:
797:
794:
789:
785:
781:
778:
773:
769:
765:
760:
756:
752:
749:
744:
740:
720:
713:
683:
680:
656:
655:
644:
641:
638:
635:
632:
629:
626:
623:
620:
616:
612:
608:
604:
601:
598:
595:
592:
548:
510:
486:) vertices of
454:
431:
390:
364:
361:
352:
338:
337:
326:
323:
320:
315:
310:
307:
304:
297:
294:
291:
287:
283:
280:
277:
274:
271:
268:
264:
261:
258:
207:
206:
194:
190:
187:
184:
179:
175:
170:
166:
162:
158:
154:
150:
147:
144:
141:
136:
131:
128:
125:
85:
47:
44:
15:
13:
10:
9:
6:
4:
3:
2:
1588:
1577:
1574:
1573:
1571:
1557:
1553:
1549:
1545:
1541:
1537:
1533:
1529:
1528:
1520:
1517:
1512:
1508:
1504:
1500:
1496:
1492:
1491:
1483:
1481:
1477:
1473:
1469:
1465:
1463:0-444-87916-1
1459:
1455:
1451:
1447:
1441:
1439:
1437:
1435:
1433:
1431:
1429:
1427:
1423:
1418:
1414:
1410:
1406:
1402:
1398:
1394:
1387:
1384:
1377:
1375:
1372:
1370:
1365:
1363:
1359:
1355:
1351:
1346:
1344:
1340:
1336:
1332:
1328:
1323:
1321:
1314:
1310:
1306:
1302:
1298:
1294:
1290:
1286:
1282:
1278:
1273:
1270:
1266:
1265:surplus-tight
1260:
1242:
1238:
1231:
1226:
1222:
1218:
1210:
1206:
1199:
1194:
1190:
1186:
1178:
1174:
1170:
1165:
1161:
1154:
1149:
1145:
1141:
1133:
1129:
1125:
1120:
1116:
1109:
1104:
1100:
1090:
1088:
1081:
1074:
1070:
1066:
1062:
1058:
1054:
1048:
1044:
1040:
1038:
1030:
1024:
1022:
1018:
1014:
1010:
1004:
1002:
994:
990:
985:
980:
970:
968:
964:
960:
952:
950:
948:
944:
939:
936:
932:
928:
927:Hall property
924:
916:
914:
911:
908:
904:
898:
880:
876:
869:
864:
860:
856:
848:
844:
837:
832:
828:
824:
816:
812:
808:
803:
799:
792:
787:
783:
779:
771:
767:
763:
758:
754:
747:
742:
738:
728:
726:
719:
712:
708:
704:
700:
696:
692:
689:
681:
679:
677:
673:
669:
665:
661:
642:
636:
633:
630:
624:
621:
618:
610:
602:
596:
590:
583:
582:
581:
578:
576:
572:
568:
564:
560:
556:
551:
546:
542:
538:
534:
530:
526:
522:
518:
513:
508:
504:
500:
496:
491:
489:
485:
481:
477:
473:
469:
465:
453:
451:
447:
443:
439:
434:
429:
425:
421:
416:
414:
410:
406:
403:|. Hence, by
402:
398:
393:
388:
384:
380:
374:
370:
369:Tutte theorem
362:
360:
358:
351:Note that def
349:
347:
343:
321:
313:
295:
292:
289:
281:
275:
272:
269:
248:
247:
246:
244:
240:
236:
232:
228:
224:
220:
216:
212:
185:
177:
173:
164:
156:
148:
142:
134:
114:
113:
112:
110:
106:
102:
98:
92:
88:
80:
76:
72:
68:
62:
58:
54:
45:
43:
41:
37:
33:
29:
25:
21:
1576:Graph theory
1531:
1525:
1519:
1494:
1488:
1453:
1400:
1396:
1386:
1373:
1366:
1361:
1357:
1353:
1349:
1347:
1342:
1338:
1334:
1330:
1326:
1324:
1319:
1312:
1308:
1304:
1303:: if we add
1300:
1296:
1292:
1288:
1284:
1280:
1276:
1274:
1268:
1264:
1262:
1092:
1086:
1079:
1072:
1064:
1060:
1056:
1052:
1050:
1046:
1042:
1036:
1028:
1026:
1020:
1016:
1012:
1008:
1006:
1000:
992:
988:
983:
981:) := |N
978:
972:
966:
962:
961:of a subset
958:
956:
942:
940:
934:
930:
926:
922:
920:
912:
906:
902:
900:
730:
724:
717:
710:
702:
698:
694:
690:
685:
675:
671:
670:(called the
667:
663:
659:
657:
579:
574:
573:vertices of
570:
566:
562:
558:
554:
549:
544:
540:
536:
532:
528:
524:
520:
516:
511:
506:
502:
498:
494:
493:
487:
483:
479:
475:
471:
467:
463:
455:
445:
441:
437:
432:
427:
423:
419:
417:
408:
400:
396:
391:
386:
382:
378:
376:
356:
350:
345:
341:
339:
242:
238:
234:
230:
226:
222:
218:
210:
208:
108:
104:
100:
96:
90:
83:
78:
74:
66:
60:
56:
52:
49:
39:
24:graph theory
19:
18:
1019:subsets of
577:unmatched.
107:of the set
36:Øystein Ore
1378:References
367:See also:
231:deficiency
105:deficiency
20:Deficiency
1556:121333106
1548:1588-2632
1511:0012-365X
1417:0012-7094
1279:with def(
1232:
1200:
1187:≤
1171:∩
1155:
1126:∪
1110:
1017:non-empty
870:
838:
825:≥
809:∩
793:
764:∪
748:
625:
619:−
591:ν
440:)| < |
411:admits a
293:⊆
165:−
1570:Category
1452:(1986),
995:| = −def
925:has the
921:A graph
359:X) ≥ 0.
209:Suppose
1472:0859549
959:surplus
953:Surplus
457:Theorem
377:If def(
40:surplus
1554:
1546:
1509:
1470:
1460:
1415:
991:)| − |
949:size.
943:stable
658:where
557:)| ≥ |
527:. Add
519:)| ≥ |
497:. Let
399:)| ≥ |
229:. The
103:. The
69:be an
1552:S2CID
903:tight
686:In a
495:Proof
213:is a
1544:ISSN
1507:ISSN
1458:ISBN
1413:ISSN
1027:sur(
957:The
547:, |N
509:, |N
430:, |N
389:, |N
371:and
50:Let
1536:doi
1499:doi
1495:341
1405:doi
1325:If
1299:in
1223:sur
1191:sur
1146:sur
1101:sur
1085:of
1055:= (
973:sur
965:of
861:def
829:def
784:def
739:def
723:of
693:= (
678:).
674:of
622:def
543:of
505:of
466:= (
426:of
385:of
348:.
344:of
286:max
233:of
55:= (
1572::
1550:.
1542:.
1532:21
1530:.
1505:.
1493:.
1479:^
1468:MR
1466:,
1448:;
1425:^
1411:.
1401:22
1399:.
1395:.
1371:.
1364:.
1335:G;
1263:A
1078:,
1063:,
1029:G;
1023::
901:A
716:,
701:,
523:|-
474:,
420:G;
415:.
407:,
379:G;
357:G;
282::=
245::
225:∪
221:=
149::=
59:,
42:.
1558:.
1538::
1513:.
1501::
1419:.
1407::
1362:F
1358:X
1354:F
1350:X
1343:G
1339:X
1331:G
1327:G
1320:x
1318:(
1316:G
1313:N
1309:X
1305:s
1301:X
1297:x
1293:s
1289:G
1285:X
1283:;
1281:G
1277:G
1269:X
1248:)
1243:2
1239:X
1235:(
1227:G
1219:+
1216:)
1211:1
1207:X
1203:(
1195:G
1184:)
1179:2
1175:X
1166:1
1162:X
1158:(
1150:G
1142:+
1139:)
1134:2
1130:X
1121:1
1117:X
1113:(
1105:G
1089::
1087:X
1083:2
1080:X
1076:1
1073:X
1065:E
1061:Y
1059:+
1057:X
1053:G
1039:)
1037:U
1035:(
1033:G
1021:X
1013:X
1009:G
1003:)
1001:U
999:(
997:G
993:U
989:U
987:(
984:G
979:U
977:(
975:G
967:V
963:U
931:G
923:G
907:X
886:)
881:2
877:X
873:(
865:G
857:+
854:)
849:1
845:X
841:(
833:G
822:)
817:2
813:X
804:1
800:X
796:(
788:G
780:+
777:)
772:2
768:X
759:1
755:X
751:(
743:G
727::
725:X
721:2
718:X
714:1
711:X
703:E
699:Y
697:+
695:X
691:G
676:G
668:G
664:G
662:(
660:ν
643:,
640:)
637:X
634:;
631:G
628:(
615:|
611:X
607:|
603:=
600:)
597:G
594:(
575:X
571:d
567:d
563:X
559:U
555:U
553:(
550:G
545:X
541:U
537:X
533:Y
529:d
525:d
521:U
517:U
515:(
512:G
507:X
503:U
499:d
488:X
484:X
482:;
480:G
476:E
472:Y
470:+
468:X
464:G
446:G
442:U
438:U
436:(
433:G
428:X
424:U
409:G
401:U
397:U
395:(
392:G
387:X
383:U
353:G
346:G
325:)
322:U
319:(
314:G
309:f
306:e
303:d
296:X
290:U
279:)
276:X
273:;
270:G
267:(
263:f
260:e
257:d
243:X
239:X
235:G
227:Y
223:X
219:V
211:G
193:|
189:)
186:U
183:(
178:G
174:N
169:|
161:|
157:U
153:|
146:)
143:U
140:(
135:G
130:f
127:e
124:d
109:U
101:U
97:U
93:)
91:U
89:(
86:G
84:N
79:V
75:U
67:U
63:)
61:E
57:V
53:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.