Results 1 to 2 of 2

Math Help - cycles of nodes in random graph theory

  1. #1
    Newbie
    Joined
    Nov 2012
    From
    iaoalst
    Posts
    6

    cycles of nodes in random graph theory

    Could someone help me out with some basic graph theory?

    (a cycle consisting of four nodes connected by four links to a cycle. A cycle has no start or end point nor a direction.)

    I want to show that in the random graph G(n, p) (where n is the number of nodes nodes and p is the probability of the existence of a link between two nodes), that there are ((n (n-1)(n-2)(n-3))/8 possible cycles of length 4 (consisting of only 4 nodes that is)

    I know from examples that there are (1/6)n(n -2)(n -1) possible triangles from n number of nodes. But when I use the same method for the number of connected nodes with length 4 I get:

    (from n choose 4) = (1/24)n(n -3)(n -2)(n -1)

    Which is not correct and I would need to multiply it with 3 to make it right and I don't get why. could someone help me out?

    I'm so sorry if anything is unclear. English is not my frist language.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,610
    Thanks
    1576
    Awards
    1

    Re: cycles of nodes in random graph theory

    Quote Originally Posted by xaosman View Post
    I want to show that in the random graph G(n, p) (where n is the number of nodes nodes and p is the probability of the existence of a link between two nodes), that there are ((n (n-1)(n-2)(n-3))/8 possible cycles of length 4 (consisting of only 4 nodes that is)
    (from n choose 4) = (1/24)n(n -3)(n -2)(n -1)
    Which is not correct and I would need to multiply it with 3 to make it right and I don't get why. could someone help me out?
    Where did you get this "that there are ((n (n-1)(n-2)(n-3))/8 possible cycles of length 4"

    Clearly it should be \binom{n}{4}=\frac{n(n-1)(n-2)(n-3)}{4!}.

    There must be other restrictions you have not included.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  2. draw a graph with nodes
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 4th 2011, 07:40 PM
  3. Replies: 3
    Last Post: October 24th 2010, 03:24 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum