Связность

Докажите теорему 2.1: каждый маршрут в графе между $v$ и $w$ содержит путь между $v$ и $w$, а каждый ориентированный маршрут из $v$ в $w$ в орграфе содержит ориентированный путь из $v$ в $w$.

Докажите теорему 2.2: если $A$ — матрица смежности простого графа $G=(V, E)$, где $V= \left\{ 1,2, \ldots , n\right\}$, то элемент $(i-j)$ в $k$-й степени матрицы $A$ равен числу различных маршрутов длины $k$ между вершинами $i$ и $j$. В частности, диагональный элемент $(i-i)$ в $A^{2}$ равен степени вершины $i$ для каждого $i$. (См. решённую задачу 2.2.)

Если рёбра графа помечены как $e_{i}(i=1,2, \ldots , m)$, а множество путей между двумя вершинами $v$ и $w$ помечено как $p_{i}(i=1,2, \ldots , k)$, то $\mathbf{v}, \mathbf{w}$-матрицей путей называется $k \times m$ двоичная матрица $P_{u v}$, в которой элемент $(i, j)$, соответствующий пути $p_{i}$, равен 1, если $p_{i}$ содержит ребро $e_{j}$, и 0 в противном случае. Постройте матрицу путей между вершинами 1 и 3 на рис. 2-2.

Пусть $B$ — матрица инцидентности простого графа $G=(V, E)$, в котором $V=\left\{ 1,2, \ldots , n\right\} , E= \left\{ e_{1}, e_{2}, \ldots , e_{m}\right\}$, а пути между вершиной $i$ и вершиной $j$ помечены как $p_{1}, p_{2}, \ldots , p_{k}$. Если $P$ — матрица путей $(i, j)$, то (двоичное) произведение $B P^{T}$ является двоичной матрицей $S$, в которой ненулевыми являются только элементы в $i$-й и $j$-й строках. (Умножение двоичных матриц здесь производится по модулю 2.)

Проверьте утверждение задачи 2.4, рассмотрев матрицу путей на рис. 2-2.

Если множество рёбер простого графа помечено $E=\left\{ e_{1}, e_{2}, \ldots , e_{m}\right\}$, а множество циклов помечено $\left\{ C_{1}, C_{2}, \ldots , C_{k}\right\}$, циклической матрицей графа называется двоичная матрица $k \times m$, определённая следующим образом: $C$. В строке, соответствующей $i$-му циклу $C_{i}$, элемент $(i, j)$ равен 1 тогда и только тогда, когда $e_{j}$ является ребром в $\mathrm{C}_{i}$. Постройте циклическую матрицу графа на рис. 2-3.

Пусть $B$ — матрица инцидентности простого графа $G=(V, E)$, где $V=\left\{ 1,2, \ldots , n\right\} , E= \left\{ e_{1}, e_{2}, \ldots , e_{m}\right\}$, а циклы в $G$ помечены $C_{1}, C_{2}, \ldots , C_{k}$. Если $C$ — циклическая матрица $k \times m$, то (двоичное) матричное произведение $B C^{T}$ и (двоичное) матричное произведение $C B^{T}$ являются нулевыми матрицами. (Умножение двоичных матриц здесь производится по модулю 2.)

Проверьте утверждение задачи 2.7, рассмотрев циклическую матрицу на рис. 2-3.

Покажите, что граф $G$ является двудольным тогда и только тогда, когда каждая компонента $G$ двудольна.

Докажите теорему 2.3: простой граф с тремя или более вершинами является двудольным тогда и только тогда, когда он не содержит нечётных циклов.

Докажите теорему 2.4: для любого графа $G$ выполняется $\kappa (G) \leq \lambda (G) \leq \delta (G)$.

Приведите граф, для которого неравенство, установленное в задаче 2.11, строгое.

Матрица называется вполне унимодулярной (TU) матрицей, если определитель каждой квадратной подматрицы равен -1, 0 или 1. Покажите, что каждый элемент TU-матрицы равен -1, 0 или 1, но обратное неверно.

Покажите, что матрица $A=\left[a_{i j}\right]$, в которой каждый элемент равен -1, 0 или 1, является TU-матрицей, если она удовлетворяет следующим двум условиям: (i) ни один столбец не может иметь более двух ненулевых элементов, и (ii) множество $I$ строк матрицы можно разбить на множества $I_{1}$ и $I_{2}$ так, что если $a_{i j}$ и $a_{k j}$ — два ненулевых элемента в столбце $j$, строка $i$ и строка $k$ принадлежат одному и тому же подмножеству разбиения тогда и только тогда, когда они имеют противоположные знаки.

