\documentclass[a4paper,12pt]{article}
%%\pagestyle{empty}

\usepackage[left=15mm,right=20mm,top=15mm,bottom=22mm]{geometry}
\usepackage{booktabs, multicol}
\usepackage{makeidx, graphicx, amsmath, amssymb, amsthm, ae}
\usepackage[bosnian]{babel}
%%\usepackage[cp1250]{inputenc}

\usepackage[gen]{eurosym}
\usepackage[normalem]{ulem} %%sout

\usepackage{enumitem}

\usepackage{tikz,textcomp}
\newfont\fiverm{cmr5}

\usepackage{tkz-berge}



\usepackage{stackengine,hvfloat,booktabs}



\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=cyan,
}





\def\cm{{\mbox{\rm cm}}}
\def\Inn{{\mbox{\rm Inn}}}

\def\Sym{{\mbox{\rm Sym}}}
\def\RotSym{{\mbox{\rm RotSym}}}
\def\lcm{{\mbox{\rm lcm}}}
\def\id{{\mbox{\rm id}}}




%%\def\NN{{\mbox{$\mathbb N$}}}
\def\RR{{\mbox{$\mathbb R$}}}
\def\CC{{\mbox{$\mathbb C$}}}
\def\T{{\mbox{$\mathbb T$}}}
\def\H{{\mbox{$\mathbb H$}}}
\def\Z{{\mbox{$\mathbb Z$}}}
\def\Q{{\mbox{$\mathbb Q$}}}
\def\F{{\mbox{$\mathbb F$}}}
\def\C{{\mbox{$\mathbb C$}}}
\def\E{{\mbox{$\mathcal{E}$}}}
\def\M{{\mbox{$\mathcal{M}$}}}

\def\ZZplus{{\mbox{$\mathbb Z_+$}}}

\def\S{{\mbox{$\mathcal{S}$}}}
\def\L{{\mbox{$\mathcal{L}$}}}
\def\G{{\mbox{$\mathcal{G}$}}}
\def\P{{\mbox{$\mathcal{P}$}}}

\def\B{{\mbox{$\mathcal{B}$}}}
\def\A{{\mbox{$\mathcal{A}$}}}
\def\O{{\mbox{$\mathcal{O}$}}}

\def\X{{\mbox{$\mathcal{X}$}}}
\def\V{{\mbox{$\mathcal{V}$}}}
\def\Y{{\mbox{$\mathcal{Y}$}}}
\def\W{{\mbox{$\mathcal{W}$}}}
\def\dist{{\mbox{\rm dist}}}
\def\GL{{\mbox{\rm GL}}}
\def\SL{{\mbox{\rm SL}}}
\def\NSD{{\mbox{\rm gcd}}}

\def\exc{{\mbox{\rm exc}}}
\def\ecc{{\mbox{\rm ecc}}}
\def\Alt{{\mbox{\rm Alt}}}
\def\Aut{{\mbox{\rm Aut}}}
\def\Hom{{\mbox{\rm Hom}}}
\def\spec{{\mbox{\rm spec}}}
\def\rank{{\mbox{\rm rank}}}
\def\rang{{\mbox{\rm rang}}}
\def\mod{{\mbox{\rm mod}}}
\def\div{{\mbox{\rm div}}}
\def\trag{{\mbox{\rm trag}}}
\def\tr{{\mbox{\rm tr}}}
\def\dim{{\mbox{\rm dim}}}
\def\diag{{\mbox{\rm diag}}}
\def\Mat{{\mbox{\rm Mat}}}
\def\Sim{{\mbox{\rm Sim}}}
\def\ker{{\mbox{\rm ker}}}
\def\im{{\mbox{\rm im}}}
\def\mp{{\mbox{\rm mp}}}
\def\gcd{{\mbox{\rm gcd}}}

\def\K{{\mbox{$\pmb{K}$}}}
\def\J{{\mbox{$\pmb{J}$}}}
\def\I{{\mbox{$\pmb{I}$}}}
\def\j{{\mbox{$\pmb{j}$}}}
\def\0{{\mbox{\boldmath{$0$}}}}
\def\algmult{{\mbox{\rm alg\,mult}}}
\def\geomult{{\mbox{\rm geo\,mult}}}
\def\du{{\mbox{\rm \,d$u$}}}
\def\dx{{\mbox{\rm \,d$x$}}}
\def\dt{{\mbox{\rm \,d$t$}}}
\def\dy{{\mbox{\rm \,d$y$}}}
\def\dz{{\mbox{\rm \,d$z$}}}
\def\tg{{\mbox{\rm tg\,}}}
\def\arctg{{\mbox{\rm arc\,tg\,}}}
\def\arcsin{{\mbox{\rm arc\,sin\,}}}
\def\ctg{{\mbox{\rm ctg\,}}}

\def\a{{\mbox{\boldmath $a$}}}
\def\q{{\mbox{\boldmath $q$}}}
\def\b{{\mbox{\boldmath $b$}}}
\def\j{\mbox{\boldmath $j$}}
%%\def\u{{\mbox {\boldmath $u$}}}
\def\m{{\mbox {\boldmath $m$}}}
\def\n{{\mbox {\boldmath $n$}}}
\def\vv{{\mbox {\boldmath $v$}}}
\def\w{{\mbox {\boldmath $w$}}}
\def\x{\mbox{\boldmath $x$}}
\def\h{{\mbox {\boldmath $h$}}}
\def\y{\mbox{\boldmath $y$}}
\def\0{\mbox{\boldmath $0$}}
\def\z{\mbox{\boldmath $z$}}
\def\p{\mbox{\boldmath $p$}}
\def\l{\mbox{$\lambda$}}

\def\e{{\mbox{\boldmath $e$}}}
\def\ro{{\mbox{\boldmath $\rho$}}}

\def\ra{\rightarrow}
\def\Ra{\Rightarrow}
\def\La{\Leftarrow}




\DeclareMathOperator{\NN}{{\mathbb N}}
\DeclareMathOperator{\ZZ}{{\mathbb Z}}




\input prepictex
\input pictex
\input postpictex

\def\nula{%
\raisebox{-6pt}{%
\beginpicture
\setcoordinatesystem units <0.3cm,0.3cm>
\setplotarea x from -1 to 1, y from -1 to 1
\unitlength=0.75cm
{\scriptsize
\plot -0.4 -0.8 -0.4 0.4 /
\plot -0.4 -0.8 -0.4 0.8 /
\plot -0.4 -0.8 0.4 -0.8 /
\plot 0.4 0.8 0.4 -0.8 /
\plot 0.4 0.8 -0.4 0.8 /
\plot -0.4 0 0.4 0 /
}
\endpicture}}


\def\prva{%
\raisebox{-6pt}{%
\beginpicture
\setcoordinatesystem units <0.3cm,0.3cm>
\setplotarea x from -1 to 1, y from -1 to 1
\unitlength=0.75cm
{\scriptsize
\plot -0.8 0 -0.8 0.8 /
\plot -0.8 0.8 0 0.8 /
\plot 0 0.8 0 0 /
\plot 0 0 0.8 0 /
\plot 0.8 0 0.8 -0.8 /
\plot 0.8 -0.8 -0.8 -0.8 /
\plot -0.8 -0.8 -0.8 0 /
\plot -0.8 0.8 0.8 0.8 /
\plot 0.8 0 0.8 0.8 /
}
\endpicture}}



\def\druga{%
\raisebox{-6pt}{%
\beginpicture
\setcoordinatesystem units <0.3cm,0.3cm>
\setplotarea x from -1 to 1, y from -1 to 1
\unitlength=0.75cm
{\scriptsize
\plot -0.8 -0.8 -0.8 0.8 /
\plot 0.8 0.8 -0.8 0.8 /
\plot -0.8 -0.8 -0.8 0.8 /
\plot -0.8 -0.8 0.8 -0.8 /
\plot 0.8 0.8 0.8 -0.8 /
\plot 0 0 -0.8 0 /
\plot 0 0 0 -0.8 /
}
\endpicture}}



\def\tretja{%
\raisebox{-6pt}{%
\beginpicture
\setcoordinatesystem units <0.3cm,0.3cm>
\setplotarea x from -1 to 1, y from -1 to 1
\unitlength=0.75cm
{\scriptsize
\plot -0.8 -0.8 -0.8 0.8 /
\plot 0.8 0.8 -0.8 0.8 /
\plot -0.8 -0.8 -0.8 0.8 /
\plot -0.8 -0.8 0.8 -0.8 /
\plot 0.8 0.8 0.8 -0.8 /
\plot 0 0 0.8 0 /
\plot 0 0 0 -0.8 /
}
\endpicture}}



\def\cetrta{%
\raisebox{-6pt}{%
\beginpicture
\setcoordinatesystem units <0.3cm,0.3cm>
\setplotarea x from -1 to 1, y from -1 to 1
\unitlength=0.75cm
{\scriptsize
\plot -0.8 -0.8 -0.8 0.8 /
\plot 0.8 0.8 -0.8 0.8 /
\plot -0.8 -0.8 -0.8 0.8 /
\plot -0.8 -0.8 0.8 -0.8 /
\plot 0.8 0.8 0.8 -0.8 /
\plot 0 0 -0.8 0 /
\plot 0 0 0 0.8 /
}
\endpicture}}


\def\peta{%
\raisebox{-6pt}{%
\beginpicture
\setcoordinatesystem units <0.3cm,0.3cm>
\setplotarea x from -1 to 1, y from -1 to 1
\unitlength=0.75cm
{\scriptsize
\plot -0.8 -0.8 -0.8 0.8 /
\plot 0.8 0.8 -0.8 0.8 /
\plot -0.8 -0.8 -0.8 0.8 /
\plot -0.8 -0.8 0.8 -0.8 /
\plot 0.8 0.8 0.8 -0.8 /
\plot 0 -0.8 0 0.8 /
\plot -0.8 0 0.8 0 /
}
\endpicture}}





\newcommand{\ds}{\displaystyle}

\newcommand{\ol}{\overline}






