Kezdőlap


Feladat:	A.777	Korcsoport: 18-	Nehézségi fok: nehéz
Kitűző(k):	Pálvölgyi Dömötör (Budapest)
Füzet:	2020/május, 291. oldal		PDF \| MathML
Témakör(ök):	Matematika, Nehéz feladat, Gráfelmélet

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Egy $n$ pontú, síkbarajzolt véges $G (V, E)$ gráfra jelölje $x (e)$ a $G$ gráf $e$ élén található metszéspontok (azon helyek, ahol egy másik éllel találkozik, kivéve a végpontjait) számát. Bizonyítandó, hogy

\begin{matrix} \sum_{e \in E}^{} \frac{1}{x (e) + 1} \leq 3 n - 6. \end{matrix}