Math Is Fun Forum

GemmaJ1988

Member

Registered: 2008-10-08

Posts: 39

combinatorics

hey
i've found a question in the book "a course in combinatorics" which i need help solving
problem:
"The girth of a graph is the length of the smallest polgon in the graph. Let G be a graph with girth 5 for which all vertices have degree>=d. show that G has atleast d^2+1 vetices."

can anyone please help me to understand this question

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: combinatorics

The word "polgon" was supposed to be "cycle".

To solve this problem, use a breadth first search and count vertices.  Be very careful not to travel back along the same edge from whence you came.

I was quite confused by this solution because it seems like you can easily do a lot better approximation of the number of nodes in the graph.  However, this isn't the case.  Make sure you understand why.

---

"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..."