GATE CSE 2018 | Question: 43

Question

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=$ ______.

Comments

Then they would’ve mentioned in-degree and out-degree separately , wouldn’t they ? By mentioning degree only , it also hints towards undirected graph.

---

For geting z connected component try to take 1,2,3 and gnrate all 6 combinations of it 

and then try start with (1,2,3) and try to get one of node among those 6 nodes by swaping any two adjacent labels and so on ……..

at the end you find that every vertex or label is reachable from every label so that z=1

---

let question states that there are 3! vertices = 6,

where every vertex is numbered from permutations of the numbers {1,2,3}

so the vertices are labelled as

123, 132, 213, 231, 312, 321 these are the 6 vertices

so the edges exist if we can form another permutation only by swapping adjacent no.s like in 1234 we can swap 12 , 23 , 34 only but not 14, 24 ,etc

so we find that every vertex has a degree 2 after connecting the edges

similarly, if we draw for 4! vertices we get degree 3

so for 100! , degree of each vertex is 99 = y

and there is a path from every vertex to other vertex  = z= 1

thus, 99 + 10 * 1  =109

Answer 1

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

Comments

thank you !

 

---

Nice answer

---

@moh_haris thanks man 

Answer 2

$\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.

Comments

Only 1 triangle is possible.

for n=3 we will get a hexagon, not a triangle since we have 3! vertices.

---

No, I am talking about the connected components.

---

“There is an edge between vertices u and v if and only if the label of uu can be obtained by swapping two adjacent numbers in the label of v” , BUT it is not given that we can do only 1 swap

(123) can be converted to (321) in two consecutive swaps of adjacent numbers...

---

Watch this for better understanding   Click here

Answer 3

Please refer the page that i post below:

 

 

Answer 4

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 5

Here its mentioned that edge id obtained only when”swapping two adjacent numbers”.  Hence degree of each vertex will be 99 and the graph is undirected and connected hence itself is a component. thus y=99 and z=1, so value becomes 109

Answer 6

In this question,
For n! vertices (Each vertex will have n numbers), (n-1) adjacent pairs {swapping two adjacent numbers in the label of v}.
So each vertex can connect with (n-1) vertices.

Conclusion,
Graph is (n-1) regular graph
Each vertex (n-1) degree
Component = 1 (which os obvious in this question)

For n=100,
degree = 99, component = 1
99+10*1=109