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

**jameselmore91** · January 4th 2011, 03:50 PM

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

**snowtea** · January 4th 2011, 05:43 PM

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.

**Drexel28** · January 4th 2011, 05:46 PM

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!

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?

**dwsmith** · January 4th 2011, 05:50 PM

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.

**jameselmore91** · January 4th 2011, 05:58 PM

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?

**Drexel28** · January 4th 2011, 06:00 PM

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!

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

LinkBack

Thread Tools

Display

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

Similar Math Help Forum Discussions

Vertices and Edges

Components, edges, and vertices

Edges and vertices of a solid

Graph Theory: A has 15 edges, Ā has 13 edges, how many vertices does A have?

Eulerian graph with even vertices and odd edges

Search Tags