3

The following graph consists of 50 vertices, with 25 vertices in each circle, and each vertex having a degree of 3. How many ways can we select 23 vertices from this graph such that they are not adjacent?

enter image description here

Do you have any suggestions or ideas on how to approach?

Ariana
  • 375
  • 1
    This bi-partite graph problem could be parameterized with $2n$ vertices, here $n=25$. Why don't you attempt to elaborate a method on a lower value of $n$ ? For example, if $n=4$, how many solutions do you find ? – Jean Marie Feb 18 '24 at 10:23
  • @JeanMarie I researched and found out if we can color a graph with 2 color it is bipartite and because every vertex has 3 degree so our graph is 3-regular bipartite. I tried to pick up from right and left part of the bipartite graph but It didn't work. I have the same problem for small n too. Can you give me more tips? – Ariana Feb 18 '24 at 12:01

2 Answers2

5

These vertices are in two circles. Note that we must take $11$ vertices from one circle and $12$ from the other. Otherwise we take $13$ or more vertices from one circle and since $2\cdot13>25$ there would be adjacent chosen vertices.

Suppose we take $12$ vertices from the inner circle. There are $25$ ways to do it. Indeed, every $2$ neighbour chosen vertices must have at least $1$ not chosen vertex in between them. Since there are $25-12=13$ not chosen vertices, there must be $2$ adjacent not chosen vertices.

What about the outer circle? $12$ of the vertices there are banned since they are adjacent to the chosen vertices from the inner circle. There are $2$ adjacent vacant vertices from the rest $13$, at most one of them can be chosen. If none of those two is chosen, there is the only way to choose $11$ vertices from $11$ vacant ones.

If one of them is chosen ($2$ ways to choose one), we must choose $10$ more vertices from the rest $11$ vacant ones ($\binom{11}{10}=11$ ways to do it). In total, $1+2\cdot 11=23$ ways to choose $11$ vertices from the outer circle.

To calculate the final answer, we must multiply by $2$ since we could choose $12$ vertices from the outer circle and $11$ from the inner one. Hence the answer is:

$$2\cdot25\cdot23=1150.$$

Aig
  • 4,178
  • Can you elaborate why there are 25 ways of doing it? "Suppose we take 12 vertices from the inner circle. There are 25 ways to do it" – Ariana Feb 18 '24 at 12:16
  • 1
    @Ariana I explain it in the same paragraph. Because there are $25$ ways to choose $2$ adjacent vertices (which is the same as to choose $1$ vertex). – Aig Feb 18 '24 at 12:19
5

We can’t choose two vertices on the same spoke, so we have to choose $23$ out of $25$ spokes, with $\binom{25}{23}$ choices. On any contiguous stretch of selected spokes, we have to alternate between the inner and outer circle, so there are two choices for each such stretch. If the two remaining spokes are adjacent, which happens in $25$ of the cases (as explained in Aig’s answer), there’s a single contiguous stretch and thus only $2$ choices, whereas in the remaining cases there are two contiguous stretches and thus $2^2=4$ choices, for a total of

$$ 2\cdot25+4\left(\binom{25}{23}-25\right)=1150\;, $$

in agreement with Aig’s answer.

joriki
  • 238,052