Welcome to our community

Be a part of something great, join today!

[SOLVED] Number of edges of the graph

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,028
Hey!! :eek:

Let $G$ be a graph of which the vertices are the permutations of $\{1,2,3,4,5,6,7,8,9,9,9\}$ with the property that two vertices $(\epsilon_1, \epsilon_2, \ldots, \epsilon_{11})$, $(\epsilon_1', \epsilon_2', \ldots, \epsilon_{11}')$ are connected with an edge if and only if the one is resulted from the other by exchanging the positions of two different integers.

How can we calculate the number of edges of the graph $G$ ?


We have $\frac{11!}{3!}$ (because we have 11 numbers but the number 9 is appeared three times) permutations, and so we have $\frac{11!}{3!}$ vertices, right? I haven't really understood how we can get the number of edges knowing that. Could you give me a hint? (Wondering)
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,681
Hey!! :eek:

Let $G$ be a graph of which the vertices are the permutations of $\{1,2,3,4,5,6,7,8,9,9,9\}$ with the property that two vertices $(\epsilon_1, \epsilon_2, \ldots, \epsilon_{11})$, $(\epsilon_1', \epsilon_2', \ldots, \epsilon_{11}')$ are connected with an edge if and only if the one is resulted from the other by exchanging the positions of two different integers.

How can we calculate the number of edges of the graph $G$ ?


We have $\frac{11!}{3!}$ (because we have 11 numbers but the number 9 is appeared three times) permutations, and so we have $\frac{11!}{3!}$ vertices, right? I haven't really understood how we can get the number of edges knowing that. Could you give me a hint? (Wondering)
I would start by fixing a vertex $(\epsilon_1, \epsilon_2, \ldots, \epsilon_{11})$ and counting the number of edges connected to that vertex. There will be one such edge for each transposition of the form $(\epsilon_i, \epsilon_j)$, where $i\ne j$ and $\epsilon_i$, $\epsilon_j$ are not both equal to $9$.

If there are $N$ such transpositions then $N$ will be the same for each vertex, so the total number of endpoints of edges will be $\dfrac{11!N}{3!}$. Since each edge has two endpoints, the total number of edges is then $\dfrac{11!N}{2\cdot3!}$.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,028
I would start by fixing a vertex $(\epsilon_1, \epsilon_2, \ldots, \epsilon_{11})$ and counting the number of edges connected to that vertex. There will be one such edge for each transposition of the form $(\epsilon_i, \epsilon_j)$, where $i\ne j$ and $\epsilon_i$, $\epsilon_j$ are not both equal to $9$.

If there are $N$ such transpositions then $N$ will be the same for each vertex, so the total number of endpoints of edges will be $\dfrac{11!N}{3!}$. Since each edge has two endpoints, the total number of edges is then $\dfrac{11!N}{2\cdot3!}$.
Ah ok! And is N the number of transpositions of 9 numbers, i.e $\binom{9}{2}$ ? (Wondering)
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,681
Ah ok! And is N the number of transpositions of 9 numbers, i.e $\binom{9}{2}$ ? (Wondering)
There are $11$ coordinates, and you can transpose any two of them provided that they are not both $9$s. So that gives you ${11\choose2} - {3\choose2}$ possibilities.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,028
There are $11$ coordinates, and you can transpose any two of them provided that they are not both $9$s. So that gives you ${11\choose2} - {3\choose2}$ possibilities.
I understand!! Thank you!! (Smile)