Перевіримо виконання аксіом незалежності:
- Порожня множина є ациклічним, а значить входить в.
- Очевидно, що будь-який підграф лісу, так само є лісом, а значить входить в внаслідок своєї ациклічності.
- У графі як мінімум дві компоненти пов'язаності, інакше був би остовне деревом і не існувало б ациклического безлічі з більшою потужністю. Припустимо в не існує ребра, що з'єднує дві різні компоненти пов'язаності з, значить будь-яка компонента пов'язаності з цілком вершинно-входить в яку-небудь компоненту з. Розглянемо будь-яку компоненту пов'язаності з, у неї вершин і ребер. Тепер розглянемо всі компоненти пов'язаності з, вершинно-входять в, нехай їх штук, тоді сумарна кількість ребер з одно, що не перевищує (кількість ребер в). Підсумуємо нерівність за всіма компонентами пов'язаності з і отримаємо, що суперечить умові. Значить припущення не вірно, і в існує шукане ребро з різних компонент пов'язаності.
[Ред] Матричний матроід
Нехай - векторний простір над тілом, нехай набір векторів з простору є носієм. Елементами незалежного безлічі даного матроід є безлічі лінійно незалежних векторів з набору. Тоді, називається матричним матроід (англ. Vector matroid)
Складемо матрицю інцидентності для графа. Рядки цієї матриці відповідають вершинам графа, а стовпці - ребрах.
- Якщо -е ребро є петля, инцидентная -ої вершини, то.
- Якщо -а вершина инцидентна -ому ребру, то
- інакше
Необхідно довести, що якщо ми візьмемо безліч ребер, то безліч стовпців матриці інцидентності, відповідне обраним ребрам, лінійно-незалежно, і навпаки, якщо ми візьмемо лінійно-незалежне безліч стовпців, то відповідне йому безліч ребер, що не буде утворювати циклу. Доведемо еквівалентну твердження: стовпці лінійно-залежні тоді і тільки тоді, коли відповідні їм ребра графа містять цикл.
Нехай стовпці лінійно-залежні, доведемо, що відповідні ребра графа містять цикл.
Якщо деякі стовпці матриці лінійно-залежні, то серед них можна виділити стовпці з нульовою сумою. Є два варіанта:
- Серед обраних стовпців є нульовою, тоді у відповідному безлічі ребер є петля, тобто цикл.
- У нас є стовпець, який є сумою інших стовпців. Цьому колонки відповідає ребро. Почнемо з вершини переходити по іншим ребрам з (по кожному ребру проходимо тільки один раз), в результаті ми прийдемо в вершину, так для інших вершин у нас обов'язково буде парне число виходять з них ребер, бо інакше на позиції цієї вершини в стовпці була б одиниця (а одиниці у нас тільки на позиціях і). Таким чином ми показали, що існує два шляхи між вершинами і (той який ми побудували і шлях по ребру), значить в обраному безлічі ребер є цикл.
Нехай на безлічі ребер є цикл, доведемо лінійну-залежність відповідних стовпців.
Якщо серед даної множини ребер є петля, то відповідний їй стовпець буде нульовим (з побудови матриці інцидентності), він і забезпечує лінійну-залежність всього набору векторів.
Якщо петлі немає, то розглянемо стовпці, що відповідають ребрам простого циклу. Будь-яка рядок матриці містить в цих стовпцях рівно 2 одиниці. Тому сума по модулю зазначених стовпців дорівнює нульовому стовпцю, що означає лінійну залежність вихідного безлічі стовпців.