<reponame>ylixir/school
\documentclass[letterpaper]{article}

\usepackage[utf8]{inputenc}
\usepackage{fullpage}
\usepackage{nopageno}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{tikz}

\usetikzlibrary{graphs,graphdrawing}
\usegdlibrary{trees}

\allowdisplaybreaks

\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}

\begin{document}
\title{Notes}
\date{January 26, 2015}
\maketitle
\section*{2.2 trees}
\subsection*{task:}
create a graph with two adjacent cut vertices (connected simple)

\tikz\path [graphs/.cd, nodes={shape=circle, draw, text=black,inner sep=1pt,outer sep=0pt}]
  graph [tree layout] { 1 -- {2 -- 3} -- 1--4--5--6--4 }
  [shift=(0:3)]
  graph [tree layout] { 3 -- 1 --2 --3 --4 -- 6 --7 --4--5--3 };

notice that removing a cut vertex on the second graph leaves a cut vertex, but not on the first graph.

if two cut vertices in a graph $G$ are adjacent and the edge between them is the only trail between them, then that edge is a {\bfseries cut edge}

that is to say, every path from cut vertex one to cut vertex 2 contains the edge between them.

a {\bfseries bridge} is a cut edge.

an edge $e$ in $G$ is a bridge if $k(G)<k(G-e)$.

\subsection*{example}
\begin{enumerate}
\item
\tikz\path [graphs/.cd, nodes={shape=circle, draw, text=black,inner sep=1pt,outer sep=0pt}]
  graph [tree layout] { 1 -- 2 }
  [shift=(0:1)];
\item
\tikz\path [graphs/.cd, nodes={shape=circle, draw, text=black,inner sep=1pt,outer sep=0pt}]
  graph [tree layout] { 1 -- {2 -- 3} -- 4 -- 1}
  [shift=(0:1)];
\item
\tikz\path [graphs/.cd, nodes={shape=circle, draw, text=black,inner sep=1pt,outer sep=0pt}]
  graph [tree layout] { 3--1--2--3--4--5--3 }
  [shift=(0:1)];
\item
\tikz\path [graphs/.cd, nodes={shape=circle, draw, text=black,inner sep=1pt,outer sep=0pt}]
  graph [tree layout] { 3--1--2--3--4--5--6--4 }
  [shift=(0:1)];
\end{enumerate}

1 and 4 contain cut edges.

\subsection*{task}
in row $i$ create a graph with a cut vertex $v$ such that $k(G-v)=i+1$ 

\tikz\path [graphs/.cd, nodes={shape=circle, draw, text=black,inner sep=1pt,outer sep=0pt}]
  graph [tree layout] { 1 -- {2 -- 3} -- 1--4--5--1 }
  [shift=(0:5)]
  graph [tree layout] { 1 -- 2--3--1--4--5--1--6--7--1 };


notice radial symmetry

\subsection*{question}
if $e$ is a bridgeof $G$ what values of $n$ can satisfy $k(G-e)=n+1$
\begin{enumerate}
\item
even n
\item
odd n
\item
any n
\item
1
\end{enumerate}
last option is correct (G is connected)

obviously this is different from removing a vertex.

{\bfseries tree} is a connected graph, all of whose edges are bridges.

{\scshape Note:} if ``connected'' is removed, but every edge is still a bridge, then you  have a forest.

{\scshape Note:} if a graph is not simple, then you necessarily have an edge that isn't a bridge, and so trees are simple graphs
\subsection*{theorem}
if $T$ is a tree and the order of $T$ is $n$ then the size of $T$ is $n-1$
\subsubsection*{proof}
{\scshape case 1:} $T=$\tikz\path [graphs/.cd, nodes={shape=circle, draw, text=black,inner sep=1pt,outer sep=0pt}]
  graph {1 -- 2}
  [shift=(0:1)];

$|T|=2,|E(T)|=1=2-1$

now assume it is true for $|T|=k$

Let $T$ be a tree of order $k+1$. since every  edge is a bridge, remove any edge $e$ to disconnect the graph

Now we have trees $T_1,T_2$ such that $T_1\cup T_2\cup \{e\}=T$. if $|T_1|=a$ then $|T_2|=k+1-a$

by the inductive hypothesis $|E(T_1)|=a-1$ and $|E(T_2)|=k+1-a-1=k-a$ therefore $|E(T)|=|E(T_1)|+|E(T_2)|+1=a-1+k-a+1=k$

\subsection*{theorem}
the converse is also true.

a graph $G$ of order $n$ is a tree iff the size is $n-1$

a graph $G$ is a tree iff $G$ has no cycles

\section*{homework}
2.2 numbers 1,2,3,10,14,17
\end{document}

