retagged by
19,682 views
63 votes
63 votes
Let $G$ be a graph with $100!$ vertices, with each vertex labelled by a distinct permutation of the numbers $1, 2,\ldots, 100.$ There is an edge between vertices $u$ and $v$ if and only if the label of $u$ can be obtained by swapping two adjacent numbers in the label of $v$. Let $y$ denote the degree of a vertex in $G$, and $z$ denote the number of connected components in $G$. Then, $y+10z=$ ______.
retagged by

5 Answers

Best answer
193 votes
193 votes

Answer: 109


Explanation:

We have to find $2$ things here, the degree of every vertex(which will be same for all vertices) and number of connected components.

Instead of $100$, let's solve this by taking lesser value, say $4$.

With $4!$ vertices, each vertex is a permutation of $\left \{ 1,2,3,4 \right \}$. So, we have vertices like $\left \{ 1,2,3,4 \right \}$, $\left \{ 1,3,2,4 \right \}$, $\left \{ 4,1,3,2 \right \},\ldots $ etc.

Here $\left \{ 1,2,3,4 \right \}$ will be connected with

$\left \{ 2,1,3,4 \right \}$

$\left \{ 1,3,2,4 \right \}$

$\left \{ 1,2,4,3 \right \}$

To get this list, just take $2$ adjacent numbers and swap them. eg. $\left \{ 1,2,3,4 \right \}$ swap $1$ and $2$ to get $\left \{ 2,1,3,4 \right \}$. 

The given $3$ are the only permutations we can get by swapping only $2$ adjacent numbers from $\left \{ 1,2,3,4 \right \}$. So, the degree of vertex $\left \{ 1,2,3,4 \right \}$ will be $3$. Similarly for any vertex it's degree will be $3$.

Here we got $``3"$ because we can chose any $3$ pairs of adjacent numbers. So, with $n,$ we have $n-1$ adjacent pairs to swap. So, degree will be $n-1.$

In our question, degree will be $100 - 1 = 99$ 

Now let's see how many connected components we have. 

It will be $1$. Why?

If one can reach from one vertex to any other vertex, then that means that the graph is connected.

Now if we start with a vertex say $\left \{ 1,2,3,4 \right \}$ we can reach to other vertex, say $\left \{ 4,3,2,1 \right \}$ by the following path:

$\left \{ 1234 \right \} \rightarrow \left \{ 1243 \right \} \rightarrow \left \{ 1423 \right \} \rightarrow \left \{ 4123 \right \} \rightarrow \left \{ 4132 \right \} \rightarrow \left \{ 4312 \right \} \rightarrow \left \{ 4321 \right \}$

Just take two adjacent numbers and swap them. With this operation you can create any permutation, from any given initial permutation.

This way you can show that from any given vertex we can reach any other vertex. This shows that the graph is connected and the number of connected components is $1.$

$y = 99$ and $z = 1$

$\therefore y + 10z = 99 + 10 \ast 1 = 109.$

edited by
17 votes
17 votes
$\mathbf{\underline{\color{blue}{An\;Easier \;approach:\Rightarrow}}}$

$\underline{\mathbf{Answer:109}}$

$\mathbf{\underline{Explanation:}}$

Take $\mathbf{n=3}$, then the number of vetices $=\mathbf{3!}$

Now, possible numberings for $\mathbf{"123"}$ are:

$\mathbf{213,132}\Rightarrow$ Number of degrees.

$\therefore$ For $\mathbf{n=3}$.

Degree $=2 = \mathbf{n-1}$

$\therefore$ For $\mathbf{100!}\;\;\;$ Degree $=\color{blue}{\underline{99}}$

For $\mathbf{n=3}$, Number of connected components $=\color{blue} 1\;\;\text{[$\;\because$ Only 1 connected component is possible.]}$

$\therefore$ For $\mathbf{n=100!}$, Number of connected components possible $=1$

$\therefore \;\mathbf{y = 99, z = 1}\\ \therefore 99 + 10\times 1 = 109.$

Hence, $\mathbf{109}$ is the correct answer.
edited by
2 votes
2 votes
G is a graph with 100! vertices. Label of each vertex obtains from distinct permutation of numbers “1, 2, … 100”.
There exists edge between two vertices iff label of ‘u’ is obtained by swapping two adjacent numbers in label of ‘v’.
Example:
12 & 21, 23 & 34
The sets of the swapping numbers be (1, 2) (2, 3) (3, 4) … (99,100).
The no. of such sets are 99 i.e., no. of edges = 99.
As this is regular, each vertex has ‘99’ edges correspond to it.
So degree of each vertex = 99 = y.
As the vertices are connected together, the number of components formed = 1 = z
y + 102 = 99 + 10(1) = 109
Answer:

Related questions

35 votes
35 votes
9 answers
1
gatecse asked Feb 14, 2018
17,335 views
Consider the following undirected graph $G$:Choose a value for $x$ that will maximize the number of minimum weight spanning trees (MWSTs) of $G$. The number of MWSTs of $...
38 votes
38 votes
5 answers
3
gatecse asked Feb 14, 2018
21,939 views
Consider the weights and values of items listed below. Note that there is only one unit of each item.$$\begin{array}{|c|c|c|}\hline \textbf{Item number} & \textbf{Weigh...
35 votes
35 votes
7 answers
4