A First Theorem
Your First Theorem in Graph Theory
Theorem:
Let be a -graph with
and
. Then
Proof:
Imagine that every vertex of a graph sends a "message" along every edge incident to it.
Messages sent from opposite ends of the same edge collide in the middle of all edges.
Problem
5:
How many messages are sent?
Answer
Problem
6:
How many collisions will occur?
Answer
Conclusion
Since the number of collisions is half the number of messages, the theorem is proven.
|
|