Proof about spanning trees

Правка en1, от snorkel, 2021-09-09 16:01:11

Hi, let's consider this problem.

If you have a connected graph with edges colored red or blue, to find out whether you can construct the spanning tree with exactly $$$K$$$ number of blue edges then — find the minimum number of blue edges that can be used, also find the maximum. If $$$K$$$ is in $$$[min, max]$$$ then it's possible, otherwise, no.

What is the proof of it?

I was thinking like this — If it is possible to construct the tree with $$$A$$$ vertices, and also with $$$A + 2$$$ vertices, then $$$A + 1$$$ is also possible, but why, how? Can we probably relate the solution with $$$A$$$ vertices to $$$A + 2$$$ vertices?

Thanks.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский snorkel 2021-09-09 16:01:11 656 Initial revision (published)