Math Is Fun Forum

Luke112233

Guest

about graphs and Fibonacci

I've found two problems I do not really know how to solve... can you help me please?

the first one is about graph theory, and states that a simple graph has n vertices such that for any two distinct vertices x and y, the degree of x plus the degree of y is greater than or equal to n − 1 (symbolically, deg(x) + deg(y) ≥ n − 1). Does this guarantee that G will be connected? If yes, prove it.

the second is about Fibonacci numbers and recurrence relations, and requires to prove in a combinatorial way that for n ≥ 0, f(0) + f(1) + f(2) + ... + f(n) = f(n+2) − 1, where the f are the Fibonacci numbers, f(0)=1 and f(1)=1

thanks in advance

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: about graphs and Fibonacci

I'm not sure if this method counts as a combinatorial way, but you can prove the fibonacci one with induction fairly simply.

Base case:
n=0.
f(0+2)-1 = f(0)
2-1 = 1, so this is correct.

Induction case:
Assume that the statement is true for n=k.
ie. f(0)+...+f(k) = f(k+2)-1.

Now, f(k+3)-1 = f(k+1)+f(k+2)-1.
By the induction hypothesis, this is f(k+1) + [f(0)+...+f(k)-1] - 1.
So f(k+3)-1 = f(0)+...+f(k+1) - 1.

Therefore, the statement is true for all n.

---

Why did the vector cross the road?
It wanted to be normal.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: about graphs and Fibonacci

For 1, assume that there are at least 2 unconnected parts of the graph, one having k vertices and the other having l.  You should get a contradiction from this.

For 2, induction is not a combinatorial proof.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: about graphs and Fibonacci

Fair enough. I don't see how combinatorics and Fibonacci are at all related though.

---

Why did the vector cross the road?
It wanted to be normal.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: about graphs and Fibonacci

Wikipedia has the combinatorial proof of this result.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Luke112233

Guest

Re: about graphs and Fibonacci

For 1, assume that there are at least 2 unconnected parts of the graph, one having k vertices and the other having l.  You should get a contradiction from this.

Really? but how do you get up to the contradiction? that's what I cannot see...

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: about graphs and Fibonacci

If one "section" of the graph has k vertices, what's the maximum degree at any one of those vertices in that "section".

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."