Множину вершин [ребрів] графа 0 позначають V(G) [E(G)]. Множина підграфів графа G є непересічними, якщо жодні з них не мають спільного ребра. Остовний підграф графа G — це підграф графа G, який включає всі вершини графа G; охоплення
G є остовним підграфом G, який є деревом.
Два шляхи не перетинаються якщо вони не мають спільного краю. Наприклад: мережі зв'язку.
Коли два остовних дерева одного графа не мають жодного спільного ребра тоді він відомий як охоплююче дерево, що не перетинає ребра (EDST). А floor(n/2) – це кількість EDST, які можливі з n вершинами.
Проте даний граф завжди матиме принаймні одне остовне дерево. Ребра в остовному дереві називаються "краї гілок, тоді як ребра, які не входять до охоплюючого дерева, називаються «ребрами циклу». Цей тип графа допомагає знайти мінімальну кількість ребер, необхідних для з’єднання всіх вершин у графі.
→ Реберний підграф: Розглянемо два підграфи G1 = (V1, E1) і G2 = (V2, E2) і граф G = (V, E). Якщо множина перетину E1(G1) і E2(G2) дорівнює нулю, то G1 і G2 є реберно непересічними підграфами G. Це означає, що між G1 і G2 немає спільних ребер.
Ми можемо використовувати алгоритм максимального потоку знайти k непересічних, s-t шляхів у графі. Усередині будь-якого потоку значення k на графі одиничної ємності є k непересічних шляхів. Іншими словами, значення потоку дає нам кількість непересічних шляхів.