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