(а)поток с големина k е сума от п съгласувани елементарни потоци, k от които са по цикли, а останалите – по вериги; (б) ако е допустим потокс големина k от vW до w=V\W, за произволна факторизация {W,}на V, то ; (в)N(V,A) има капацитет, ако са дадени две целочислени функции и върху А: 0(а)(а), aA.
Ако поне един допустим поток от vW до w=V\W за произволна факторизация {W,} на V, то , където и са съответно: (а) горната и долната граница на капацитета на ; (б) максималната и минималната граница на големините на допустимите потоци; (в) минималната и максималната граница на големините на допустимите потоци.
Теоремата за max поток и min разрез гласи: (а) максималната от големините на потоците от v до w е равна на минималния от капацитетите на разрезите между v и w; (б) минималната от големините на потоците от v до w е равна на максималния от капацитетите на разрезите между v и w; (в) максималният поток от v до w е равен на минималния разрез между v и w.
Кое от следните твърдения не е формулировка на теорема на Менгер за свързаността на графа G: (а) min брой върхове, разделящи различни несъседни върхове, е равен на max брой независими вериги между тях; (б) min брой ребра, разделящи различни върхове, е равен на max брой вериги без общи ребра между тях; (в) min брой разрези, разделящи различни върхове, е равен на max брой независими компоненти между тях.
Сдвояване в граф без примки G=(V,E) е множество: (а)М Е, ако в М съседни ребра; (б)М Е, ако в М 2 ребра са съседни; (в)М V, ако в М съседни върхове.
Теоремата на Кьониг-Хол за сватбите гласи: (а) В пълен двуделен граф G(V1,V2;Г) пълно сдвояване на V1 с V2 ,SV; (б) В двуделен граф G(V1,V2;Г) пълно сдвояване на V1 с V2 ,SV; (в) В двуделен граф G(V1,V2;Г) пълно сдвояване на V1 с V2 , SV.
За прост двуделен граф G(V1,V2;Г) с дефицитне е вярно, че: (а) min брой върхове на опората е равен на max брой дъги на сдвояването; (б) числото на външната устойчивост на G е (G)=; (в) max брой дъги на сдвояване е .
В унгарския алгоритъм за построяване на максимално сдвояване се използва еквивалентността на следните твърдения: (а) сдвояването М е максимално в простия двуделен граф G(V1,V2;Г) път от М+ в М – в графа (М,); (б) сдвояването М е максимално в графа G сдвояването с по-голяма мощност в G; (в) сдвояването М е максимално в простия двуделен граф G(V1,V2;Г) редуващи се вериги от силни и слаби дъги, съединяващи два различни ненаситени върха.
Граф G=(V,Е) има 1-фактор (а) броят на нечетните компоненти на подграфа G'[V\S], SV, е равен на S (мощността на S); (б) броят на четните компоненти на подграфа G'[V\S], SV, е поне S; (в) броят на нечетните компоненти на подграфа G'[V\S], SV, е най-много S.
Задачата за забранените подграфи е задача от вида: (а) да се определи минималния брой ребра в един п-граф, съдържащ граф F; (б) да се определи максималния брой ребра в един п-граф, несъдържащ граф F; (в) да се определи броя ребра в един п-граф, непринадлежащи на подграф F.
Екстремален граф на дадено нестрого неравенство за числова характеристика на клас от графи е: (а) графът с екстремален брой ребра в класа графи с тази характеристика; (б) граф, за който е изпълнено съответното равенство; (в) най-големият възможен граф с тази характеристика.
Ако G е п-граф, който не съдържа път с дължина k, то размерът на G е най-много (k–1)п/2 и екстремалните графи на това неравенство са: (а) графи на Мур; (б) свързани графи с всички блокове свързани k-графи; (в) графи с компоненти пълни k-графи.
Теоремата на Туран за пълните графи гласи: (а) Максималният брой ребра в п-граф, несъдържащ пълен r-граф е равен на броят на ребрата на пълен (r–1)-делен п-граф; (б) Графът на Туран Тr–1(п) има върха в k-тия си клас; (в) Броят на ребра на пълен (r–1)-делен п-граф е равен на размера на графа на Туран Тr–1(п).
Задачата на Заранкиевич е задача: (а) аналогична на теоремата на Туран в класа на равнинните графи; (б) за определяне на z(m,n;s,t) – максималния брой ребра на двуделен граф с m върха в първия и n върха във втория клас, ако той не съдържа пълен двуделен граф с s върха в първия и t върха във втория клас, където и ; (в) за определяне на z(m,n;s,t) – максималния брой ребра на двуделен граф с m върха в първия и n върха във втория клас, съдържащ пълен двуделен граф с s върха в първия и t върха във втория клас, където и .
Формулата на Ойлер за свързан равнинен граф с n върха, m ребра и f области е: (а)n–m+f=2; (б)m–n+f=2; (в)n+m–f=2.
Не е вярно, че: (а) графите на Понтрягин-Куратовски са равнинни; (б) графът на Понтрягин-Куратовски от I тип е пълният граф от ред 5; (в) графът на Понтрягин-Куратовски от II тип е пълният двуделен граф с 3 върха в единия клас и 3 върха в другия клас.
Кое от следните НДУ за равнинност на граф Gне е вярно: (а)G не съдържа подграф, изоморфен с точност до връх от степен 2 на един от графите K5и K3,3; (б)G съдържа база от цикли и един допълнителен цикъл, такъв че тази съвкупност от цикли да съдържа точно 2 пъти ребро на G; (в)G да има спрегнат граф.
Дуален граф на G е граф , получен от G чрез еднозначно съпоставяне: (а) на област на G – връх на , като се запазва релацията съседство; (б) на ребро на G – връх на , като се запазва релацията съседство; (в) на връх на G – връх на , като се запазва релацията съседство.
Многостенен граф е правилен, ако: (а) е хомогенен и дуалният му граф е също хомогенен; (б) негов връх има една и съща степен; (в) може да се отъждестви с изпъкнал многостен в евклидовото пространство.
Не е вярно, че: (а) единствените нетривиални правилни многостенни графи са 5; (б) тетраедърът е дуален сам на себе си; (в) кубът е дуален на додекаедъра, а октаедърът – на икосаедъра.
k-оцветяване на върховете на граф G=(V,E) наричаме: (а) функция с: V{1,2,…,k}, такава че множество с–1(j) е вътрешно устойчиво; (б) функция с: V{1,2,…,k}, такава че всички множества с–1(j) са различни; (в) биективна функция с: V{1,2,…,k}.
Ако за всички породени подграфи Н на G, тогава за хроматичното число на G имаме: (а) ; (б) ; (в) .
Ако графът Gсъдържа пълен подграф K, без който G се разпада на компоненти Н1, Н2,…, то за хроматичните числа на G и на породените подграфи Gi =K+Hi, i=1,2,… имаме: (а) ; (б) ; (в) .
Ако G е свързан граф с максимална степен max и G не е нито пълен граф, нито цикъл с нечетна дължина, тогава според теоремата на Брукс: (а) ; (б) ; (в) .
Ако за два съседни върха a и b на граф G са получени от G два графа – G' чрез свързване на a и b и G'' чрез отъждествяване на a и b, тогава: (а) хроматичното число на G е по-голямото между хроматичните числа на G'и на G''; (б) броят на оцветяванията на G е сумата от оцветяванията на G'и на G''; (в) съответствието между оцветяванията на G, при които a и b са оцветени еднакво и оцветяванията на G' е взаимно еднозначно.
Според теоремата на Визинг хроматичният клас на граф G е: (а) или max(G) или max(G)+1; (б) най-много max(G); (в) най-малко max(G)+1.
Всеки равнинен граф е: (а) 5-оцветим; (б) 4-оцветим; (в) 3-оцветим.
Броят на цветовете, необходими за оцветяване на граф върху ориентируема повърхнина от род е най-много: (а); (б); (в) .