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

• January 4th 2011, 03:50 PM
jameselmore91
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!

James Elmore
• January 4th 2011, 05:43 PM
snowtea
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.
• January 4th 2011, 05:46 PM
Drexel28
Quote:

Originally Posted by jameselmore91
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!

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?
• January 4th 2011, 05:50 PM
dwsmith
Quote:

Originally Posted by Drexel28

P.S. What the hell does this have to do with group theory?

Not sure but it is in the correct forum.
• January 4th 2011, 05:58 PM
jameselmore91
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?
• January 4th 2011, 06:00 PM
Drexel28
Quote:

Originally Posted by jameselmore91
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!