Skip to content

Tag Archives: proof

A Calculational Proof of the Handshaking Lemma

Tuesday, April 7, 2009

In graph theory, the degree of a vertex A, d.A, is the number of edges incident with the vertex A, counting loops twice. So, considering graph 0 below, we have d.A=3, d.B=3, d.C=1, d.D=3, and d.E=2.
A well-known property is that every undirected graph contains an even number of vertices with odd degree. The result first [...]

Filed in Algorithms, Computing Science, Education, Mathematics, Methodology | Also tagged , , , , , , , , | Comments (2)

Multiples in the Fibonacci series

Friday, May 9, 2008

I found the following problem on K. Rustan M. Leino’s puzzles page:

[Carroll Morgan told me this puzzle.]
Prove that for any positive K, every Kth number in the Fibonacci sequence is a multiple of the Kth number in the Fibonacci sequence.
More formally, for any natural number n, let F(n) denote Fibonacci number n. That is, F(0) [...]

Filed in Mathematics, Methodology | Also tagged , , , | Comments (6)