\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage[latin1]{inputenc}

\title{Getting started}
\author{Veloci Raptor}
\date{03/14/15}

\begin{document}
\large
Problem 4 \\
No \\
Proof \\
If the graph is simple and has $n$ vertices then the only possible degrees are $0,1,2,\dots,n-1$. \\
Formally $\forall_{i \in [0,n-1]} \exists_{v \in G} (D(v) = i)$ \\
So $\exists_{v \in G} (D(v) = n-1)$ and $\exists_{v \in G} (D(v = 0))$.
The first one is connected to all vertices while the second one is connected to none, this contradicts each other therefor it cannot be true. \\

Problem 5 \\
I do not see how this is true. \\
Counter Example. \\
Given a graph $G = (\{v_1,v_2\},\{\{v_1,v_2\}\})$ with average degree $\overline{d} = 1$, there are only two subgraphs and the average degree of them both are $0$, hence there is no subgraph with average degree at least $\overline{d}/2$. \\

problem 9 \\
A) \\
If $G$ is not connected then we can rewrite $G$ as disjoint connected components $G_1,G_2,\dots,G_n$. \\
Pick some arbritary $i \in [1,n] $, lets say $i = 1$ and some arbritary vertex $v \in G_i$. \\
Then $\forall_{j \in [1,n],j  \neq i} \forall_{u \in G_j} \exists_{e(edge) \in \overline{G}} (e = \{u,v\})$, or in words $v \in \overline{G}$ is atleast connected to all nodes not in $G_i$. \\
But since this holds $\forall_{v \in G_i}$, then $\forall_{u,w \in G_i} \exists_{t \in G, t \notin G_i} (\{t,u\} \in \overline{G} $ and $\{t,w\} \in \overline{G})$ therefor the graph is always connected .  \\
B) \\
For example $P_n$ where $n \geq 4$. \\
\end{document}