Достаточность

От противного: пусть существует непланарный граф, который не содержит подграфов, гомеоморфных или . Пусть — такой граф с наименьшим возможным числом рёбер, не содержащий изолированных вершин.

Билет 10

Вопрос 1

1. Определение 1.1. Бинарное отношение a на множестве X называется отношением поряд ка, если оно транзитивно:

и антисимметрично:

2. Частично упорядоченное множество — математическое понятие, которое формализует интуитивные идеи упорядочивания, расположения в определенной последовательности и т. п. Неформально говоря, множество частично упорядочено, если указано, какие элементы следуют(больше и т. п.) за какими

3. Линейно упорядоченное множество или цепь ― частично упорядоченное множество, в котором для любых двух элементов a и b имеет место или .

Вопрос 2