\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*{Šestá série domácích úkolů\\z diskrétní matematiky}
\subsection*{Deadline: 20. 11. 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 (3b) Rozhodněte, zda existují grafy s následujícími posloupnosti stupňů:
\begin{enumerate}
    \item 4, 3, 3, 2, 2, 2, 0
    \item 5, 4, 3, 2, 2, 1, 0
    \item 6, 4, 3, 2, 2, 1, 0
\end{enumerate}

\item (3b) Buď $X$ množina $\{1,4,7\}$.
Sestrojíme graf $G=(V,E)$ graf, kde $V=\{1,2,3,4,5,6,7,8\}$ a $E=\{\{i,j\}\colon |j-i| \in X\}$.
Nakreslete tento graf a  spočtěte jeho skóre (posloupnost stupňů vrcholů).\footnote{Pro zajímavost: jedná se o příklad tzv.~\href{https://en.wikipedia.org/wiki/Paley_graph}{Paleyho grafu}, které mají řadu zajímavých vlastností, např. jsou izomorfní svému doplňku. Paleyho grafy se využívají např. v~teorii čísel nebo Ramseyho teorii.}

\item (2b) Buď $n$ libovolné přirozené číslo. Najděte všechna čísla $k$, pro která existuje strom s~přesně $k$ vrcholy stupně jedna.
\item (2b) Dokažte, že v~každém konečném grafu existují dva vrcholy se stejným stupněm.
\item (bonus+3b) Dokažte, že pokud $d_1\geq d_2\geq d_3\geq\ldots\geq d_n$ je posloupnost všech stupňů nějakého grafu,
tak 
\begin{itemize}
 \item $\sum_{k=0}^n d_i$ je sudé
 \item pro každé $k=1,\ldots, n$ platí
 \[\sum_{i=1}^k d_i\leq k(k-1) + \sum_{i=k+1}^n\min\{d_i,k\}\]
\end{itemize}

\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}
