Results 1 to 2 of 2

Thread: Triangles in a graph

  1. #1
    Newbie
    Joined
    Nov 2015
    From
    Niš
    Posts
    16

    Question Triangles in a graph

    Hi guys,

    How to prove that a graph with n nodes and m edges has at least m*(4*m - n2)/(3*n) triangles?
    Thanks in advance! ^-^
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,686
    Thanks
    1495

    Re: Triangles in a graph

    This is just a guess, but find the maximum number of edges that can fit with zero triangles. (Try to make as many squares as possible). At first, just look for patterns. Then try to relate the number of vertices with the number of edges.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: Mar 4th 2013, 10:02 AM
  2. Replies: 3
    Last Post: Mar 19th 2011, 04:42 AM
  3. Replies: 0
    Last Post: Sep 25th 2010, 05:59 AM
  4. Graph Theory - Complete graphs and triangles
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 3rd 2009, 08:39 AM
  5. Replies: 1
    Last Post: Feb 15th 2009, 05:35 AM

Search Tags


/mathhelpforum @mathhelpforum