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

1. ## 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 $\displaystyle T_{m,n}$. Show that:

$\displaystyle \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 $\displaystyle n/m$"

I hope someone has a solution!

James Elmore

2. Here is the closest I get. It comes up with the formula, but not as directly as I had hoped.

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

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

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

Remove $\displaystyle (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 $\displaystyle k(n - k)$.

So we get $\displaystyle \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.

3. 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 $\displaystyle T_{m,n}$. Show that:

$\displaystyle \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 $\displaystyle 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 $\displaystyle k$, I'll just write $\displaystyle \frac{n}{m}$)

\displaystyle \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?

4. 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.

5. 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?

6. 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!