4. Докажнте что в любом графе есть две вершнны, нз которых выходнт одинаковое колнче- ство ребер.

Для доказательства утверждения о том, что в любом графе есть две вершины, из которых выходят одинаковое количество рёбер, воспользуемся принципом Дирихле. Пусть \( G \) — граф с \( n \) вершинами. Каждая вершина может иметь от 0 до \( n-1 \) выходящих рёбер (в случае, если граф неориентированный, и если он ориентированный, то количество выходящих рёбер может варьироваться от 0 до \( n-1 \) в зависимости от количества других вершин). Таким образом, количество возможных значений степени (числа выходящих рёбер) для каждой вершины в графе \( G \) может быть от 0 до \( n-1 \). Это даёт нам \( n \) возможных значений. Однако, если у нас есть \( n \) вершин, то по принципу Дирихле, если мы попытаемся распределить \( n \) объектов (вершины) по \( n \) ящикам (возможным значениям степени), то в случае, если хотя бы одна из вершин имеет степень \( n-1 \) (что возможно только в полном графе), то оставшиеся \( n-1 \) вершин могут иметь степени от 0 до \( n-2 \). Это означает, что у нас будет \( n-1 \) возможных значений для \( n-1 \) вершин, что по принципу Дирихле гарантирует, что как минимум две вершины будут иметь одинаковую степень. Таким образом, в любом графе действительно существуют как минимум две вершины, из которых выходят одинаковое количество рёбер.