\documentclass[a4paper,10pt]{article}
\usepackage{circle,russcorr,wrapfig,graphicx}
\setcounter{задача}{-1}
\begin{document}
\заголовок{7 февраля 2004 г.}{Графы}{15}

\textit{Граф}~--- это (конечное) множество точек и соединяющих эти
точки отрезков. Точки называют \textit{вершинами}, а отрезки~---
\textit{рёбрами}.
Граф называется \textit{связным}, если любые две его вершины
соединены ломанной.
Граф называется \textit{полным}, если любые две его вершины
соединены ребром.
\textit{Степенью} вершины называется число выходящих из неё рёбер.

\bigskip

\z Если граф можно обойти, пройдя по каждому ребру ровно один раз, то
в этом графе не более двух нечётных вершин. (теорема Эйлера)

\z\p Можно ли объединить $17$ компьютеров в сеть так, чтобы каждый был
бы соединён ровно с тремя другими?

\p В некотором государстве $n$ городов и из каждого города выходит
ровно $3$ дороги. Может ли в этом государстве быть ровно $100$ дорог?

\z Пусть в некотором графе $n$ вершин и $p$ рёбер. \p Найдите сумму
степеней его вершин. \p Докажите, что число нечётных вершин в этом
графе чётно.

\begin{wrapfigure}{r}{75pt}
  \vspace*{-0.7cm}
  \includegraphics[scale=0.8]{15.1.eps}
  \mbox{Рис. 1}
  \includegraphics[scale=0.5]{15.2.eps}
  \mbox{Рис. 2}  
\end{wrapfigure}

\z\p Можно ли прогуляться по парку, перейдя через каждый забор ровно
один раз? (См.~рис.~1.)

\p Гуляя по Кенигсбергу, Л. Эйлер захотел обойти город, пройдя по
каждому мосту ровно один раз. Сможет ли он это сделать? (См.~рис.~2.)

\z\p Докажите, что из куска проволоки длиной $120$см нельзя, не
разламывая её, сделать каркас куба с ребром длины $10$см.
\p Какое наименьшее число раз придётся сломать проволоку, чтобы
изготовить каркас?

\z У царя Дадона было $3$ сына. Из его потомков по мужской линии $100$
имело по $2$ сына, а остальные умерли бездетными. Сколько всего
потомков было у царя Дадона?

\z\p Докажите, что при любой раскраске в два цвета полного графа
с $6$ вершинами в нём найдётся одноцветный треугольник. \p Докажите,
что при любой раскраске в три цвета полного графа
с $17$ вершинами в нём найдётся одноцветный треугольник.

\end{document}