Покажите, что следующие матрицы являются TU-матрицами:

Покажите, что граф является двудольным тогда и только тогда, когда его матрица инцидентности является вполне унимодулярной матрицей.

Наименьшее число цветов, необходимое для раскраски вершин графа так, чтобы каждая вершина получила уникальный цвет и никакие две смежные вершины не получили одинаковый цвет, называется хроматическим числом (или вершинным хроматическим числом) графа. Покажите, что граф двудолен тогда и только тогда, когда его хроматическое число равно двум.

Покажите, что следующие утверждения эквивалентны для простого графа $G$:

Предположим, каждое множество в семействе подмножеств конечного множества представлено вершиной. Две вершины, представляющие два различных подмножества, принадлежащих семейству, соединяются ребром, если у них есть хотя бы один общий элемент. Построенный таким образом простой граф называется графом пересечений семейства подмножеств данного множества. Постройте граф пересечений семейства подмножеств множества $X=\left\{ 1,2, \ldots , 10\right\}$ с семейством $\left\{ A, B, C, D, E, F\right\}$, где $A=\left\{ 1,3,5,7,9\right\} , B= \left\{ 2,4,6,8,10\right\} , C=\left\{ 1,2,3\right\} , D=\left\{ 4,5,6,8,9\right\} , E=\left\{ 5,6,7,9\right\}$ и $F=\left\{ 4,6,10\right\}$.

Покажите, что каждый простой граф (изоморфен) является графом пересечений некоторого семейства подмножеств конечного множества.

Число пересечений $\omega (G)$ графа $G$ — это минимальное число элементов множества $X$, такого что $G$ является графом пересечений семейства подмножеств $X$. Покажите, что число пересечений связного графа не может превышать его размер.

Постройте:

Покажите, что число пересечений связного графа не менее чем с четырьмя вершинами равно его размеру тогда и только тогда, когда он не содержит треугольников.

Найдите число пересечений $K_{n}$, где $n>1$.

Граф пересечений конечного семейства открытых интервалов вещественной прямой называется интервальным графом. Покажите, что циклический граф с $n$ вершинами (изоморфен) интервальному графу только при $n=3$.

Покажите, что:

Граф $G$ называется хордальным графом, если в каждом цикле $C$ графа $G$ найдётся ребро (принадлежащее $G$), соединяющее две несмежные (в $C$) вершины. Покажите, что каждый интервальный граф является хордальным графом.

Покажите, что граф $G$ хордален тогда и только тогда, когда $C_{n}$ не является порождённым подграфом $G$ ни для какого $n>3$.

Приведите пример хордального графа, который не является интервальным графом.

Граф $G=(V, E)$ называется графом безразличия, если для каждого положительного числа $\delta$ существует отображение $f$ из $V$ в множество вещественных чисел, такое что $\left|f(v)-f(w)\right|<\delta$ тогда и только тогда, когда $v$ и $w$ смежны. Покажите, что граф на рис. 2-14 является графом безразличия.

Fig. 2-14

Покажите, что каждый граф безразличия является интервальным графом.

Построив пример, покажите, что интервальный граф не обязательно является графом безразличия.

Покажите, что каждый граф безразличия является интервальным графом, каждый интервальный граф является хордальным графом, а каждый хордальный граф является графом пересечений.

Интервальный граф называется единичным интервальным графом, если длина открытого интервала, соответствующего вершине, одинакова для каждой вершины. Покажите, что граф является графом безразличия тогда и только тогда, когда он является единичным интервальным графом.

Орграф $D$ называется транзитивным орграфом, если существует дуга из $u$ в $v$ всякий раз, когда существует дуга из $u$ в $w$ и существует дуга из $w$ в $v$, для любого набора трёх различных вершин $u, v$ и $w$ в $D$. Простой граф $G$ называется транзитивно ориентируемым графом (или графом сравнимости), если $G$ имеет ориентацию $D$, являющуюся транзитивным орграфом. Покажите, что дополнение интервального графа является транзитивно ориентируемым графом.

