Results 1 to 6 of 6

Math Help - Deriving the formula for the edges of an m-Partite graph over n vertices.

  1. #1
    Junior Member
    Joined
    Mar 2010
    Posts
    51

    Deriving the formula for the edges of an m-Partite graph over n vertices.

    I'm taking Graph theory next semester and have started doing some preliminary studying, the online book I found has practice problems in it and I'm having a hard time with this particular problem:

    "The complete m-partite graph on n vertices in which each part has n/m vertices is denoted by T_{m,n}. Show that:

    \epsilon(T_{m,n}) = \left(\begin{array}{cc}n-k\\2\end{array}\right) + (m-1)\left(\begin{array}{cc}k+1\\2\end{array}\right) where k is n/m"

    I hope someone has a solution!

    Thank in advance,

    James Elmore
    Last edited by jameselmore91; January 4th 2011 at 07:04 PM. Reason: Mispelled "Graph theory" with "Group theory"
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    Here is the closest I get. It comes up with the formula, but not as directly as I had hoped.

    Consider an T_{n,m}. Take away one part. Create a complete graph with remaining n-k vertices:

    \binom{n-k}{2} edges.

    Now in the n-k vertices we have extra edges in each of the m - 1 parts

    Remove (m-1)\binom{k}{2} edges.

    Add in the last part. Each of its k vertices needs to connect to all n - k other vertices.

    Add k(n - k).

    So we get \epsilon(T_{m,n}) = \binom{n-k}{2} - (m-1)\binom{k}{2} + k(n - k).

    If you simplify this you will get the formula (remember n = mk).

    I would like to know if there is a more direct argument for the formula without the need for algebra.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by jameselmore91 View Post
    I'm taking Group theory next semester and have started doing some preliminary studying, the online book I found has practice problems in it and I'm having a hard time with this particular problem:

    "The complete m-partite graph on n vertices in which each part has n/m vertices is denoted by T_{m,n}. Show that:

    \epsilon(T_{m,n}) = \left(\begin{array}{cc}n-k\\2\end{array}\right) + (m-1)\left(\begin{array}{cc}k+1\\2\end{array}\right) where k is n/m"

    I hope someone has a solution!

    Thank in advance,

    James Elmore
    To me it seems that the binomial coefficient stuff is just a ploy. I feel a simple argument shows that the total number of edges is (forgetting your definition of k, I'll just write \frac{n}{m})


    \displaystyle \begin{aligned}\sum_{k=1}^{m-1}\frac{n}{m}\left(\frac{m-k}{m}n\right) &=\frac{n^2}{m^2}\sum_{k=1}^{m-1}\left(m-k\right)\\ &=\frac{n^2}{m^2}\left(m(m-1)+\frac{m(m-1)}{2}\right)\\ &= {{n-\frac{n}{m}}\choose 2}+(m-1){{\frac{n}{m}+1}\choose 2}\end{aligned}


    P.S. What the hell does this have to do with group theory?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5
    Quote Originally Posted by Drexel28 View Post

    P.S. What the hell does this have to do with group theory?
    Not sure but it is in the correct forum.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Mar 2010
    Posts
    51
    Ohh! Haha, my mistake.. I was trying to find a place to fit "Graph Theory" and when I read group theory on the board header it kinda of stuck I guess. This would be the correct board for Graph Theory though right?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by jameselmore91 View Post
    Ohh! Haha, my mistake.. I was trying to find a place to fit "Graph Theory" and when I read group theory on the board header it kinda of stuck I guess. This would be the correct board for Graph Theory though right?
    Indeed it would be!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Vertices and Edges
    Posted in the Geometry Forum
    Replies: 2
    Last Post: March 23rd 2010, 03:16 PM
  2. Components, edges, and vertices
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 1st 2009, 11:35 AM
  3. Edges and vertices of a solid
    Posted in the Geometry Forum
    Replies: 1
    Last Post: May 6th 2009, 08:02 AM
  4. Replies: 5
    Last Post: June 22nd 2008, 11:20 PM
  5. Eulerian graph with even vertices and odd edges
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 23rd 2007, 04:12 PM

Search Tags


/mathhelpforum @mathhelpforum