定義1： 若能將無(wú)向圖G= 的頂點(diǎn)集V劃分成兩個(gè)子集 V1和V2（V1交V2為空集），使得G中任何一條邊的兩個(gè)端點(diǎn)一個(gè)屬于V1，另一個(gè)屬于V2，則稱(chēng)G為二部圖（也稱(chēng)偶圖），V1、V2稱(chēng)為互補(bǔ)頂點(diǎn)子集，此時(shí)可將G記成G= .
若V1中任一頂點(diǎn)與V2中每一個(gè)頂點(diǎn)均有且僅有一條邊相關(guān)聯(lián)，則稱(chēng)二部圖G為完全二部圖（或完全偶圖）。
定理1： 一個(gè)無(wú)向圖G=是二部圖當(dāng)且僅當(dāng)G中無(wú)奇數(shù)長(zhǎng)度的回路。
定義2： 設(shè)G=為無(wú)向圖，E*屬于E，若E*中任意兩條邊均不相鄰，則稱(chēng)E*為G中的匹配（或邊獨(dú)立集）。若在E*中再加入任何1條邊就都不是匹配了，則稱(chēng)E*為極大匹配。邊數(shù)最多的極大匹配稱(chēng) 匹配，匹配中的元素（邊）的個(gè)數(shù)稱(chēng)為G的匹配數(shù)。
設(shè)M為G中一個(gè)匹配。v屬于V（G），若存在M中的邊與v關(guān)聯(lián)，
則稱(chēng)v為M飽和點(diǎn)，否則稱(chēng)v為M非飽和點(diǎn)。若G中每個(gè)頂點(diǎn)都是M飽和點(diǎn)，則稱(chēng)M為G中完美匹配。
定義3： 設(shè)G=為一個(gè)二部圖，M為G中一個(gè)匹配，若|M|=min{|V1|,|V2|},則M為G中一個(gè)完備匹配，此時(shí)若|V1|<=|V2|，則稱(chēng)M為V1到V2的一個(gè)完備匹配。如果|V1|=|V2|，這時(shí)M為G中的完美匹配。
定理2：（Hall定理）設(shè)二部圖G=〈V1，V2，E〉，|V1|<=|V2|，G中存在從V1到V2的完備匹配當(dāng)且僅當(dāng)V1中任意k個(gè)頂點(diǎn)（k=1，2....，|V1|）至少鄰接V2中的k個(gè)頂點(diǎn)。
定理3：
由Hall定理容易證明下面定理：
1，V1中每個(gè)頂點(diǎn)至少關(guān)聯(lián)t（t>0）條邊；
2，V2中每個(gè)頂點(diǎn)至多關(guān)聯(lián)t條邊，則G中存在V1到V2的完備匹配。
Hall定理中的條件為“相異性條件”，定理3中的條件為“t條件”。
滿足t條件的二部圖，一定滿足相異性條件，事實(shí)上，由條件（1）可知，V1中k個(gè)頂點(diǎn)至少關(guān)聯(lián) kt條邊。由條件（2）可知，這 kt條邊至少關(guān)聯(lián)V2中的k個(gè)頂點(diǎn)，于是若G滿足t條件，則G一定滿足相異性條件，但反之不真。
若V1中任一頂點(diǎn)與V2中每一個(gè)頂點(diǎn)均有且僅有一條邊相關(guān)聯(lián)，則稱(chēng)二部圖G為完全二部圖（或完全偶圖）。
定理1： 一個(gè)無(wú)向圖G=是二部圖當(dāng)且僅當(dāng)G中無(wú)奇數(shù)長(zhǎng)度的回路。
定義2： 設(shè)G=為無(wú)向圖，E*屬于E，若E*中任意兩條邊均不相鄰，則稱(chēng)E*為G中的匹配（或邊獨(dú)立集）。若在E*中再加入任何1條邊就都不是匹配了，則稱(chēng)E*為極大匹配。邊數(shù)最多的極大匹配稱(chēng) 匹配，匹配中的元素（邊）的個(gè)數(shù)稱(chēng)為G的匹配數(shù)。
設(shè)M為G中一個(gè)匹配。v屬于V（G），若存在M中的邊與v關(guān)聯(lián)，
則稱(chēng)v為M飽和點(diǎn)，否則稱(chēng)v為M非飽和點(diǎn)。若G中每個(gè)頂點(diǎn)都是M飽和點(diǎn)，則稱(chēng)M為G中完美匹配。
定義3： 設(shè)G=為一個(gè)二部圖，M為G中一個(gè)匹配，若|M|=min{|V1|,|V2|},則M為G中一個(gè)完備匹配，此時(shí)若|V1|<=|V2|，則稱(chēng)M為V1到V2的一個(gè)完備匹配。如果|V1|=|V2|，這時(shí)M為G中的完美匹配。
定理2：（Hall定理）設(shè)二部圖G=〈V1，V2，E〉，|V1|<=|V2|，G中存在從V1到V2的完備匹配當(dāng)且僅當(dāng)V1中任意k個(gè)頂點(diǎn)（k=1，2....，|V1|）至少鄰接V2中的k個(gè)頂點(diǎn)。
定理3：
由Hall定理容易證明下面定理：
1，V1中每個(gè)頂點(diǎn)至少關(guān)聯(lián)t（t>0）條邊；
2，V2中每個(gè)頂點(diǎn)至多關(guān)聯(lián)t條邊，則G中存在V1到V2的完備匹配。
Hall定理中的條件為“相異性條件”，定理3中的條件為“t條件”。
滿足t條件的二部圖，一定滿足相異性條件，事實(shí)上，由條件（1）可知，V1中k個(gè)頂點(diǎn)至少關(guān)聯(lián) kt條邊。由條件（2）可知，這 kt條邊至少關(guān)聯(lián)V2中的k個(gè)頂點(diǎn)，于是若G滿足t條件，則G一定滿足相異性條件，但反之不真。