Найдите транзитивную ориентацию для дополнения интервального графа $K_{1,3}$.

Покажите, что если дополнение $G$ транзитивно ориентируемо, отсюда не следует, что $G$ — интервальный граф, построив соответствующий пример.

Пусть $G=(V, E)$ — простой граф хотя бы с одним ребром. Рёберным графом $\boldsymbol {L}(\boldsymbol {G})$ (также известным как граф пересечений рёбер, присоединённый граф, производный граф или граф-образ рёбер) графа $G$ называется граф $(W, F)$, где существует взаимно однозначное соответствие $\phi$ из $E$ в $W$, такое что между $\phi (e)$ и $\phi \left(e^{\prime }\right)$ существует ребро тогда и только тогда, когда рёбра $e$ и $e^{\prime }$ имеют общую вершину. Постройте рёберный граф графа $K_{4}$.

Найдите рёберный граф графа, изображённого на рис. 2-18(a).

Покажите, что рёберный граф $G=(V, E)$ является графом пересечений семейства подмножеств прямого произведения $V \times V$.

Если $v$ — вершина рёберного графа $L(G)$, соответствующая ребру, соединяющему вершину $x$ и вершину $y$ в $G$, найдите степень $v$ в $L(G)$.

Найдите порядок и размер $L\left(K_{n}\right)$.

Найдите порядок и размер рёберного графа $L(G)$ простого графа $G$ с $n$ вершинами и $m$ рёбрами.

Пусть $G$ — простой граф с пятью вершинами, степени которых равны 1, 2, 3, 3 и 3. Найдите число вершин и рёбер в $L(G)$.

Найдите рёберный граф:

Покажите, что не существует графа $G$, для которого $L(G)=K_{1.3}$.

Постройте пример, показывающий, что если $L(G)$ и $L(H)$ изоморфны, отсюда не следует, что $G$ и $H$ изоморфны.

Покажите, что:

Пусть $X$ — множество всех вершин и рёбер графа $G$ с $n$ вершинами и $m$ рёбрами. Построим граф $T(G)=(X, F)$, в котором два элемента $x$ и $y$ соединены ребром, если:

Покажите, что граф является деревом тогда и только тогда, когда между каждой парой вершин графа существует единственный путь.

Покажите, что граф является деревом тогда и только тогда, когда он связен и каждое его ребро является мостом.

Покажите, что граф с $n$ вершинами является деревом тогда и только тогда, когда он связен и имеет $(n-1)$ рёбер.

Покажите, что граф с $n$ вершинами является деревом тогда и только тогда, когда он ацикличен и имеет $(n-1)$ рёбер.

Покажите, что граф $G$ является деревом тогда и только тогда, когда он ацикличен и, всякий раз когда произвольные две вершины в $G$ соединяются ребром, полученный расширенный граф $G^{\prime }$ имеет ровно один цикл.

Покажите, что граф $G$ является деревом тогда и только тогда, когда он связен и, всякий раз когда произвольные две вершины в $G$ соединяются ребром, полученный расширенный граф $G^{\prime }$ имеет ровно один цикл.

Докажите теорему 2.5: следующие утверждения эквивалентны для графа $G$ с $n$ вершинами.

1. $G$ — дерево.

2. Между каждой парой вершин в $G$ существует единственный путь.

3. $G$ связен, и каждое ребро в $G$ является мостом.

4. $G$ связен и имеет $(n-1)$ рёбер.

5. $G$ ацикличен и имеет $(n-1)$ рёбер.

6. $G$ ацикличен, и всякий раз, когда две произвольные несмежные вершины в $G$ соединяются ребром, полученный расширенный граф $G^{\prime }$ имеет единственный цикл.

7. $G$ связен, и всякий раз, когда две произвольные несмежные вершины в $G$ соединяются ребром, полученный расширенный граф имеет единственный цикл.

Докажите теорему 2.7: граф связен тогда и только тогда, когда у него есть остовное дерево.

Докажите теорему 2.8: пусть $G$ — простой граф с $n$ вершинами. Если остовный подграф $H$ удовлетворяет любым двум из следующих трёх свойств, он будет удовлетворять и третьему свойству. (i) $H$ связен. (ii) $H$ имеет $(n-1)$ рёбер. (iii) $H$ ацикличен.

Покажите, что если граф несвязен, его дополнение связно.

Вершина степени 1 в графе называется концевой вершиной (или висячей вершиной, или крайней вершиной). Покажите, что каждое дерево порядка два или более имеет не менее двух концевых вершин.

Покажите, что вектор $\mathrm{d}=\left[\begin{array}{llll}d_{1} & d_{2} & \ldots & d_{n}\end{array}\right]$ положительных целых чисел, где $d_{1} \leq d_{2} \leq \ldots \leq d_{n}$, является вектором степеней дерева с $n$ вершинами тогда и только тогда, когда $d_{1}+d_{2}+\cdots +d_{n}=2(n-1)$.

Докажите теорему 2.6: центр дерева является либо одноэлементным множеством, состоящим из единственной вершины, либо множеством, состоящим из двух смежных вершин.

Путь $P$ между двумя различными вершинами связного графа $G$ называется диаметральным путём, если в $G$ нет другого пути, длина которого больше длины $P$. Покажите, что:

Дерево, имеющее ровно одну вершину $v$ степени 2, в котором степень каждой неконцевой вершины (кроме $v$) равна 3, называется двоичным деревом, а корнем двоичного дерева называется единственная вершина степени 2. Покажите, что число вершин в двоичном дереве нечётно.

Покажите, что число концевых вершин в двоичном дереве с $n$ вершинами равно $(n+1) / 2$.

Покажите, что если $T$ — дерево с $n$ вершинами, а $G$ — граф с $\delta (G) \geq (n-1)$, то $T$ изоморфно подграфу $G$.

Покажите, что дерево с $n$ вершинами изоморфно подграфу дополнения циклического графа с $(n+2)$ вершинами.

Граф называется унициклическим, если он содержит ровно один циклический подграф. Покажите, что если в графе с $n$ вершинами и $m$ вершинами выполняются любые два из следующих условий, третье условие также выполняется:

Покажите, что каждому помеченному дереву с $n$ вершинами соответствует единственный вектор $s=\left[\begin{array}{llll}s_{1} & s_{2} & \cdots & s_{n-2}\end{array}\right]$, где $s_{i} \in N=\left\{ 1,2, \ldots , n\right\}$ для $i=1,2, \ldots ,(n-2)$.

Найдите единственный вектор, соответствующий помеченному дереву, изображённому на рис. 2-19.

Fig. 2-19

Покажите, что каждому вектору $s$ с $(n-2)$ компонентами, каждая из которых является элементом $N= \left\{ 1,2, \ldots , n\right\}$, соответствует единственное помеченное дерево с $n$ вершинами.

Постройте единственное помеченное дерево, соответствующее вектору $s=\begin{array}{llllllllll}1 & 4 & 2 & 2 & 4 & 3 & 3 & 3 & 4 & 4\end{array}$ ].

Докажите теорему 2.9 (теорема Кэли): число различных помеченных деревьев с $n$ вершинами равно $n^{n-2}$, что также равно числу остовных деревьев в $K_{n}$

Ориентированное дерево $T$, в котором существует единственная вершина $v$ с полустепенью захода 0, а полустепень захода каждой другой вершины равна 1, называется древовидностью (арборесценцией) с корнем в $v$. Найдите число различных помеченных древовидностей с $n$ вершинами.

Дерево с $n$ вершинами называется деревом с помеченными рёбрами, если каждому ребру присвоено уникальное положительное целое число от 1 до $(n-1)$. Покажите, что число различных деревьев с помеченными рёбрами, имеющих $(n-1)$ помеченных рёбер и $n$ непомеченных вершин, равно $n^{n-3}$.

Пусть $G$ — неориентированный граф с $n$ помеченными вершинами и $m$ помеченными рёбрами. Придадим каждому ребру произвольную ориентацию, и пусть $A$ — матрица инцидентности полученного орграфа. Покажите, что:

Пусть произвольная матрица инцидентности $A$ связного графа $G=(V, E)$ с $n$ вершинами определена, как в задаче 2.77. Приведённой матрицей инцидентности $\boldsymbol {A}_{r}$ называется матрица, полученная из $A$ удалением строки, скажем, $n$-й строки. Покажите, что любая подматрица $B$ размера $(n-1) \times (n-1)$ матрицы $A_{r}$ невырождена тогда и только тогда, когда рёбра, соответствующие столбцам $B$, образуют рёбра остовного дерева в $G$.

