# Several graph theory proofs

1. Let $G=(V,E)$ be a graph with $|V|=n$. Prove that $G$ is connected if $d(v)\geq \frac{n-1}{2}$ for all $v\in V$.

2. Let $G=(V,E)$ be a graph with $|V|=n$ and $|E|=m$. Prove that $\min\limits_{u\in V} d(u) \leq 2\dfrac{m}{n}\leq \max\limits_{v\in V}d(v)$.

My attempts:

1. $|E|\leq n(n-1)$ since every node can have at most $n-1$ edges, and there are $n$ nodes in total. Hence making use of the formula $\sum\limits_{v\in V}d(v)=2|E|$, we obtain $\sum\limits_{v\in V}d(v)\leq 2n(n-1)$. I don't know how to proceed from here.

2. All I can come up with is that $\max\limits_{v\in V}d(v)=n-1$. I don't think this helps me though.

-
1. You might find hints in the following question: math.stackexchange.com/questions/728795/… – DracoMalfoy Mar 27 '14 at 17:06

1. Actually, $|E|\leq n(n-1)/2$; you are counting each edge twice, when it goes from a node, and when it goes to a node. Take two arbitrary nodes $x,y$. If they are not connected, then there is not an edge between them, so all the outgoing edges from $x$ must go to at least $(n-1)/2$ nodes other than $x$. Similarly all the outgoing edges from $y$ must go to at least $(n-1)/2$ nodes, all distinct from both $x$ and the neighbors of $x$, or otherwise $G$ would be connected. But wait, how many nodes have we used already...?
2. Use the formula $\sum_v d(v)=2m$. Suppose $\min_v d(v)\leq 2m/n$ were false, then $d(v)>2m/n$ for all $v$. Insert into the formula. Do the same thing for the inequality $2m/n\leq \max_v d(v)$.
Do each case separately. First prove that $\min_v d(v)\leq 2m/n$ can't be true, because you will get a contradiction against the formula $\sum_v d(v)=2m$. You will not use anything about the maximum to do this. The proof for the other case will be similar, but I recommend you to sit down and do it with as much detail as in the first case. – Samuel May 25 '13 at 12:06
$d(v)>2m/n\implies \sum_v d(v)>\sum_v 2m/n=n2m/n=2m$, which contradicts $\sum_vd(v)=2m$. – Samuel May 25 '13 at 12:18
If the degree of a node is $d(v)$, then it is adjacent to exactly $d(v)$ nodes, and $d(v)\geq (n-1)/2$. – Samuel May 25 '13 at 13:40