\newcommand\barbelow[1]{\stackunder[2pt]{$#1$}{\rule{1.5ex}{.1ex}}}





\newtheoremstyle{zaFiguru} %name
  {3.4mm}    %Space above, empty = `usual value'
  {3.5mm}    %Space below
  {\rm}   %Body font
  {}     %Indent amount (empty = no indent, \parindent = para indent)
  {\bf}   %Thm head font
  {}      %Punctuation after thm head
  {2mm}   %Space after thm head: \newline = linebreak
  {\thmname{#1} \thmnumber{\Large #2.}\thmnote{\,(#3)}}       %Thm head spec





%%\swapnumbers
\theoremstyle{zaFiguru}
\newtheorem{zad}{}


\def\ug{{{\measuredangle}}}
\def\tr{{{\triangle}}}


\setlength{\textheight}{262mm}
\setlength{\textwidth}{180mm}
\begin{document}
\raggedright



\section{Sets and Mathematical Induction}

\begin{zad}
Let $A$ be a set of cardinality $n \in \ZZ^+$, and let $\P(A)$ denote the power set of $A$. Using mathematical induction, prove the following equality:
$$
|\P(A)| = 2^n.
$$
\end{zad}

\begin{zad}
Prove the following statement: If $n$ books are distributed among $m$ boxes, then at least one box will contain at least $\left\lfloor\frac{n - 1}{m}\right\rfloor + 1$ books. Provide a detailed explanation of each step in your proof.
\end{zad}









\section{Basic Combinatorial Principles: Sum Principle, Product Principle, Equality Principle}

\begin{zad}
Suppose we have $5$ (identical) oranges and $8$ (identical) apples. How many different non-empty collections of fruit can we make if a collection can include at most $3$ oranges? 
Before calculating the numerical value, provide at least three examples of possible collections.
\end{zad}

\begin{zad}
How many different five-digit numbers can be formed using the digits $1$, $2$, $3$, and $4$ if:
\begin{enumerate}[label=\rm(\alph*)]
\item there are no additional restrictions?
\item the sum of the digits must be even?
\item there must be more even digits than odd digits?
\end{enumerate}
Provide the result as a numerical value.
\end{zad}

\begin{zad}
How many different $4$-digit numbers can be formed using the digits $2$, $3$, $5$, $6$, $7$, and $8$ under the following conditions:
\begin{enumerate}[label=\rm(\alph*)]
\item the digits in the number are all distinct?
\item all digits in the number are the same?
\item the number is greater than $5688$?
\item the number is divisible by $5$?
\item the number is a palindrome\footnote{A palindrome is a sequence that reads the same forwards and backwards, e.g., 12321, 1221.}?
\item the number is even and is a palindrome?
\end{enumerate}
Provide the result as a precise numerical value. For all parts of the task, provide at least three examples of possible $4$-digit numbers before computing numerical results.
\end{zad}

\begin{zad}
In how many ways can we form a sequence of $5$ letters using the letters $x$, $y$, $a$, $b$, $u$, and $v$, considering the following conditions:
\begin{enumerate}[label=\rm(\roman*)]
\item letters in the sequence can be repeated?
\item letters in the sequence cannot be repeated, and the sequence must include the letter $x$?
\item letters in the sequence can be repeated, and the sequence must include the letter $x$?
\end{enumerate}
\end{zad}

\begin{zad}
Let $A = \{-4, -3, -2, -1, 1, 2, 3, 4\}$. In how many ways can we choose four numbers from the set $A$ if the selected numbers must have different absolute values:
\begin{enumerate}[label=\rm(\alph*)]
\item and the order of selection matters?
\item and the order of selection does not matter?
\end{enumerate}
\end{zad}















\section{The Pigeonhole Principle}

\begin{zad}
In the Diocletian family, there are $12$ children. Prove that at least two family members were born in the same month.
\end{zad}

\begin{zad}
How many students must take the written exam in Discrete Mathematics II to ensure that at least four students receive the same score if the exam is graded on a scale from $0$ to $100$?
\end{zad}

\begin{zad}
Given five points inside an equilateral triangle with side length $2$ cm, prove that there exist two points that are at most $1$ cm apart.
\end{zad}

\begin{zad}
At a party, there are $8$ students aged between $18$ and $30$ years. Justify that it is possible to select two different groups of individuals such that the sum of the ages in one group equals the sum of the ages in the other group.
\end{zad}

\begin{zad}
From the set $\{1, 2, \ldots, 2n\}$, $n+1$ distinct numbers are chosen. Prove that among the selected integers, there are always two whose greatest common divisor is $1$.
\end{zad}

\begin{zad}
Every week, $200$ cargo ships arrive at the Port of Koper. Justify that there are at least two ships that arrive at the port less than an hour apart.
\end{zad}

\begin{zad}
At a family gathering, nine people aged between $18$ and $58$ years were present. Justify that it is possible to select two different groups of individuals such that the sum of the ages in one group equals the sum of the ages in the other group.
\end{zad}

\begin{zad}
Consider a game involving $10$ tennis players (one-on-one matches). Each player plays at least one match, and no two players play against each other more than once (the exact number of matches played by each player is unknown, and two different players may participate in different numbers of matches). Prove that there are at least two players who have played the same number of matches.
\end{zad}

\begin{zad}
Consider a standard die with $6$ faces numbered from $1$ to $6$. Select four of its faces. Prove that among these four faces, there are two that are on opposite sides of the die.
\end{zad}








\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}










\newpage
\section{Ordered Selection with Repetition. Ordered Selection without Repetition.}

\hvFloat[floatPos=!htb,capPos=before,onlyText=true,]{}
{{
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=1cm,y=1cm]
\draw [line width=2pt] (0,0)-- (3,0);
\draw [line width=2pt] (0,0)-- (0,4);
\draw [line width=2pt] (0,4)-- (3,4);
\draw [line width=2pt] (3,4)-- (3,0);
\draw [line width=2pt] (3,1)-- (0,1);
\draw [line width=2pt] (0,2)-- (3,2);
\draw [line width=2pt] (0,3)-- (3,3);
\draw [line width=2pt] (1,4)-- (1,0);
\draw [line width=2pt] (2,4)-- (2,0);
\begin{scriptsize}
\draw [fill=red] (0,0) circle (2pt);
\draw[color=black] (-0.28,-0.07) node {\large$X$};
\draw [fill=red] (3,4) circle (2.5pt);
\draw[color=black] (3.2,4.35) node {\large$Y$};
\end{scriptsize}
\end{tikzpicture}
}}
{\begin{zad}
A student wants to walk from point $X$ to point $Y$ along the streets as shown in the figure on the right. How many different shortest paths can they choose?
\end{zad}}{fg}

\begin{zad}
From a box containing balls numbered from $1$ to $20$, $6$ balls are chosen. How many ways can this be done if
\begin{enumerate}[label=\rm(\alph*)]
\item the balls are selected one at a time and returned to the box?
\item the balls are selected one at a time and not returned to the box?
\item the balls are selected two at a time and not returned to the box?
\item all $6$ balls are selected at once?
\end{enumerate}
Provide the result as an exact numerical value. For each part of the problem, give at least three examples of arrangements that can be made before calculating numerical values.
\end{zad}

\begin{zad}
In a swimming competition with four swimmers, how many ways can the competition end if ties are possible?
\end{zad}

\begin{zad}
A man has $12$ relatives: $5$ are men and $7$ are women. His wife also has $12$ relatives: $7$ are men and $5$ are women. They have no relatives in common. The couple decides to invite $12$ relatives for a visit. In how many ways can they do this if
\begin{enumerate}[label=\rm(\alph*)]
\item each invites $6$ relatives, and exactly $6$ of the invited people are men?
\item both invite the same number of women?
\end{enumerate}
It is not necessary to express the answers with exact numerical values.
\end{zad}







\section{Permutations}

\begin{zad}
In how many ways can $10$ people be arranged into pairs? Before calculating the numerical value, provide at least three examples of possible arrangements.
\end{zad}

\begin{zad}
In how many different ways can $4$ different mathematics books, $3$ different fiction books, and $5$ different encyclopedias be arranged on a shelf if
\begin{enumerate}[label=\rm(\alph*)]
  \item the books can be mixed freely?
  \item all mathematics books must be grouped together?
  \item books of the same type must be grouped together?
\end{enumerate}
\end{zad}

\begin{zad}
In how many ways can a group of $6$ women and $5$ men line up for a photograph if no two people of the same gender are standing next to each other?
\end{zad}

\begin{zad}
First, list $12$ distinct permutations of the following $10$ letters: $a,a,a,b,b,n,n,e,s,t$.

Then prove that the number of distinct permutations of $n$ objects, where the first object appears $k_1$ times, the second object appears $k_2$ times, the third object appears $k_3$ times, and all remaining objects appear exactly once, is given by
$$
\frac{n!}{k_1!\cdot k_2!\cdot k_3!}.
$$
Explain each step of the proof in detail.
\end{zad}

\begin{zad}
\begin{enumerate}[label=\rm(\alph*)]
\item How many different "words" can be formed by rearranging the letters of the word *banana*?
\item How many words from part (a) have the letter $b$ immediately before the letter $a$?
\item How many words from part (a) do not contain the sequence $bnn$?
\item How many words from part (a) have the letter $b$ appearing before all $a$'s (not necessarily immediately before them)?
\end{enumerate}
\end{zad}









%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%







\section{Principle of Double Counting}

\begin{zad}
Prove the equality
$$
\sum_{k=0}^n \binom{n}{k}=2^n
$$
by providing a combinatorial proof (using the principle of double counting) and addressing the following question: In how many different ways can we form a word of length $n$ using any number of the letters $A$ and $B$?
\end{zad}

\begin{zad}
Prove the equality
$$
\sum_{k=0}^n k\cdot\binom{n}{k}=n\cdot 2^{n-1}
$$
by providing a combinatorial proof (using the principle of double counting).
\end{zad}

\begin{zad}
\label{cetiri}
Prove the equality
$$
\sum_{j=0}^t \binom{a}{j}\binom{b}{t-j}=\binom{a+b}{t}
$$
by providing a combinatorial proof (using the principle of double counting) and addressing the following question: In how many different ways can we form two words of lengths $a$ and $b$ using exactly $t$ letters $A$ (which must be used) and any number of letters $B$?
\end{zad}

\begin{zad}
Provide a combinatorial proof (using the principle of double counting) of the following equality:
$$
{{n+m}\choose k}= \sum\limits_{\ell=0}^k {{n}\choose \ell} \cdot {{m}\choose {k-\ell}}
\qquad(0\leq k \leq m \leq n).
$$
\end{zad}

\begin{zad}
Prove the equality
$$
\sum_{k=0}^m k\cdot \binom{n}{k}\binom{m}{k}=n\cdot \binom{n+m-1}{n}
$$
by providing a combinatorial proof (using the principle of double counting).
\end{zad}

\begin{zad}
Prove the equality
$$
\sum_{k=0}^n 2^k\binom{n}{k}=3^n.
$$
\begin{enumerate}[label=\rm(\alph*)]
\item Provide an algebraic proof.
\item Provide a combinatorial proof (using the principle of double counting), by addressing the following questions: 
How many different ways can we choose a pair of subsets $(X, Y)$ such that $X \subseteq Y$ for a set of size $n$? How many different sequences of length $n$ can we form using the digits $0$, $1$, and $2$?
\end{enumerate}
\end{zad}

\begin{zad}
Prove the equality
$$
\binom{2n}{n}=\sum_{k=0}^n \binom{n}{k}^2
$$
by providing a combinatorial proof.
\end{zad}

\begin{zad}
Prove the equality
$$
\binom{n+1}{r+1}=\sum_{k=r+1}^{n+1} \binom{k-1}{r}
$$
by providing a combinatorial proof.
\end{zad}

\begin{zad}
\begin{enumerate}[label=\rm(\alph*)]
\item Provide a combinatorial proof of the equality
\begin{equation}
\label{ghj}
\sum_{k=2}^n \binom{n}{k}\binom{k}{2} = \binom{n}{2}2^{n-2}
\end{equation}
for $n \geq 2$.
\item Write the identity \eqref{ghj} for $n=5$ and interpret it using Pascal's triangle.
\end{enumerate}
\end{zad}

\begin{zad}
\begin{enumerate}[label=\rm(\alph*)]
\item Provide (algebraic or combinatorial) proof of the equality
\begin{equation}
\label{ztj}
\sum_{j=0}^n \binom{k+j}{j} = \binom{n+k+1}{n}
\end{equation}
for any two numbers $n,k\in \mathbb{Z}^+$.
\item Write the identity \eqref{ztj} for $k=1$ and use the identity to compute the sum $\sum_{j = 0}^n j$.
\item Use the identity \eqref{ztj} to compute $\sum_{j=0}^n j^2$.
\item Write the identity \eqref{ztj} for $n=4$ and $k=2$ and interpret it using Pascal's triangle.
\end{enumerate}
\end{zad}









\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}







\newpage
\section{Properties of Binomial Coefficients}

\begin{zad}
Prove that for $n > 0$ the following equality holds:
$$
{n \choose 0} - {n \choose 1} + {n \choose 2} - \dotsb + (-1)^n {n \choose n} = 0.
$$
\end{zad}

\begin{zad}
Find a simpler expression for 
$$
\sum_{k=0}^{n}{n \choose k} {2z \choose 2}^k x^{n-k}.
$$ 
The final expression should be the $n$-th power of a quadratic polynomial in variables $x$ and $z$, written in simplified form (e.g., $ax^2 + bz^2 + cxz + dx + ez + f$, for some constants $a, b, c, d, e, f$).
\end{zad}

\begin{zad}
Let $X$ be a set of size $n > 0$.
\begin{enumerate}[label=\rm(\roman*)]
\item Let $\S$ be the set of all subsets of $X$ with even cardinality, and let $\L$ be the set of all subsets of $X$ with odd cardinality. Let $x$ be any element of $X$, and define $f: \S \to \L$ as follows: for every $A \in \S$, let 
$$
f(A) = 
\begin{cases} 
A \setminus \{x\}, & \text{if } x \in A, \\ 
A \cup \{x\}, & \text{if } x \notin A.
\end{cases}
$$
Prove that the mapping $f$ is bijective.
\item Using the result from part (i), provide a combinatorial proof of the identity:
$$
\sum_{k=0}^n (-1)^k {n \choose k} = 0.
$$
\end{enumerate}
\end{zad}

\begin{zad}
A thief is attempting to crack a door code. The code consists of $12$ buttons labeled $0$, $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$, $\#$, and $*$, and requires six digits followed by either $\#$ or $*$. Determine the number of possible codes:
\begin{enumerate}[label=\rm(\roman*)]
\item without any additional constraints.
\item if no digit is repeated.
\end{enumerate}

The thief observes the buttons and notices the following:

- Buttons $4$, $6$, $7$, $8$, and $*$ are never used in the code.

- The button $1$ appears at least twice.

- There are no guarantees for the usage of other buttons.

\begin{enumerate}[resume, label=\rm(\roman*)]
\item How many codes are possible given these new hints?
\item How many codes are possible if the thief also determines that $1$ appears strictly more often than $9$, and $9$ appears strictly more often than $2$?
\end{enumerate}
\end{zad}









\section{Principle of Inclusion and Exclusion}

\begin{zad}
A binary string of length eight is called a syllable. Find the number of syllables in which the second bit is $0$ or the third bit is $1$. Calculate the exact numerical value of your solution!
\end{zad}

\begin{zad}
How many natural numbers $\leq 70$ are coprime to $50$ (i.e., they share no common divisors with $50$ other than $1$)?
\end{zad}

\begin{zad}
How many ten-digit binary strings can be formed that either begin with $111$ or end with $101$ (or both), if:
\begin{enumerate}[label=\rm(\alph*)]
\item there are no additional restrictions?
\item the string contains exactly $6$ ones?
\end{enumerate}
\end{zad}

\begin{zad}
Out of $100$ students, $46$ play volleyball, $47$ play handball, and $48$ play football. Additionally, $12$ students play any pair of these sports (but not the third), and $14$ students play all three sports. How many students do not play any of these three sports?
\end{zad}

\begin{zad}
Among the students in a dormitory:
\begin{itemize}
    \item $12$ play football $(N)$, $20$ play basketball $(K)$, $20$ play volleyball $(O)$, and $8$ play handball $(R)$.
    \item $5$ students play both $N$ and $K$, $7$ play both $N$ and $O$, and $4$ play both $N$ and $R$.
    \item $16$ students play both $K$ and $O$, $4$ play both $K$ and $R$, and $3$ play both $O$ and $R$.
    \item $3$ students play $N$, $K$, and $O$, $2$ play $N$, $K$, and $R$, $2$ play $K$, $O$, and $R$, and $3$ play $N$, $O$, and $R$.
    \item $2$ students play all four sports.
    \item Additionally, $71$ students do not play any of the four sports.
\end{itemize}
Find the total number of students in the dormitory.
\end{zad}

\begin{zad}
In how many ways can $20$ identical candies be distributed among three children if we allow some children to receive no candies, and:
\begin{enumerate}[label=\rm(\alph*)]
\item there are no restrictions on the number of candies per child?
\item at least one child receives at least $7$ candies?
\item at least one child receives at least $10$ candies?
\end{enumerate}
\end{zad}










\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}










\newpage
\section{Unordered Selection with Repetition}

\begin{zad}
In how many ways can $6$ pieces of fruit be selected from a bowl containing apples, oranges, and pears, if the order in which the pieces are selected does not matter and only the type of fruit (not the individual piece) is significant? Assume that the bowl contains at least six pieces of each type of fruit.
\end{zad}

\begin{zad}
In how many ways can five banknotes be selected from a cash register containing banknotes of denominations €5, €10, €20, €50, €100, €200, and €500? Assume that the order of selection does not matter, banknotes of the same denomination are indistinguishable, and there are at least five banknotes of each denomination. Provide the result as an exact numerical value.
\end{zad}

\begin{zad}
A group of $40$ people has been trained as astronauts for the first mission to Mars. They are divided into $5$ groups (red, yellow, blue, green, brown). Each group has $8$ different members, each with a training level from $1$ to $8$. The training level represents the type of training, and each member is trained in exactly one of $8$ different tasks (no two members of the same group share the same training level).
\begin{enumerate}[label=\rm(\alph*)]
\item In how many different ways can $6$ people be selected such that exactly three training levels are represented, each appearing twice? Provide the result as an exact numerical value.
\item In how many ways can $5$ people be selected such that they have $5$ consecutive training levels? Provide the result as an exact numerical value.
\end{enumerate}
\end{zad}






\section{Unordered Selections without Repetition}

\begin{zad}
How many integer solutions does the equation $x_1 + x_2 + x_3 + x_4 = 12$ have if:
\begin{enumerate}[label=\rm(\alph*)]
\item $x_1 \geq 0$, $x_2 \geq 0$, $x_3 \geq 0$, $x_4 \geq 0$?
\item $x_1 \geq 1$, $x_2 \geq 2$, $x_3 \geq 1$, $x_4 \geq 2$?
\end{enumerate}
Provide the result as an exact numerical value. In both parts of the task, give at least three solutions to the given equation before calculating the numerical value.
\end{zad}

\begin{zad}
How many integer solutions does the equation $x_1 + x_2 + x_3 + x_4 + x_5 = 22$ have if:
\begin{enumerate}[label=\rm(\alph*)]
\item $x_1 \geq 0$, $x_2 \geq 20$, $x_3 \geq 0$, $x_4 \geq 0$, $x_5 \geq 0$?
\item $x_1 \geq 2$, $x_2 \geq 3$, $x_3 \geq 4$, $x_4 \geq 3$, $x_5 \geq 2$?
\end{enumerate}
Provide the result as an exact numerical value. In both parts of the task, give at least three solutions to the given equation before calculating the numerical value.
\end{zad}

\begin{zad}
In how many ways can $33$ identical drops be distributed into boxes $A$, $B$, $C$, and $D$ if box $A$ contains at least two drops, box $B$ contains at least five drops, and box $C$ contains \emph{exactly} six drops? (Note that there are no restrictions for box $D$.)  
Provide the answer as an exact numerical value.
\end{zad}

\begin{zad}
A store sells three types of batteries: $AAA$, $AA$, and $9V$. There are only two $9V$ batteries left in stock, but more than $10$ batteries of each of the other two types. Petra wants to buy $10$ batteries and needs at least two $AAA$ batteries. In how many ways can she do this? Calculate the exact numerical value of your solution!
\end{zad}

\begin{zad}
Sara and Matevž are collecting stones and shells on the beach, gathering a total of $12$. There are $4$ types: sharp stones, round stones, ribbed shells, and spiral shells. If stones or shells of the same type are indistinguishable, how many collections of size $12$ can be made:
\begin{enumerate}[label=\rm(\roman*)]
\item without any additional conditions?
\item if they want at least $4$ ribbed shells and $2$ spiral shells?
\item if they want at least one stone or shell of each type and at most $3$ round stones?
\end{enumerate}
Finally, they collected $1$ round stone, $2$ sharp stones, $4$ ribbed shells, and $5$ spiral shells (all colorful and very different) and now wish to divide the loot. Sara wants to keep $2$ stones (round or sharp) and $4$ shells (ribbed or spiral), while Matevž will take the rest.  
\begin{enumerate}[resume, label=\rm(\roman*)]
\item How many different divisions can they make?
\end{enumerate}
\end{zad}






\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}










\newpage
\section{Linear Recursive Equations with Constant Coefficients}

\begin{zad}
Solve the recurrence equation \( F(n) = 4F(n-2) \) with initial conditions \( F(0) = 0 \) and \( F(1) = 4 \).
\end{zad}

\begin{zad}
Solve the recurrence equation \( F(n) = 4F(n-1) - 3F(n-2) \) with initial conditions \( F(0) = 2 \) and \( F(1) = 5 \).
\end{zad}

\begin{zad}
Solve the recurrence equation
\[
F(n) = F(n-1) + F(n-2) - F(n-3)
\]
with initial conditions \( F(0) = F(1) = 0 \) and \( F(2) = 4 \). Use the characteristic equation method.
\end{zad}

\begin{zad}
\textbf{Lucas Sequence} is defined as \( L(0) = 2 \), \( L(1) = 1 \), and \( L(n) = L(n-1) + L(n-2) \) for \( n \geq 2 \).
\begin{enumerate}[label=\rm(\alph*)]
\item Compute the first six terms of the sequence.
\item Derive an explicit (non-recursive) formula for \( L(n) \).
\end{enumerate}
\end{zad}













\section{Recursive Equations}

\begin{zad}
\begin{enumerate}[label=\rm(\roman*)]
\item Alja deposits \(1000\euro{}\) in a local bank at an annual interest rate of \(8\%\). Define recursively the amount \(a_n\) in her account at the end of \(n\) years.
\item In a meeting room, \(n\) guests are present. Each person shakes hands with every other person exactly once. Define recursively the number of handshakes \(h(n)\) that occur, and solve the obtained recurrence equation.
\end{enumerate}
\end{zad}

\begin{zad}
\begin{enumerate}[label=\rm(\roman*)]
\item A bus driver pays a toll using only \(1\euro{}\) and \(2\euro{}\) coins, inserting one coin at a time into a toll machine. Find a recurrence relation for the number of distinct ways the driver can pay a toll of \(n\euro{}\) (considering the order of coins).
\item Solve the recurrence equation \(F(n) = 8F(n-1) - 16F(n-2)\) with initial conditions \(F(0) = -1\) and \(F(1) = 4\). Use the characteristic equation method.
\end{enumerate}
\end{zad}

\begin{zad}
We have \(L\)-shaped tiles that cover \(3\) squares. We want to tile rectangular floors of size \(2 \times n\) squares for \(n \geq 0\). Find a recurrence relation for the number of ways to tile a \(2 \times n\) floor for \(n \geq 2\). Determine the numerical value of the number of ways to tile a \(2 \times 12\) floor.
\end{zad}

\begin{zad}
Let \(a_n\) be the number of all strings of length \(n\) consisting of the letters \(A\), \(B\), and \(C\), but not containing the substring "CA". Find a recurrence relation for \(a_n\). Also, calculate the numerical value of \(a_5\).
\end{zad}

\begin{zad}
Let \(a_n\) denote the number of binary sequences of length \(n\) (sequences of length \(n\) containing only digits \(0\) and \(1\)) that do not contain the subsequence \(001\). 

Find a recurrence relation for \(a_n\) and the initial values. 

Also, determine the numerical value of \(a_6\).
\end{zad}

\begin{zad}
In how many ways can we tile a rectangular floor of size \(2 \times n\) squares, \(n > 0\), using rectangular tiles of size \(1 \times 2\) and \(2 \times 2\) squares? Find a recurrence relation and solve the obtained equation. How many ways are there to tile a floor of size \(2 \times 5\) squares?
\end{zad}

\begin{zad}
Frogs and storks are grazing by the edge of a pond. Each minute, the following happens: in the first half of the minute, each frog present at the beginning of the minute attracts three new frogs and one new stork. In the second half of the minute, each stork eats one frog. Initially, there are two frogs and one stork. Write a recurrence relation that gives the number of frogs and storks at the beginning of the \(n\)-th minute for all \(n \in \mathbb{Z}^+_0\).
\end{zad}

\begin{zad}
We have square tiles of size \(1 \times 1\) and rectangular tiles of size \(1 \times 2\). We want to tile a rectangular floor of size \(2 \times n\) squares for \(n \geq 0\), such that the longer edges of two parallel rectangular tiles must align completely, i.e., the following arrangement is not allowed:
\begin{center}
\includegraphics{dn1}
\end{center}
Let \(F(n)\) denote the number of different tilings for a \(2 \times n\) floor.
\begin{enumerate}[label=\rm(\alph*)]
\item Justify that the equation \(F(n) = 2F(n-1) + 3F(n-2)\) gives a recurrence relation for the number of different tilings for \(n \geq 2\).
\item Write the initial conditions and verify your result by listing all possible tilings for a floor of size \(2 \times 2\) squares and comparing it with the result obtained using the recurrence relation.
\item Provide an explicit equation for \(F(n)\).
\end{enumerate}
\end{zad}

\begin{zad}
We have square tiles of size \(1 \times 1\) and \(L\)-shaped tiles (covering 3 squares). We want to tile a rectangular floor of size \(2 \times n\) squares for \(n \geq 0\), but the following arrangement is not allowed:
\begin{center}
\includegraphics{ploscice4}
\end{center}
\begin{enumerate}[label=\rm(\alph*)]
\item Find a recurrence relation for the number of ways to tile a \(2 \times n\) floor for \(n \geq 2\).
\item Write the initial conditions and verify your result by listing all possible tilings for a floor of size \(2 \times 2\) squares and comparing it with the result obtained using the recurrence relation.
\end{enumerate}
\end{zad}

\begin{zad}
We have square tiles of size \(1 \times 1\) and \(I\)-shaped tiles (covering 3 squares). We want to tile a rectangular floor of size \(2 \times n\) squares for \(n \geq 0\), but the following arrangements are not allowed:
\begin{center}
\includegraphics[scale=0.8]{plosckeOlikeCrkeI}
\end{center}
Let \(F(n)\) denote the number of different tilings for a \(2 \times n\) floor.
\begin{enumerate}[label=\rm(\alph*)]
\item Find a recurrence relation for \(F(n)\) for \(n \geq 3\).
\item Calculate \(F(6)\).
\end{enumerate}
\end{zad}







\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}











\newpage
\section{Distributions}

\begin{zad}
\begin{enumerate}[label=\rm(\alph*)]
\item Write down all the possibilities for arranging three different items (apple, orange, and banana) into two {\em distinct} boxes so that no box is empty.
\item Let $n$ be a natural number. Provide a combinatorial proof of the following equation:
$$
S(n,2) = 2^{n-1} - 1.
$$
\end{enumerate}
\end{zad}

\begin{zad}
In how many ways can we arrange $8$ different rings into $3$ boxes,
\begin{enumerate}[label=\rm(\alph*)]
\item if the boxes are identical and each box must contain at least one ring?
\item if the boxes are distinct and each box must contain at least one ring?
\end{enumerate}
Provide the result as an exact numerical value. Before computing the numerical values, list at least three examples of possible arrangements.
\end{zad}

\begin{zad}
In how many ways can $10$ indistinguishable balls be placed into eight distinguishable containers?
\end{zad}

\begin{zad}
In how many ways can four different employees be assigned to three indistinguishable offices if each office can accommodate any number of employees?
\end{zad}

\begin{zad}
Four fishermen went to a lake to catch fish. At the end of the day, they collectively caught $11$ identical fish. They now need to divide these $11$ fish into $4$ identical bags. In how many ways can this be done if
\begin{enumerate}[label=\rm(\alph*)]
\item each bag contains at least one fish?
\item some bags can be empty?
\end{enumerate}
Provide the results as exact numerical values.
\end{zad}

\begin{zad}
Four fishermen went to a lake to catch fish. At the end of the day, they collectively caught $13$ identical fish. They now need to divide these fish among themselves. In how many ways can this be done if:
\begin{enumerate}[label=\rm(\alph*)]
\item each fisherman must receive at least one fish?
\item some fishermen can receive no fish?
\end{enumerate}
Provide the results as exact numerical values.
\end{zad}

\begin{zad}
We need to assign $6$ distinct household chores to $5$ workers such that each worker gets at least one chore. In how many ways can this be done?
\end{zad}

\begin{zad}
A standard deck of cards has $52$ distinct cards. Each of the four suits (spades, clubs, hearts, diamonds) contains $13$ cards, ranging from Ace (the lowest) to King (the highest). In how many ways can all the cards be distributed among $4$ players such that each player receives at least one card?
\end{zad}

\begin{zad}
In how many ways can eight DVDs be packed into three boxes such that each box contains at least one DVD, if we have
\begin{enumerate}[label=\rm(\alph*)]
\item eight different DVDs and three indistinguishable boxes,
\item eight different DVDs and three distinguishable boxes?
\end{enumerate}
Provide the results as exact numerical values.
\end{zad}

\begin{zad}
In how many ways can eight DVDs be packed into three boxes such that each box contains at least one DVD, if we have
\begin{enumerate}[label=\rm(\alph*)]
\item eight different DVDs and three distinguishable boxes,
\item eight indistinguishable DVDs and three indistinguishable boxes,
\item eight indistinguishable DVDs and three distinguishable boxes?
\end{enumerate}
Provide the results as exact numerical values.
\end{zad}

\begin{zad}
In how many ways can seven different balls be distributed into four indistinguishable boxes if each box can contain any number of balls?

There is no need to provide the result as an exact numerical value.
\end{zad}

\begin{zad}
In how many ways can four different employees be assigned to three indistinguishable offices if each office can accommodate any number of employees?
\end{zad}

\begin{zad}
In $4$ distinct art classes, we enroll $12$ children. Among the children, there are two pairs of siblings, and siblings are not to be placed in separate groups. Count the different ways to do this, ensuring that no class is empty.
\end{zad}

\begin{zad}
\begin{enumerate}[label=\rm(\alph*)]
\item We want to divide $12$ children into four playgroups. However, there are {\bf exactly two pairs} of siblings among the children, and siblings are not to be placed in separate groups. How many possibilities do we have?
\item In how many ways can $30$ mangoes be divided into three identical baskets? Some baskets may remain empty.
\end{enumerate}

\medskip
Provide exact numerical values for your results.
\end{zad}

\begin{zad}
In how many ways can $9$ rings be distributed among $4$ fingers of the right hand (excluding the thumb), if:
\begin{enumerate}[label=\rm(\alph*)]
\item the rings are indistinguishable, and the fingers can also be empty?
\item the rings are indistinguishable, and each finger must have at least one ring?
\item the rings are distinct, the order of rings on a finger does not matter, and the fingers can also be empty?
\item the rings are distinct, the order of rings on a finger does not matter, and each finger must have at least one ring?
\item the rings are distinct, the order of rings on a finger matters, and the fingers can also be empty?
\item the rings are distinct, the order of rings on a finger matters, and each finger must have at least one ring?
\end{enumerate}
Provide the result as an exact numerical value. Before calculating the numerical values, list at least three examples of possible arrangements.
\end{zad}







\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}








\newpage
\section{Graph Theory}

\begin{zad}
Determine the number of edges in a graph with $6$ vertices, where $2$ vertices have degree $4$ and $4$ vertices have degree $2$. Draw two such connected graphs.
\end{zad}

\begin{zad}
The following graph $G$ is given:
\begin{center}
\definecolor{uuuuuu}{rgb}{0,0,0}
\begin{tikzpicture}[scale=.7,line cap=round,line join=round,>=triangle 45,x=1cm,y=1cm]
\draw [line width=1pt] (-3.2360679774997894,1.8042260651806146)-- (0,4.155367074350506);
\draw [line width=1pt] (0,4.155367074350506)-- (3.23606797749979,1.804226065180613);
\draw [line width=1pt] (3.23606797749979,1.804226065180613)-- (2,-2);
\draw [line width=1pt] (2,-2)-- (-2,-2);
\draw [line width=1pt] (-2,-2)-- (-3.2360679774997894,1.8042260651806146);
\draw [line width=1pt] (0,4.155367074350506)-- (2,-2);
\draw [line width=1pt] (-2,-2)-- (0,4.155367074350506);
\draw [line width=1pt] (-3.2360679774997894,1.8042260651806146)-- (3.23606797749979,1.804226065180613);
\draw [line width=1pt] (-2,-2)-- (3.23606797749979,1.804226065180613);
\draw [line width=1pt] (-3.2360679774997894,1.8042260651806146)-- (2,-2);
\draw [line width=1pt] (0,0.7527638409423467)-- (-0.6180339887498946,-0.09788696740969288);
\draw [line width=1pt] (0,0.7527638409423467)-- (0.6180339887498952,-0.09788696740969335);
\draw [line width=1pt] (0,0.7527638409423467)-- (1,1.0776835371752527);
\draw [line width=1pt] (0,0.7527638409423467)-- (0,1.8042260651806137);
\draw [line width=1pt] (-1,1.0776835371752533)-- (0,0.7527638409423467);
\begin{scriptsize}
\draw [fill=uuuuuu] (-2,-2) circle (2.5pt);
\draw[color=uuuuuu] (-2.32,-2.03) node {$A$};
\draw [fill=uuuuuu] (2,-2) circle (2.5pt);
\draw[color=uuuuuu] (2.3,-2.01) node {$B$};
\draw [fill=uuuuuu] (3.23606797749979,1.804226065180613) circle (2.5pt);
\draw[color=uuuuuu] (3.5,1.97) node {$C$};
\draw [fill=uuuuuu] (0,4.155367074350506) circle (2.5pt);
\draw[color=uuuuuu] (0.16,4.59) node {$D$};
\draw [fill=uuuuuu] (-3.2360679774997894,1.8042260651806146) circle (2.5pt);
\draw[color=uuuuuu] (-3.5,2.09) node {$E$};
\draw [fill=uuuuuu] (0,0.7527638409423467) circle (2pt);
\draw[color=uuuuuu] (0.16,1.15) node {$F$};
\draw [fill=uuuuuu] (1,1.0776835371752527) circle (2pt);
\draw[color=uuuuuu] (1.28,1.35) node {$L$};
\draw [fill=uuuuuu] (0,1.8042260651806137) circle (2pt);
\draw[color=uuuuuu] (0.16,2.19) node {$M$};
\draw [fill=uuuuuu] (-1,1.0776835371752533) circle (2pt);
\draw[color=uuuuuu] (-1.38,1.51) node {$N$};
\draw [fill=uuuuuu] (-0.6180339887498946,-0.09788696740969288) circle (2pt);
\draw[color=uuuuuu] (-0.88,-0.25) node {$O$};
\draw [fill=uuuuuu] (0.6180339887498952,-0.09788696740969335) circle (2pt);
\draw[color=uuuuuu] (0.8,-0.23) node {$P$};
\draw (-2,4.09) node {\Large $G$};
\end{scriptsize}
\end{tikzpicture}
\end{center}
\begin{enumerate}[label=\rm(\roman*)]
\item Provide an example of a subgraph with $6$ vertices that is not an induced subgraph.
\item Provide an example of an induced subgraph with $6$ vertices.
\item Provide an example of a walk of length $7$ that is not a path.
\item Provide an example of a graph $H$ with vertex set $\{a,b,c,d,e,f,p,l,m,n,o\}$ that is isomorphic to the given graph $G$ and is drawn in a different way.
\item Is $G$ planar? (Provide a detailed justification for your answer.)
\item Is $\chi(G) = 2$? (Provide a detailed justification for your answer.)
\end{enumerate}
\end{zad}






\section{Graph}

\begin{zad}
\begin{enumerate}[label=\rm(\roman*)]
\item Let $e_1, e_2, \ldots, e_n$ be the edges of graph $G$, and let $x_{i-1}$ and $x_i$ be the endpoints of edge $e_i$ $(1 \leq i \leq n)$. Show that any closed walk $(e_1, e_2, \ldots, e_n)$ of length at least $3$ with pairwise distinct vertices $x_1, x_2, \ldots, x_n$ is a cycle.
\item A graph that contains no cycles is called {\bf acyclic}. A walk is acyclic if the subgraph consisting of the vertices and edges of the walk is acyclic.  
Prove: A walk has all distinct vertices if and only if it is an acyclic trail.
\item If $u$ and $v$ are distinct vertices of graph $G$, and there exists a walk in $G$ from $u$ to $v$, show that there exists an acyclic trail from $u$ to $v$. {\it (Explain in detail why every shortest walk from $u$ to $v$ is in fact an acyclic trail.)}
\end{enumerate}
\end{zad}

\begin{zad}
Show that the sum of the degrees of all vertices in a graph is equal to twice the number of edges, i.e., 
$$
\sum_{v \in V(G)} d(v) = 2 \cdot |E(G)|.
$$
\end{zad}

\begin{zad}
Let $G$ be a simple graph with $n$ vertices. Show that $G$ must be connected if it has more than $\frac{(n-1)(n-2)}{2}$ edges.
\end{zad}

\section{Tree}

\begin{zad}
Given a tree with exactly five vertices of degree $2$, three vertices of degree $3$, four vertices of degree $4$, and no vertices of degree greater than $4$, determine how many vertices of degree $1$ the tree has.
\end{zad}

\begin{zad}
Let $G$ be a simple graph with $n$ vertices and $n-1$ edges. Is it true that $G$ is a forest if and only if $G$ is connected? Prove the statement or provide a counterexample.
\end{zad}

\begin{zad}
Show that for any tree $T$, there exists exactly one path between every pair of vertices.
\end{zad}

\begin{zad}
Show that if a graph $G$ has exactly one path between every pair of vertices, then $G$ is a tree.
\end{zad}

\begin{zad}
Prove that every tree is a planar graph.
\end{zad}

\begin{zad}
Let $T$ be a tree. Show that if $T$ contains a vertex of degree $k \geq 2$, then it also contains at least $k$ vertices of degree $1$.
\end{zad}

\begin{zad}
Prove: If an edge $e$ is the heaviest edge in a cycle $C$ of a weighted graph $G$, then there exists a minimum spanning tree of $G$ that does not include edge $e$.
\end{zad}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%





\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}







\newpage
\section{Graph Homomorphisms}

\begin{zad}
Let $G = (V,E)$ and $G' = (V',E')$ be (simple) graphs. 
We say that a graph $G$ is {\bf homomorphic} to a graph $G'$ if there exists a mapping $\phi : V \to V'$ such that for every edge $\{x,y\} \in E$ of graph $G$, it holds that $\{\phi(x),\phi(y)\} \in E'$.
Such a mapping $\phi$ is called a {\bf homomorphism} of graph $G$ to graph $G'$ and is denoted as $\phi : G \to G'$.

\medskip
Show that for any three graphs $G_1$, $G_2$, and $G_3$, if there exists a homomorphism $f : G_1 \to G_2$ and a homomorphism $g : G_2 \to G_3$, then there also exists a homomorphism $h : G_1 \to G_3$.
Using the proof, find the corresponding homomorphisms for the following graphs:
\begin{center}
\includegraphics[scale=.8]{homomorfizem-triGr}
\end{center}
\end{zad}






\section{Induced Subgraph, Graph Isomorphisms, and Closed Walks}

\begin{zad}
We are given a graph $G$:
\begin{center}
\begin{tikzpicture}[scale=.35]
\node at (5.84,-2.232050807568878) {$f$};
\node at (5.84,2.232050807568878) {$e$};
\node at (-0.62,-0.6) {$c$};
\node at (1.84,-0.6) {$d$};
\node at (-4.62,2.2320508075688774) {$a$};
\node at (-4.62,-2.2320508075688774) {$b$};
\draw [line width=1pt] (5.34,-1.732050807568878)-- (2.34,0); %%df
\draw [line width=1pt] (-4.12,-1.7320508075688776)-- (-4.12,1.7320508075688774); %%ba
\draw [line width=1pt] (-1.12,0)-- (-4.12,1.7320508075688774); %%ac
\draw [line width=1pt] (-4.12,-1.7320508075688776)-- (-1.12,0); %%bc
\draw [line width=1pt] (2.34,0)-- (5.34,1.732050807568878); %%de
\draw [line width=1pt] (-4.12,1.7320508075688776)-- (5.34,1.732050807568878); %%ae
\draw [line width=1pt] (-4.12,-1.7320508075688776)-- (5.34,-1.732050807568878); %%bf
\draw [line width=1pt] (5.34,1.732050807568878)-- (5.34,-1.732050807568878); %%ef
%% \draw [line width=1pt] (2.34,0) %%vozlisce d
%%\draw [line width=1pt] (-1.12,0)-- (2.34,0); %%cd
\fill (-1.12,0) circle [radius=0.27];
\fill (2.34,0) circle [radius=0.27];
\fill (2.34,0) (5.34,1.732050807568878) circle [radius=0.27];
\fill (2.34,0) (5.34,-1.732050807568878) circle [radius=0.27];
\fill (2.34,0) (-4.12,1.7320508075688774) circle [radius=0.27];
\fill (2.34,0) (-4.12,-1.7320508075688776) circle [radius=0.27];
\node at (0.61,-4) {$G$};
\end{tikzpicture}
\end{center}
\vspace{-7mm}
\begin{enumerate}[label=\rm(\alph*)]
\item For the graph $G$ in the figure, provide an example of an induced subgraph that is not bipartite and has 5 vertices.

\item Find four isomorphisms of graph $G$ onto itself (i.e., graph $G$ onto itself). 
(An isomorphism of graph $G$ onto itself is called an {\it automorphism} of graph $G$).

\item For the graph $G$ in the figure, provide an example of a closed walk that includes all edges of the graph, or explain why such a walk does not exist.
\end{enumerate}
\end{zad}

\section{Graph Isomorphisms}

\begin{zad}
Determine which pairs of graphs are isomorphic.

\medskip
\centering\includegraphics[width=0.5\textwidth]{ex2-class1.png}
\end{zad}


\begin{zad}
For the graph $G$ in the figure:
\begin{center}
	\begin{tikzpicture}[vertex/.style={inner sep=2pt,draw,circle}]	
	\begin{scope}
	\node[vertex, label=above:$ u $] (2) at (-1.5,2) {};
	\node[vertex, label=above:$ v $] (3) at (-0.5,2) {};
	\node[vertex, label=above:$ w $] (4) at (0.5,2) {};
	\node[vertex, label=above:$ x $] (5) at (1.5,2) {};
	\node[vertex, label=right:$ y $] (1) at (0,0) {};
	\path (1) edge (2);
	\path (1) edge (3);
	\path (1) edge (4);
	\path (1) edge (5);
	\path (2) edge (3);
	\path (3) edge (4);
	\path (4) edge (5);
	\pgftext[base, x=0cm,y=-0.75cm]{$G$};
	\end{scope}
	\end{tikzpicture}
\end{center}
\begin{enumerate}[label=\rm(\alph*)]
\item Provide examples of three pairs of non-isomorphic spanning trees.
\item Provide examples of three pairs of non-isomorphic spanning subgraphs that are not bipartite.
\end{enumerate}
Justify your answer precisely.
\end{zad}




\begin{zad}
We are given the following graphs:
\begin{center}
	\begin{tikzpicture}[vertex/.style={inner sep=2pt,draw,circle}]	
	\begin{scope}
	\node[vertex, label=below:$ a $] (1) at (0,0) {};
	\node[vertex, label=left:$ b $] (2) at (-1.5,0.5) {};
	\node[vertex, label=right:$ c $] (3) at (1.5,0.5) {};
	\node[vertex, label=left:$ d $] (4) at (-1,1) {};
	\node[vertex, label=right:$ e $] (5) at (1,1) {};
	\node[vertex, label=left:$ f $] (6) at (-2,1.5) {};
	\node[vertex, label=right:$ g $] (7) at (2,1.5) {};
	\node[vertex, label=above:$ h $] (8) at (-0.5,2) {};
	\node[vertex, label=above:$ i $] (9) at (0.5,2) {};
	\node[vertex, label=left:$ j $] (10) at (-1.5,2.5) {};
	\node[vertex, label=right:$ k $] (11) at (1.5,2.5) {};
	\node[vertex, label=above:$ \ell $] (12) at (0,3) {};
	\path (1) edge (2);	
	\path (1) edge (3);	
	\path (1) edge (8);	
	\path (1) edge (9);		
	\path (2) edge (4);	
	\path (2) edge (6);	
	\path (3) edge (5);	
	\path (3) edge (7);
	\path (4) edge (5);
	\path (4) edge (10);
	\path (5) edge (11);
	\path (6) edge (8);
	\path (6) edge (10);
	\path (7) edge (9);
	\path (7) edge (11);
	\path (8) edge (12);
	\path (9) edge (12);
	\path (10) edge (12);
	\path (11) edge (12);
	\pgftext[base, x=0cm,y=-1cm]{$G$};
	\end{scope}
	
	
	\begin{scope}[xshift=5cm, yshift=1cm]
	\node[vertex, label=below:$ p $] (1) at (3,-1) {};
	\node[vertex, label=below:$ o $] (2) at (1.5,-1) {};
	\node[vertex, label=below:$ q $] (3) at (4.5,-1) {};
	\node[vertex, label=above:$ t $] (4) at (2,0) {};
	\node[vertex, label=above:$ u $] (5) at (4,0) {};
	\node[vertex, label=right:$ s $] (6) at (1,0) {};
	\node[vertex, label=left:$ v $] (7) at (5,0) {};
	\node[vertex, label=left:$ r $] (8) at (0,0) {};
	\node[vertex, label=right:$ w $] (9) at (6,0) {};
	\node[vertex, label=above:$ x $] (10) at (1.5,1) {};
	\node[vertex, label=above:$ z $] (11) at (4.5,1) {};
	\node[vertex, label=above:$ y $] (12) at (3,1) {};
	\path (1) edge (2);	
	\path (1) edge (3);	
	\path (1) edge (8);	
	\path (1) edge (9);		
	\path (2) edge (4);	
	\path (2) edge (6);	
	\path (3) edge (5);	
	\path (3) edge (7);
	\path (4) edge (5);
	\path (4) edge (10);
	\path (5) edge (11);
	\path (6) edge (8);
	\path (6) edge (10);
	\path (7) edge (9);
	\path (7) edge (11);
	\path (8) edge (12);
	\path (9) edge (12);
	\path (10) edge (12);
	\path (11) edge (12);	
	\pgftext[base, x=3cm,y=-2cm]{$H$};
	\end{scope}
	\end{tikzpicture}
\end{center}

Are the graphs $G$ and $H$ isomorphic? Provide a precise justification for your answer.
\end{zad}



\begin{zad}
We are given a graph $G$:
\begin{center}
\begin{tikzpicture}[scale=.4]
\draw [line width=1pt] (2.34,0)-- (5.34,1.732050807568878);
\node at (5.84,-2.232050807568878) {$x$};
\node at (5.84,2.232050807568878) {$y$};
\node at (-0.62,-0.6) {$v$};
\node at (1.84,-0.6) {$w$};
\node at (-4.62,2.2320508075688774) {$z$};
\node at (-4.62,-2.2320508075688774) {$u$};
\draw [line width=1pt] (5.34,-1.732050807568878)-- (2.34,0);
\draw [line width=1pt] (-1.12,0)-- (-4.12,1.7320508075688774);
\draw [line width=1pt] (-4.12,-1.7320508075688776)-- (-1.12,0);
\draw [line width=1pt] (-1.12,0)-- (2.34,0);
\fill (-1.12,0) circle [radius=0.27];
\fill (2.34,0) circle [radius=0.27];
\fill (2.34,0) (5.34,1.732050807568878) circle [radius=0.27];
\fill (2.34,0) (5.34,-1.732050807568878) circle [radius=0.27];
\fill (2.34,0) (-4.12,1.7320508075688774) circle [radius=0.27];
\fill (2.34,0) (-4.12,-1.7320508075688776) circle [radius=0.27];
\node at (0.61,-4) {$G$};
\end{tikzpicture}
\end{center}
Find all isomorphisms of graph $G$ onto itself (i.e., graph $G$ onto itself). 
(An isomorphism of graph $G$ onto itself is called an {\it automorphism} of graph $G$). Provide a precise justification for your answer.
\end{zad}


\begin{zad}
We are given a graph $G$:
\begin{center}
\begin{tikzpicture}[scale=.35]
\draw [line width=1pt] (2.34,0)-- (5.34,1.732050807568878);
\node at (5.84,-2.232050807568878) {$f$};
\node at (5.84,2.232050807568878) {$e$};
\node at (-0.62,-0.6) {$c$};
\node at (1.84,-0.6) {$d$};
\node at (-4.62,2.2320508075688774) {$a$};
\node at (-4.62,-2.2320508075688774) {$b$};
\draw [line width=1pt] (5.34,-1.732050807568878)-- (2.34,0);
\draw [line width=1pt] (-4.12,-1.7320508075688776)-- (-4.12,1.7320508075688774);
\draw [line width=1pt] (-1.12,0)-- (-4.12,1.7320508075688774);
\draw [line width=1pt] (-4.12,-1.7320508075688776)-- (-1.12,0);
\draw [line width=1pt] (-1.12,0)-- (2.34,0);
\fill (-1.12,0) circle [radius=0.27];
\fill (2.34,0) circle [radius=0.27];
\fill (2.34,0) (5.34,1.732050807568878) circle [radius=0.27];
\fill (2.34,0) (5.34,-1.732050807568878) circle [radius=0.27];
\fill (2.34,0) (-4.12,1.7320508075688774) circle [radius=0.27];
\fill (2.34,0) (-4.12,-1.7320508075688776) circle [radius=0.27];
\node at (0.61,-4) {$G$};
\end{tikzpicture}
\end{center}
Find all isomorphisms of the graph $G$ onto the graph $G$ (i.e., the graph $G$ onto itself).  
(An isomorphism of the graph $G$ onto itself is called an {\it automorphism} of the graph $G$).  
\end{zad}











\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}







\newpage
\section{Eulerian and Hamiltonian Graph.}

\begin{zad}
Does the following digraph have
\begin{center}
\includegraphics[width=.35\textwidth]{digraph.png}
\end{center}
\begin{enumerate}[label=\rm(\roman*)]
\item an Eulerian circuit?
\item a non-closed Eulerian trail?
\item a Hamiltonian cycle?
\item a Hamiltonian path?
\end{enumerate}
For each question, if the answer is affirmative, draw the circuit/trail/cycle/path. If the answer is negative, provide a justification.
\end{zad}

\begin{zad}
For each of the following graphs, determine:
\begin{enumerate}[label=\rm(\alph*)]
\item whether it contains an induced subgraph that is non-bipartite and has $6$ vertices;
\item whether it is Eulerian;
\item whether it contains a non-closed Eulerian trail;
\item whether it is Hamiltonian.
\end{enumerate}
\begin{center}
\includegraphics[scale=1.2]{tri-grafi-e-ham_v8}
\end{center}
\end{zad}

\begin{zad}
Let $G$ be a simple graph with $n$ vertices and $m$ edges, where $n \geq 3$. Assume that $m \geq \frac{(n-1)(n-2)}{2} + 2$. Prove that $G$ is Hamiltonian. Does the converse hold?
\end{zad}

\section{Eulerian Graph. Hamiltonian Graph. Kruskal's Algorithm.}

\begin{zad}
Use Kruskal's algorithm to find a minimum spanning tree for the graph given in the figure below. Describe all the steps of the algorithm and state the weight of the resulting tree.
\begin{center}
\includegraphics[width=.4\textwidth]{kruskal-dn2}
\end{center}
\end{zad}

\begin{zad}
Given the following graph $G$:
\begin{center}
\includegraphics[scale=1]{ham}
\end{center}
\begin{enumerate}[label=\rm(\alph*)]
\item Determine if $G$ has a Hamiltonian cycle. If $G$ has a Hamiltonian cycle, find one. If it does not, provide a justification explaining why such a cycle does not exist.
\item Is $G$ an Eulerian graph? Justify your answer.
\item Provide an example of a spanning tree for the graph $G$ shown.
\item Give an example of a spanning subgraph of $G$ that is not bipartite.
\end{enumerate}
\end{zad}

\begin{zad}
Consider the following graph $H$:

\begin{center}
	\begin{tikzpicture}[scale=1, vertex/.style={inner sep=2pt,draw,circle}]
	\begin{scope}
	\node[vertex, label=below:$ a $] (1) at (0,0) {};
	\node[vertex, label=below:$ b $] (2) at (2,0) {};
	\node[vertex, label=below:$ c $] (3) at (4,0) {};
	\node[vertex, label=above:$ f $] (4) at (0,1.5) {};
	\node[vertex, label=above:$ e $] (5) at (2,1.5) {};
	\node[vertex, label=above:$ d $] (6) at (4,1.5) {};
	\path (1) edge (2);
	\path (1) edge (6);
	\path (1) edge (5);
    \path (1) edge[bend right=75, looseness=0.75] (3);	
	\path (2) edge (3);
	\path (2) edge (4);
	\path (2) edge (6);
	\path (3) edge (5);
	\path (3) edge (4);
	\path (4) edge (5);
    \path (4) edge[bend left=75, looseness=0.75] (6);	
	\path (5) edge (6);	
	\pgftext[base, x=5cm,y=-0.75cm]{\small$H$};
	\end{scope}
	\end{tikzpicture}
\end{center}
\begin{enumerate}[label=\rm(\alph*)]
  \item Is $H$ regular?
  \item Is $H$ Hamiltonian?
  \item Is $H$ Eulerian?
\end{enumerate}
Justify your answers.
\end{zad}

\begin{zad}
Consider the following graph $G$ with edge weights:
\begin{center}
	\begin{tikzpicture}[vertex/.style={inner sep=2pt,draw,circle}]
	\begin{scope}
	\node[vertex, label=below:$ a $] (1) at (0,0) {};
	\node[vertex, label=below:$ b $] (2) at (2,0) {};
	\node[vertex, label=below:$ c $] (3) at (4,0) {};
	\node[vertex, label=left:$ d $] (4) at (0,2) {};
	\node[vertex, label=above:$ e $] (5) at (2,2) {};
	\node[vertex, label=right:$ f $] (6) at (4,2) {};
	\draw (2) -- (3) -- (6) -- (2) -- (5) -- (6);
	\draw (1) -- (4) -- (2) -- (1);
	\draw (4) -- (5);
	\path (1) edge[bend right=45, looseness=0.9] (3);
	\path (1) edge[bend left=100, looseness=2.2] (5);
	\path (3) edge[bend right=100, looseness=2.2] (5);
	\pgftext[base, x=1cm,y=-0.3cm]{$13$};
	\pgftext[base, x=3cm,y=-0.3cm]{$8$};
	\pgftext[base, x=1cm,y=2.15cm]{$10$};
	\pgftext[base, x=3cm,y=2.15cm]{$13$};	
	\pgftext[base, x=-0.25cm,y=1cm]{$12$};
	\pgftext[base, x=4.25cm,y=1cm]{$10$};
	\pgftext[base, x=2cm,y=-1.15cm]{$12$};
	\pgftext[base, x=2.25cm,y=1cm]{$13$};	
	\pgftext[base, x=1cm,y=1.15cm, rotate=-45]{$13$};
	\pgftext[base, x=3cm,y=1.15cm, rotate=45]{$9$};
	\pgftext[base, x=-0.45cm,y=2.45cm, rotate=45]{$8$};
	\pgftext[base, x=4.45cm,y=2.45cm, rotate=-45]{$12$};
	\end{scope}
	\end{tikzpicture}
\end{center}

\begin{enumerate}[label=\rm(\alph*)]
\item Use Kruskal’s algorithm to find the minimum spanning tree in graph $G$ and determine its weight. Describe each step of the algorithm.
\item Is the minimum spanning tree uniquely determined? Justify your answer.
\item Can we orient the edges of graph $G$ such that the resulting digraph $D$ is strongly connected? Provide an appropriate orientation or justify why it does not exist.
\item Can we orient the edges of graph $G$ such that the resulting digraph $D$ contains an Eulerian circuit? Provide an appropriate orientation or justify why it does not exist.
\end{enumerate}
\end{zad}

\begin{zad}
Let $G$ be the following weighted connected graph.

\begin{center}
\begin{tikzpicture}[scale=.55]
\GraphInit[vstyle=Dijkstra]
\SetVertexMath
\SetGraphUnit{4}
\node at (-5,7) {\Large{$G$}};
				\Vertices{square}{g,d,a,f}
				\WE(f){h}
				\EA(a){b}
				\EA(d){c}
				\NO(a){e}
				\Edge[label=$1$](h)(f)
				\Edge[label=$4$](g)(f)
				\Edge[label=$2$](h)(g)
				\Edge[label=$2$](g)(d)
				\Edge[label=$3$](d)(c)
				\Edge[label=$4$](f)(e)
				\Edge[label=$3$](a)(d)
				\Edge[label=$2$](a)(e)
\Edge[label=$1$](a)(b)
\Edge[label=$2$](a)(c)
\Edge[label=$2$](c)(b)
\Edge[label=$3$](e)(b)
\end{tikzpicture}
\end{center}

\begin{enumerate}[label=\rm(\alph*)]
\item Use Kruskal’s greedy method to find the minimum spanning tree (minimum connector) of graph $G$. Explain all the steps required to obtain your solution.
\item Determine if the tree computed in the previous part is unique, i.e., if there is another tree with the same weight that can be found using Kruskal’s method.
\item Is $G$ Hamiltonian? If so, find a Hamiltonian cycle in $G$.
\item Calculate $\chi(G)$.
\item Show that there is a graph homomorphism from $G$ to the complete graph $K_r$, where $r = \chi(G)$.
\end{enumerate}
\end{zad}











\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}







\newpage
\section{Digraph}

\begin{zad}
Consider the following digraph $D$.
\begin{center}
\includegraphics[width=0.2\textwidth]{digraph}
\end{center}
\begin{enumerate}[label=\rm(\roman*)]
\item Find the difference between the in-degree and out-degree for each vertex.
\item Does $D$ contain an Eulerian circuit? Justify your answer.
\end{enumerate}
\end{zad}

\begin{zad}
Two special types of vertices are more interesting in digraphs than in undirected graphs. A vertex that is not the tail of any edge, i.e., with no "arrows" leading away from it, is called a {\bf sink}. A {\bf source} is a vertex that is not the head of any edge.

\medskip
Consider the given digraph $D$.
%%\includegraphics[scale=.25]{digraph-e}
\begin{center}
\begin{tikzpicture}[->,>=stealth, node distance=2cm, auto, thick, state/.style={inner sep=2pt,draw,circle}]
    \node[state] (v) {$v$};
    \node[state] (u) [right of=v] {$u$};
    \node[state] (t) [right of=u] {$t$};
    \node[state] (w) [right of=t] {$w$};
    \node[state] (z) [right of=w] {$z$};
    \node[state] (x) [below of=t] {$x$};
    \node[state] (y) [below of=w] {$y$};

    \path (u) edge[bend left] (v)
              edge[bend right] (v)
          (t) edge (u)
          (t) edge (w)
              edge (x)
          (z) edge (w)
          (w) edge (y)
          (x) edge (y);

\end{tikzpicture}
\end{center}
\begin{enumerate}[label=\rm(\roman*)]
\item Is $D$ weakly connected?
\item Is $D$ strongly connected?
\item Does there exist a cycle in the digraph $D$?
\item Identify all sinks in the digraph $D$.
\item Identify all sources in the digraph $D$.
\end{enumerate}
\end{zad}

\begin{zad}
\begin{enumerate}[label=\rm(\alph*)]
\item Provide three different examples of directed graphs with the vertex set $\{a,b,c,d,e,f,g,h\}$. Recall that a directed graph is a digraph whose underlying graph is simple.
\item Determine the number of directed graphs with the vertex set $\{a,b,c,d,e,f,g,h\}$.
\item Provide three different examples of digraphs with the vertex set $\{a,b,c,d,e,f,g,h\}$ that do not contain multiple edges or loops.
\item Determine the number of digraphs with the vertex set $\{a,b,c,d,e,f,g,h\}$ that do not contain multiple edges or loops.
\end{enumerate}
\end{zad}

\begin{zad}
Prove that for every natural number $n \geq 2$, the edges of a complete graph on $n$ vertices can be oriented such that all vertices of the resulting digraph have different out-degrees.
\end{zad}

\begin{zad}
In class, we showed that the number of simple graphs with the vertex set $\{1, 2, \ldots, n\}$ is $2^{{n \choose 2}}$.
\begin{enumerate}[label=\rm(\alph*)]
\item Determine the number of digraphs with the vertex set $\{1, 2, \ldots, n\}$ that do not contain multiple edges (i.e., more than one directed edge from the same start vertex to the same end vertex) or loops (i.e., directed edges that connect a vertex to itself).
\item Determine the number of digraphs with the vertex set $\{1, 2, \ldots, n\}$ that do not contain multiple edges, but each vertex can have at most one loop.
\item Determine the number of directed graphs with the vertex set $\{1, 2, \ldots, n\}$.
\item A {\bf tournament} is a directed graph whose underlying graph is complete. Determine the number of tournaments with the vertex set $\{1, 2, \ldots, n\}$.
\end{enumerate}
\end{zad}

\begin{zad}
Show that a digraph $D$ in which all vertices have the same in-degree as out-degree is strongly connected if and only if it is weakly connected.
\end{zad}

\begin{zad}
\label{hGr}
Two special types of vertices are more interesting in digraphs than in undirected graphs. A vertex that is not the tail of any edge, i.e., with no "arrows" leading away from it, is called a {\bf sink}. A {\bf source} is a vertex that is not the head of any edge.

\medskip
Show that every acyclic digraph has at least one sink and at least one source.
\end{zad}

\begin{zad}
If the vertices of a digraph with $n$ vertices can be labeled from $1$ to $n$ such that $i > j$ whenever there is a path from vertex $i$ to vertex $j$, then this labeling is called a {\bf topological ordering}.

\medskip
Show that every acyclic digraph has at least one topological ordering.
\end{zad}





\section{Tree and Digraph}

\begin{zad}
Let $T$ be a tree. Show that the edges of the tree $T$ can be oriented so that in the resulting directed graph, the in-degree and out-degree of each vertex differ by at most one.
\end{zad}






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Matching}

\begin{zad}
If all vertices of a graph $G$ have the same degree $k$, the graph is called {\bf $\boldsymbol{k}$-regular}.

Let $k > 0$ and $G$ be a bipartite $k$-regular graph with bipartition $\{A, B\}$. Show that the graph $G$ has a matching that saturates $A$.
\end{zad}







\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}







\newpage
\section{Planar Graphs and the Chromatic Number of a Graph}

\begin{zad}
Consider the following two graphs:
\begin{enumerate}[label=\rm(\roman*)]
  \item Are they isomorphic to each other?
  \item Are they planar?
\end{enumerate}
\begin{center}
  \includegraphics[width=.5\textwidth]{IsomPlanar}
  \end{center}
\end{zad}

\begin{zad}
We are given a graph $G$:
\begin{center}
\includegraphics{ravninski-2}
\end{center}
\begin{enumerate}[label=\rm(\alph*)]
\item For the graph $G$ in the figure, provide an example of an induced subgraph that is not bipartite and has $5$ vertices.
\item Is $G$ planar?
\item Determine the chromatic number of the graph $G$.
\end{enumerate}
\end{zad}

\begin{zad}
We are given a graph $L$:
\begin{center}
\includegraphics{rav-v2}~~$L$
\end{center}
\begin{enumerate}[label=\rm(\alph*)]
\item Is the graph $L$ planar? Justify your answer.
\item Find the chromatic number of the graph $L$.
\item Is $\chi(L,2) > 0$? Is $\chi(L,3) > 0$? Is $\chi(L,4) > 0$? Justify your answers.
\end{enumerate}
\end{zad}

\begin{zad}
Consider the following graph $G$:
\begin{center}
\begin{tikzpicture}[scale=.4]
\draw [line width=1pt] (2.34,0)-- (5.34,1.732050807568878);
\node at (5.84,-2.232050807568878) {$f$};
\node at (5.84,2.232050807568878) {$e$};
\node at (-0.62,-0.6) {$c$};
\node at (1.84,-0.6) {$d$};
\node at (-4.62,2.2320508075688774) {$a$};
\node at (-4.62,-2.2320508075688774) {$b$};
\draw [line width=1pt] (5.34,-1.732050807568878)-- (2.34,0);
\draw [line width=1pt] (-4.12,-1.7320508075688776)-- (-4.12,1.7320508075688774);
\draw [line width=1pt] (-1.12,0)-- (-4.12,1.7320508075688774);
\draw [line width=1pt] (-4.12,-1.7320508075688776)-- (-1.12,0);
\draw [line width=1pt] (-1.12,0)-- (2.34,0);
\fill (-1.12,0) circle [radius=0.27];
\fill (2.34,0) circle [radius=0.27];
\fill (2.34,0) (5.34,1.732050807568878) circle [radius=0.27];
\fill (2.34,0) (5.34,-1.732050807568878) circle [radius=0.27];
\fill (2.34,0) (-4.12,1.7320508075688774) circle [radius=0.27];
\fill (2.34,0) (-4.12,-1.7320508075688776) circle [radius=0.27];
\node at (0.61,-4) {$G$};
\end{tikzpicture}
\end{center}
\begin{enumerate}[label=\rm(\alph*)]
\item Find all isomorphisms of the graph $G$ onto itself (i.e., automorphisms of the graph $G$).
\item Determine the chromatic number of the graph $G$ and calculate its chromatic polynomial $\chi(G,t)$.
\end{enumerate}
\end{zad}

\begin{zad}
Consider the following graph:
\begin{center}
\centering\includegraphics[width=0.45\textwidth]{KspsC}
\end{center}
\begin{enumerate}[label=\rm(\alph*)]
\item Is it possible to draw this graph without lifting the pen from the paper, never retracing an edge, and starting and ending at the same vertex?
\item Find the chromatic number of the given graph.
\item Show that the graph is not planar.
\end{enumerate}
\end{zad}

\begin{zad}
\begin{enumerate}[label=\rm(\alph*)]
\item Find two $4$-vertex graphs with different chromatic polynomials.
\item Find two non-isomorphic $4$-vertex graphs with the same chromatic polynomial.
\item Prove that the number of ways to properly color a cycle $C_n$ with $n \geq 3$ vertices using $t$ colors is:
\begin{itemize}
\item $(t-1)[(t-1)^{n - 1} + 1]$ if $n$ is even.
\item $(t-1)[(t-1)^{n - 1} - 1]$ if $n$ is odd.
\end{itemize}
\end{enumerate}
\end{zad}












\section{Different math problems}




\begin{zad}
Consider the following graph $G$:
\begin{center}
\includegraphics{graphG2-dn}
$G$
\end{center}
\begin{enumerate}[label=\rm(\alph*)]
\item Is $G$ an Eulerian graph?
\item Does $G$ contain an Eulerian trail?
\item Is $G$ Hamiltonian?
\item Determine the chromatic number of the graph $G$.
\end{enumerate}
\end{zad}

\begin{zad}
\label{Kg2i}
A \textbf{wheel graph} $W_n$ for $n \geq 4$ is a graph with $n$ vertices consisting of a cycle $C_{n-1}$ (called the \textit{outer cycle}) and an additional central vertex that is adjacent to every vertex in the cycle.
\begin{enumerate}[label=\rm(\alph*)]
\item Draw the wheel graphs $W_4, W_5, W_6,$ and $W_7$. Start with the outer cycle, then add the central vertex, and connect it to each vertex in the cycle.
\item For which $n \geq 4$ is $W_n$ an Eulerian graph? For which $n \geq 4$ does $W_n$ have an Eulerian trail?
\item For which $n \geq 4$ is $W_n$ Hamiltonian?
\item Show that there exists an orientation of the edges of $W_n$ such that the absolute difference between the in-degree and out-degree of each vertex is at most one.
\end{enumerate}
\end{zad}

\begin{zad}
Let $W_n$ be the wheel graph from the previous problem (see Problem \ref{Kg2i}).
\begin{enumerate}[label=\rm(\alph*)]
\item Calculate the clique number $\omega(W_n)$ of the graph $W_n$ (the size of the largest complete subgraph in $W_n$).
\item Find the chromatic number $\chi(W_n)$ of the graph $W_n$.
\item Show that the chromatic polynomial of $W_n$ is given by:
	$$\chi(W_n, t) = t\left((t-2)^{n-1} - (-1)^n (t-2)\right).$$
\end{enumerate}
\end{zad}

\begin{zad}
Consider the graph $G$ below and answer the questions. Justify your answers.

\begin{center}
\begin{tabular}{c}
\begin{tikzpicture}[scale=.35]
\SetVertexMath
\GraphInit[vstyle=Classic]
\tikzset{VertexStyle/.style = {
		shape = circle,
		fill = black,%
		inner sep = 0pt,
		outer sep = 0pt,
		minimum size = 7pt,
		draw}}
\SetGraphUnit{5}
\Vertices{circle}{c,b,a,h,g,f,e,d}
\foreach \v in {c,e,f,g}{\Edge(a)(\v)}
\foreach \v in {d,e,f,g}{\Edge(b)(\v)}
\foreach \v in {f,g,h}  {\Edge(c)(\v)}
\foreach \v in {f,g,h}  {\Edge(d)(\v)}
\foreach \v in {g,h}    {\Edge(e)(\v)}
\foreach \v in {h}      {\Edge(f)(\v)}
\end{tikzpicture}
\\
\large{$G$}
\end{tabular}
\end{center}
\begin{enumerate}[label=\rm(\alph*)]
\item Is $G$ Hamiltonian?
\item Is $G$ connected?
\item Is $G$ an Eulerian graph? Does it contain an Eulerian trail?
\item Is $G$ planar?
\item Determine $\chi(G)$.
\end{enumerate}
\end{zad}

\begin{zad}
Let $G$ be the following weighted graph:
\begin{center}
\includegraphics[scale=1]{rail}
\end{center}
\begin{enumerate}[label=\rm(\roman*)]
\item Use Kruskal's greedy algorithm to find a minimum spanning tree of $G$ and specify its total weight. Outline the steps of the algorithm.
\item Determine whether the tree found in the previous part is unique, i.e., whether another spanning tree with the same weight can be obtained using Kruskal's method.
\item Is $G$ an Eulerian graph? If yes, write the corresponding trail; if no, provide a justification.
\item Is $G$ Hamiltonian? Does $G$ have a Hamiltonian path? If yes, specify the cycle/path; if no, justify your answer.
\item Calculate $\chi(G)$.
\end{enumerate}
\end{zad}






\bigskip
\begin{center}
All above math problems  are taken from the following website: \url{https://osebje.famnit.upr.si/~penjic/teaching.html}.

{\sc The reader can find all solutions to the given problems on the same page.}
\end{center}








\end{document}