Покажите, что если $A_{r}$ — приведённая матрица инцидентности (как определено в задаче 2.77) связного графа $G$, а $\left(A_{r}\right)^{T}$ — её транспонированная матрица, число остовных деревьев в $G$ равно определителю $A_{r}\left(A_{r}\right)^{T}$.

Если $e$ — ребро графа $G$, то $G-e$ — подграф $G$, полученный из $G$ удалением $e$ из $G$. После удаления ребра $e$, соединяющего вершины $v$ и $w$, пусть вершины $v$ и $w$ объединяются в единую вершину. Полученный граф $G^{\prime }$ называется стянутым графом, полученным стягиванием ребра $e$, и обозначается G.e. Если $\tau (G)$ — число остовных деревьев в $G$, покажите, что $\tau (G)=\tau (G-e)+ \tau$ (G.e).

Покажите, что если $T_{i}=\left(V_{i}, E_{i}\right)$, где $i=1,2, \ldots , k$ — поддеревья $T=(V, E)$, такие что каждая пара поддеревьев имеет хотя бы одну общую вершину, то всё множество поддеревьев имеет общую вершину.

Найдите остовное дерево поиска в глубину (DFS), начиная поиск с вершины 2, в графе, изображённом на рис. 2-20.

Fig. 2-20

Покажите, что орграф $G=(V, E)$ сильно связен тогда и только тогда, когда выполняется следующее свойство: для каждого непустого подмножества $X$ вершин существует дуга из некоторой вершины $x$ в $X$ в некоторую вершину $y$ в дополнении $X$.

Покажите, что если турнир содержит ориентированный контур, он содержит ориентированный треугольник.

Если $G$ — турнир с $n$ вершинами, то вектор, компоненты которого — $n$ полустепеней исхода, расположенных в неубывающем порядке, называется вектором очков турнира. Турнир называется транзитивным турниром, если всякий раз, когда $(u, v)$ и $(v, w)$ — дуги, $(u, w)$ также является дугой. Покажите, что турнир $G$ с $n$ вершинами транзитивен тогда и только тогда, когда его вектор очков равен $\left[\begin{array}{lllll}0 & 1 & 2 & \cdots & (n-1)\end{array}\right]$.

Пусть $D^{\prime }$ — орграф, полученный из сильно связного смешанного графа $G$ (см. раздел 2.2) удалением неориентированного ребра $e=\left\{ x, y\right\}$ из $G$ и заменой каждого другого ребра в $G$ двумя дугами в противоположных направлениях. Пусть $X$ — множество всех вершин $v$, таких что в $D^{\prime }$ существует ориентированный путь из $x$ в $v$, состоящий хотя бы из одной дуги. Аналогично, пусть $Y$ — множество всех вершин $v$, таких что в $D^{\prime }$ существует ориентированный путь из $y$ в $v$, состоящий хотя бы из одной дуги. Если $x$ не принадлежит $Y$, а $y$ не принадлежит $X$, то $e=\left\{ x, y\right\}$ — мост в смешанном графе.

Покажите, что если $G$ — сильно связный смешанный граф, любое ребро, не являющееся мостом, можно преобразовать в дугу так, чтобы полученный смешанный граф также был сильно связным.

Докажите теорему 2.10 (теорема Роббинса): граф сильно ориентируем тогда и только тогда, когда он связен и не имеет мостов.

Пусть $G$ — связный граф, в котором ни одно ребро не является мостом, и пусть $T$ — DFS-остовное (ориентированное) дерево, полученное поиском, начатым с фиксированной вершины $r$, называемой корнем дерева. Покажите, что в $T$ существует ориентированный путь к каждой вершине из корня $r$.

Пусть $G$ — связный простой граф, в котором ни одно ребро не является мостом, и пусть $T$ — DFS-остовное дерево в графе. Пусть $f(x)$ — единственная метка вершины $x$, присвоенная ей в ходе поиска, как в задаче 2.88. Если $\left\{ v, u\right\}$ — любое ребро, не использованное как дуга в $T$, и если $w$ — любая вершина, такая что $f(v)< f(w) \leq f(u)$, то в $T$ существует ориентированный путь из $v$ в $w$.

