\documentclass[a4paper,10pt]{article}
\usepackage[czech]{babel}
\usepackage{amsmath, amsthm, amsfonts, amssymb} %basic mathematical fonts and symbols
\usepackage{graphicx} %inclusion of pictures
\usepackage{fnpct} %proper footnotes spacing after commas and dots
\usepackage{footnotebackref} 		%Footnotes reference back to the original text
\usepackage{hyperref}						%references are clickable
\hypersetup{colorlinks=true, linkcolor=red, urlcolor=blue, citecolor=blue, pdfpagemode=UseNone, pdfstartview=FitH, bookmarksopen=true}
\hypersetup{pdftitle=Discrete Mathematics}
\usepackage[utf8]{inputenc}
\usepackage[inline]{enumitem}

\newcommand{\abs}[1]{\left|#1\right|} % absolute value
\newcommand{\lnorm}[2]{{\left\|#2\right\|_#1}}% an l_p norm
\newcommand{\norm}[1]{\left\|#1\right\|} % a norm
\newcommand{\R}{\mathbb{R}} 	%real numbers
\newcommand{\Z}{\mathbb{Z}} 	%integers
\newcommand{\N}{\mathbb{N}} 	%natural numbers
\newcommand{\Q}{\mathbb{Q}} 	%rational numbers
\newcommand{\C}{\mathbb{C}} 	%complex numbers

%opening
\title{}
\author{}
\usepackage{fullpage}

\begin{document}
\section*{Desátá série domácích úkolů\\z diskrétní matematiky}
\subsection*{Deadline: 21. 12. 2020; 23:59:59.99}

U každého příkladu nezapomeňte svá řešení pořádně zdůvodnit. 
\subsection*{Zadání}
\begin{enumerate}
\item\relax[3b] Petersenův graf není rovinný. Odeberte z něj nejmenší možný počet hran tak, aby se tento graf stal rovinným a najděte jeho rovinné nakreslení.

Lze výsledný graf nakreslit rovinně tak, aby všechny hrany byly (rovné) úsečky? (bonus+2b)
\item\relax[3b] Průsečíkové číslo $cr(G)$ grafu $G$ je nejmenší počet křížení, s jakým se $G$ podaří nakreslit do roviny. (Např. $cr(K_5)=1$.) 
Je-li $n\geq 3$ počet vrcholů $G$ a $m$ počet jeho hran, dokažte, že
\[
 cr(G)\geq m-3n+6.
\]
\item\relax[3b] Vnitřní obvod (anglicky \emph{girth}) $g(G)$ grafu $G$ je definován jako délka nejkratšího cyklu v $G$. 
Dokažte, že pro souvislý rovinný graf s $g=g(G)\geq 3$, $n$ vrcholy a $m$ hranami platí 
\[m\leq \frac{g(n-2)}{g-2}.\]
\item\relax[2b] Buď $W$ graf, jehož vrcholy jsou všechny prvky $\Z_8$, takový,
že $u$ a $v$ jsou spojeny hranou právě tehdy, když $u-v\in\{1,4,7\}$. (Odčítání se samozřejmě vyhodnocuje v~$\Z_8$, tj. modulo $8$.)

Jedná se o rovinný graf? Pokud, ano, poskytněte rovinné nakreslení.
Pokud ne, najděte podrozdělení $K_5$ nebo $K_{3,3}$ obsažené ve $W$.
\end{enumerate}


\subsection*{Pokyny}
Řešení posílejte na ppatak@seznam.cz s předmětem ``diskretka''.
Řešení mohou být v jakémkoli formátu (v ideálním případě pdf z \LaTeX{u}, ale stačí i naskenované, nafocené pdf, jpeg), 
snažte se, aby byla řešení čitelná.
U bonusových příkladů se Vám body započítavají, 
ale body z bonusového příkladu se nepočítají do celkového maximálního počtu bodů.
Příklady můžete zaslat i opakovaně, počítá se nejlepší dosažení počet bodů.
\end{document}
