Teoria grafów

[kasienka16m]

Wykaż że jeśli H i K są podgrafami grafu G i grafy \(\displaystyle{ H \cup K}\)oraz \(\displaystyle{ H \cap K}\)są zdefiniowane w naturalny sposób, to rząd rozcięcia \(\displaystyle{ \partial}\) ma następujące własności:
a)\(\displaystyle{ 0 \le \partial (H) \le \left|E(H) \right|}\)
gdzie \(\displaystyle{ \left|E(H) \right|}\)jest liczbą krawędzi grafu H
b) jeśli H jest podgrafem K to \(\displaystyle{ \partial (H) \le \partial (K)}\)
\(\displaystyle{ c) \partial (H \cup K) + \partial (H \cap K) \le \partial (H)+ \partial (K)}\)