Пусть $G$ и $T$ такие же, как в задаче 2.89. Если в $T$ существует ориентированный путь $P$ из вершины $a$ в вершину $x$ и ориентированный путь $Q$ из другой вершины $b$ в $x$, то в дереве $T$ существует либо ориентированный путь из $a$ в $b$, либо из $b$ в $a$.

Пусть $G$ и $T$ такие же, как в задаче 2.89, с той же нумерацией меток, что и ранее. Если $\left\{ u, v\right\}$ — ребро, не входящее в $T$, и $f(u)<f(v)$, это ребро преобразуется в дугу из $v$ в $u$. Таким образом, каждое ребро в $G$ теперь преобразовано в дугу, что даёт ориентацию $G^{\prime }$ графа $G$, основанную на поиске в глубину. Длина (единственного) пути в $T$ от корня до вершины $x$ обозначается $d(x)$. Если $d(x) \geq 1$ и $y$ — любая вершина с $d(y)<d(x)$, то в $G^{\prime }$ существует ориентированный путь из $x$ в $y$.

Пусть $G$ и $G^{\prime }$ такие же, как в задаче 2.91. Покажите, что в $G^{\prime }$ существует ориентированный путь от каждой вершины до корня.

Докажите теорему 2.11 (теорема Робертса): процедура ориентирования с помощью поиска в глубину в связном графе без мостов даёт сильно связный орграф. (Это ещё один способ установить теорему Роббинса. Таким образом, приведённое здесь доказательство можно назвать доказательством теоремы Роббинса по Робертсу.)

Покажите, что вершина $\nu$ связного графа является точкой сочленения тогда и только тогда, когда существуют две различные вершины $u$ и $w$, такие что каждый путь между этими двумя вершинами проходит через $v$.

Покажите, что любой нетривиальный граф имеет не менее двух вершин, не являющихся точками сочленения.

Покажите, что ребро связного графа является мостом тогда и только тогда, когда существуют вершины $\nu$ и $w$, такие что каждый путь между этими двумя вершинами содержит это ребро.

Покажите, что ребро является мостом тогда и только тогда, когда никакой цикл не содержит этого ребра.

Нетривиальный связный граф называется неразделимым графом, если он не имеет точек сочленения. Подграф $H$ графа $G$ называется блоком графа $\boldsymbol {G}$, если $H$ неразделим и максимален относительно этого свойства: если существует неразделимый подграф $H^{\prime }$, такой что $H$ является подграфом $H^{\prime }$, то $H=H^{\prime }$. Найдите блоки графа на рис. 2-21.

Fig. 2-21

Покажите, что два блока имеют не более одной общей вершины. Каким отличительным свойством обладает вершина, общая для двух блоков?

Покажите, что $G$ является 2-связным тогда и только тогда, когда $G$ связен, имеет не менее трёх вершин и не имеет точек сочленения.

Покажите, что центр связного графа является подмножеством множества вершин некоторого блока.

Покажите, что в графе с $n$ вершинами длина пути не может превышать $(n-1)$, а длина цикла не может превышать $n$.

Покажите, что граф $G$ с $n$ вершинами связен тогда и только тогда, когда ни один элемент матрицы $(A+A^{2}+\cdots +A^{n-1})$ не равен нулю, где $A$ — его матрица смежности.

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

Найдите число пересечения для $K_{n}$ при $n>4$.

Пусть $T(G)$ — тотальный граф графа $G=(V, E)$, где $V=\left\{ 1,2, \ldots , n\right\}$. Пусть $d_{i}$ — степень $i$ в $G$

Если и $G$, и его дополнение являются деревьями, найдите порядок $G$.

Найдите число рёбер в лесе с $n$ вершинами и $k$ деревьями.

Покажите, что дерево является двудольным графом.

Покажите, что если дерево имеет ровно две концевые вершины, степень каждой другой вершины равна 2, и, следовательно, оно является путём.

Найдите число концевых вершин в дереве с $n$ вершинами.

Покажите, что если степень каждой неконцевой вершины дерева равна 3, число вершин дерева чётно.

В дереве с 14 концевыми вершинами степень каждой неконцевой вершины равна либо 4, либо 5. Найдите число вершин степени 4 и степени 5.

Найдите число различных помеченных деревьев с пятью вершинами.

Если $G$ — подграф, полученный удалением ребра из $K_{n}$, найдите число остовных деревьев в $G$.

Покажите, что двудольный граф является транзитивно ориентируемым графом, но не наоборот.