Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- \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_{0 \leq i < n} \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 6 \\
- First lets state for every graph $G$, $\sum_{v \in G} D(v) \% 2 = 0$, that is the sum of degrees for every graph is even. \\
- So lets assume that $u,v$ do not have a path, that means they are part of some seperate connected components. \\
- Lets call them $W,G$, then the their sum of degrees would be $(|W|-1) \cdot even + odd$ and $(|G|-1) \cdot even + odd$, $c \cdot even = even$ for some constant c and $even+odd = odd$, so that means their sums of degrees are both odd which is not possible, thus by contradiction must $u,v$ be in the same connected component and therefor there must exist a $u,v$-path. \\
- 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_{1\leq j \leq 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}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement