Project Links Logo Artwork
Graph Theory: Industrial Drilling
Home > Graph Theory: Industrial Drilling > Foundations > A First Theorem
Crib Sheet
Library
Help
Map
Problem List
Module Home
Links Home


conceptsdiscoverapplycollaboratepractice
 
 
go backgo forward
go backgo forward

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.

 
 
go backgo forward
go backgo forward