\documentclass[12pt,letterpaper]{article}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amscd}
\usepackage{enumerate}
\usepackage{fancyhdr}
\usepackage{mathrsfs}
\usepackage{bbm}
\usepackage{framed}
\usepackage{mdframed}
\usepackage{cancel}
\usepackage{mathtools}
\usepackage{verbatim}
\usepackage[letterpaper,voffset=-.5in,bmargin=3cm,footskip=1cm]{geometry}
\setlength{\parindent}{0.0in}
\setlength{\parskip}{0.1in}
\allowdisplaybreaks
\headheight 15pt
\headsep 10pt
\newcommand\N{\mathbb N}
\newcommand\Z{\mathbb Z}
\newcommand\R{\mathbb R}
\newcommand\Q{\mathbb Q}
\newcommand\lcm{\operatorname{lcm}}
\newcommand\setbuilder[2]{\ensuremath{\left\{#1\;\middle|\;#2\right\}}}
\newcommand\E{\operatorname{E}}
\newcommand\V{\operatorname{V}}
\newcommand\Pow{\ensuremath{\operatorname{\mathcal{P}}}}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
\newcommand\hint[1]{\textbf{Hint}: #1}
\newcommand\note[1]{\textbf{Note}: #1}
\newcounter{enum22i}
\newenvironment{22enumerate}{\begin{enumerate}[a.]\itemsep0em\setcounter{enumi}{\value{enum22i}}}{\setcounter{enum22i}{\value{enumi}}\end{enumerate}}
\newenvironment{22itemize}{\begin{itemize}\itemsep0em}{\end{itemize}}
\fancypagestyle{firstpagestyle} {
\renewcommand{\headrulewidth}{0pt}
\lhead{\textbf{CSCI 0220}}
\chead{\textbf{Discrete Structures and Probability}}
\rhead{M. Littman}
}
\fancypagestyle{fancyplain} {
\renewcommand{\headrulewidth}{0pt}
\lhead{\textbf{CSCI 0220}}
\chead{Homework 9}
\rhead{\textit{Wednesday, April 29}}
}
\pagestyle{fancyplain}
\usepackage{tikz}
\begin{document}
\thispagestyle{firstpagestyle}
\begin{center}
{\huge \textbf{Homework 9}}
{\large \textit{Due: Wednesday, April 29}}
\end{center}
All homeworks are due at 12:55 PM on Gradescope.
Please do not include any identifying information about yourself in the handin, including your Banner ID.
Be sure to fully explain your reasoning and show all work for full credit.
\subsection*{Problem 1}
{
\nopagebreak
{\setcounter{enum22i}{0}
Let $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ be graphs. We say that
$G_1$ is \emph{isomorphic} to $G_2$ if there is a bijection
\begin{align*}
f : G(V_1) \to G(V_2)
\end{align*}
such that $\{u,v\} \in E(G_{1})$ if and only if $\{f(u), f(v)\} \in E(G_{2})$.
We call $f$ an \emph{isomorphism} from $G_1$ to $G_2$, and it can be
thought of as a ``relabeling'' of $G_1$.
\begin{center}
\begin{tikzpicture}
\node[shape=circle, draw=black] (A) at (1,3) {A};
\node[shape=circle, draw=black] (B) at (0,1) {B};
\node[shape=circle, draw=black] (C) at (2,1) {C};
\node[shape=circle, draw=black] (D) at (3,3) {D};
\node ($G_1$) at (1.5, -0.25) {$G_1$};
\draw (A) -- (B);
\draw (A) -- (C);
\draw (A) -- (D);
\draw (C) -- (D);
\node (Z) at (6,2.5) {isomorphism};
\draw [->] (5,2) -- (7,2);
\node[shape=circle, draw=black] (E) at (9,3) {1};
\node[shape=circle, draw=black] (F) at (8,1) {2};
\node[shape=circle, draw=black] (G) at (10,1) {3};
\node[shape=circle, draw=black] (H) at (11,3) {4};
\node ($G_2$) at (9.5, -0.25) {$G_2$};
\draw (E) -- (F);
\draw (E) -- (G);
\draw (E) -- (H);
\draw (G) -- (H);
\end{tikzpicture}
\end{center}
Define the relation $R$ on graphs as follows:
\begin{align*}
R = \{(G_1,G_2)\ \mid\ G_1\text{ is isomorphic to }G_2\}
\end{align*}
We will show that $R$ is an equivalence relation by providing appropriate isomorphisms and proving they have the necessary properties.
\begin{22enumerate}
\item Prove that $R$ is reflexive.
\item Prove that $R$ is symmetric.
\item Prove that $R$ is transitive.
\end{22enumerate}
}
}
\subsection*{Problem 2}
{
\nopagebreak
{\setcounter{enum22i}{0}
Let $K_{n}$ denote the complete graph on $n$ vertices.
We define a \emph{random graph} $G$
on $n$ vertices where
$G$ is a subgraph of $K_{n}$ such that $E(G) \subseteq E(K_{n})$ is constructed
as follows:
For each possible edge $e \in E(K_{n})$, we include $e$ in $E(G)$
with probability $p$, and exclude $e$ with probability $1-p$.
\begin{22enumerate}
\item What is the probabilty that a random graph $G$ on $n$
vertices is the complete graph $K_{n}$?
\end{22enumerate}
For any graph $G$, consider a set $T = \{u,v,w\}$ such that
$T \subseteq V(G)$ and $|T| = 3$. We say that $T$ forms a \emph{triangle} in
$G$ if $\{u, v\}$, $\{v, w\}$, and $\{u, w\}$ are all elements of $E(G)$.
\begin{22enumerate}
\item How many distinct triangles are in $K_{n}$?
\item Let $T \subseteq V(K_{n})$ be a triangle in $K_{n}$. What is the
probability that, for a random graph $G$ on the same $n$ vertices ($V(G) = V(K_n)$,
that
$T$ is \emph{also} a triangle in $G$?
\item What is the expected number of triangles in a random
graph on $n$ vertices?
\item If $p=\frac{1}{2}$, for what values of $n$ is the expected number of triangles over 500?
\end{22enumerate}
}
}
\subsection*{Problem 3}
{
\nopagebreak
{\setcounter{enum22i}{0}
\begin{22enumerate}
\item Let $X$ be a discrete, finite random variable and $E[X]=\mu$. Prove
that the following is true:
\[\Pr[X\ge \mu] > 0 \text{ and } \Pr[X\le \mu] > 0\]
(Hence if the expectation of a random variable is $\mu$ then the random
variable must take on a value greater than or equal to $\mu$ and it must
take on a value less than or equal to $\mu$.)
\item Let $G$ be a graph with $n$ vertices and $m$ edges. Using your result
from part a, prove there exists a partition of the vertices into two
disjoint sets $A$ and $B$ such that there are at least $\frac{m}{2}$ edges
with one vertex in $A$ and one vertex in $B$.
\hint Your proof will not be constructive.
\end{22enumerate}
}
}
\subsection*{Problem 4}
{
\nopagebreak
{\setcounter{enum22i}{0}
Show that, in any graph $G$, if there is a vertex $v$
of odd degree, then there is a path from $v$ to some other vertex of
odd degree.
}
}
\subsection*{Problem 5}
{
\nopagebreak
{\setcounter{enum22i}{0}
A full binary tree is a tree in which every node has zero or two children. For
example, there are five possible full binary trees with four leaves (childless nodes):
\begin{center}
\begin{tikzpicture}
\node (1) at (1.33,4) [label] {1};
\node[shape=circle, draw=black, scale=0.75] (A) at (3,3) {};
\node[shape=circle, draw=black, scale=0.75] (B) at (2,2) {};
\node[shape=circle, draw=black, scale=0.75] (C) at (4,2) {};
\node[shape=circle, draw=black, scale=0.75] (D) at (1.5,1) {};
\node[shape=circle, draw=black, scale=0.75] (E) at (2.5,1) {};
\node[shape=circle, draw=black, scale=0.75] (F) at (3.5,1) {};
\node[shape=circle, draw=black, scale=0.75] (G) at (4.5,1) {};
\draw (A) -- (B);
\draw (A) -- (C);
\draw (B) -- (D);
\draw (B) -- (E);
\draw (C) -- (F);
\draw (C) -- (G);
\end{tikzpicture}
\begin{tikzpicture}
\node (2) at (0,3) [label] {2};
\node[shape=circle, draw=black, scale=0.75] (A) at (2,3) {};
\node[shape=circle, draw=black, scale=0.75] (B) at (1.5,2) {};
\node[shape=circle, draw=black, scale=0.75] (C) at (2.5,2) {};
\node[shape=circle, draw=black, scale=0.75] (D) at (1,1) {};
\node[shape=circle, draw=black, scale=0.75] (E) at (2,1) {};
\node[shape=circle, draw=black, scale=0.75] (F) at (0.5,0) {};
\node[shape=circle, draw=black, scale=0.75] (G) at (1.5,0) {};
\draw (A) -- (B);
\draw (A) -- (C);
\draw (B) -- (D);
\draw (B) -- (E);
\draw (D) -- (F);
\draw (D) -- (G);
\end{tikzpicture}
\begin{tikzpicture}
\node (3) at (0.5,3) [label] {3};
\node[shape=circle, draw=black, scale=0.75] (A) at (2,3) {};
\node[shape=circle, draw=black, scale=0.75] (B) at (1.5,2) {};
\node[shape=circle, draw=black, scale=0.75] (C) at (2.5,2) {};
\node[shape=circle, draw=black, scale=0.75] (D) at (1,1) {};
\node[shape=circle, draw=black, scale=0.75] (E) at (2,1) {};
\node[shape=circle, draw=black, scale=0.75] (F) at (1.5,0) {};
\node[shape=circle, draw=black, scale=0.75] (G) at (2.5,0) {};
\draw (A) -- (B);
\draw (A) -- (C);
\draw (B) -- (D);
\draw (B) -- (E);
\draw (E) -- (F);
\draw (E) -- (G);
\end{tikzpicture}
\begin{tikzpicture}
\node (4) at (1,3) [label] {4};
\node[shape=circle, draw=black, scale=0.75] (A) at (2,3) {};
\node[shape=circle, draw=black, scale=0.75] (B) at (1.5,2) {};
\node[shape=circle, draw=black, scale=0.75] (C) at (2.5,2) {};
\node[shape=circle, draw=black, scale=0.75] (D) at (2,1) {};
\node[shape=circle, draw=black, scale=0.75] (E) at (3,1) {};
\node[shape=circle, draw=black, scale=0.75] (F) at (1.5,0) {};
\node[shape=circle, draw=black, scale=0.75] (G) at (2.5,0) {};
\draw (A) -- (B);
\draw (A) -- (C);
\draw (C) -- (D);
\draw (C) -- (E);
\draw (D) -- (F);
\draw (D) -- (G);
\end{tikzpicture}
\begin{tikzpicture}
\node (5) at (1,3) [label] {5};
\node[shape=circle, draw=black, scale=0.75] (A) at (2,3) {};
\node[shape=circle, draw=black, scale=0.75] (B) at (1.5,2) {};
\node[shape=circle, draw=black, scale=0.75] (C) at (2.5,2) {};
\node[shape=circle, draw=black, scale=0.75] (D) at (2,1) {};
\node[shape=circle, draw=black, scale=0.75] (E) at (3,1) {};
\node[shape=circle, draw=black, scale=0.75] (F) at (2.5,0) {};
\node[shape=circle, draw=black, scale=0.75] (G) at (3.5,0) {};
\draw (A) -- (B);
\draw (A) -- (C);
\draw (C) -- (D);
\draw (C) -- (E);
\draw (E) -- (F);
\draw (E) -- (G);
\end{tikzpicture}
\end{center}
Prove that a full binary tree with $n \geq 2$ leaf nodes must have exactly $n-1$ non-leaf nodes.
}
}
\end{document}