Вершинами графа $L_n$ являются отрезки координатной плоскости [(0, i); (n + 1, i)] и [(i, 0); (i, n + 1)](для целых i от 1 до n, всего 2n вершин), в квадратных скобках указаны координаты концов отрезка.Две вершины графа (то есть отрезки) соединены ребром тогда и только тогда, когда эти отрезкипересекаются. Найдите максимальный размер независимого множества в графе $ L_n $.

Предположим, что в независимом множестве $L_n$ есть хотя бы n + 1 элемент. Тогда найдется хотя
бы 1 отрезок 1-го типа и 1 отрезок 2-го типа, которые находятся в этом множестве. Пусть отрезок
1-го типа имеет координаты [(0;k);(n + 1;k)], а отрезок 2-го типа имеет координаты [(m;0);(m;n + 1)].
Тогда эти отрезки пересекаются в точке (m;k), тогда в независимом множестве $L_n$ эти отрезки будут соединены ребром – противоречие. Тогда в независимом множестве $L_n$ есть не более n элементов.
Пример на n элементов: возьмем n отрезков 1-го типа. Они не пересекаются, соответственно в независимом множестве $L_n$ они не соединены ребром.