Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  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.


Could anyone please provide any additional hints to these problems? Thank you in advance

share|improve this question
    
1. You might find hints in the following question: math.stackexchange.com/questions/728795/… –  DracoMalfoy Mar 27 at 17:06

1 Answer 1

up vote 4 down vote accepted
  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)$.

share|improve this answer
1  
1. Yes. 2. The formula is given, so there's no problem here. Often how you come up with a statement is different from the way how you prove it. –  Samuel May 25 '13 at 11:48
1  
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
1  
$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
1  
That is correct. –  Samuel May 25 '13 at 12:32
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.