Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Girth of a Graph.

  1. Aug 29, 2009 #1


    User Avatar
    Gold Member

    The girth of a graph is the length of the smallest polygon in the graph. Let G be graph with girth 5 for which all vertices have degree >=d. Show that G has at least d^2+1 vertices.
    Can equality hold?

    I am not sure, but how do I use the fact that the girth of G is 5, the only thing it tells me is that there are at least 5 vertices?

    Should I prove this statement by induction on d?

    What I did think of is using the fact the summing the degrees over all the vertices gives us that (1) 2|E|>=d*N, where N is the number of vertices and E is the set of edges of G.
    Now if I show that |E|>=(d^3+d)/2, and this is not a strict bound, then I prove it, but it seems even difficult than a proof by induction which I am not sure how to do also.

    Any hints?
  2. jcsd
  3. Aug 29, 2009 #2
    Well, if the graph has girth 5, that means that if nodes A and B are adjacent, then B cannot be adjacent to any other node that A is adjacent to. Additionally, if B and C are both adjacent to A, then the intersection of the nodes adjacent to B and C is just A.

    If a given node A connects to d other nodes, then there are (at least) d*(d-1) nodes other than A that are adjacent to nodes adjacent to A. And A can't connect to any of those. So for each node A in the graph, there are at least d*(d-1) nodes that are not adjacent to A. And there are at least d nodes that are adjacent to A. And then there's A itself. Adding all these nodes together, you get d*(d-1) + d + 1 = d^2 + 1.
  4. Aug 29, 2009 #3


    User Avatar
    Gold Member

    Thanks, I got to this same reasoning after someone else gave me a hint on how to solve this from another forum.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook