title: Basic Questions about Minimum Spanning Tree
body: <p>This is not a homework. I am trying to do exercises from a textbook to understand <code>MST (minimum spanning tree)</code>.</p>
  
  <p>Suppose I have a cycle <code>C</code> in a weighted undirected graph <code>G</code>. As I understand, the following is correct:</p>
  
  <ul>
  <li>The <em>heaviest</em> edge in <code>C</code> belongs to <em>no</em> MST of <code>G</code>. That is, there is <em>no</em> MST of <code>G</code>, which contains that edge.</li>
  <li>The <em>lightest</em> edge in <code>C</code> belongs to <em>some</em> MST of <code>G</code>. That is, there is an MST of <code>G</code>, which contains that edge. </li>
  </ul>
  
  <p>Now I wonder if the followings claims are correct too.</p>
  
  <ul>
  <li>The <em>lightest</em> edge in <code>C</code> belongs to <em>all</em> MST of <code>G</code>. That is, there is <em>no</em> MST of <code>G</code>, which does not contain that edge. </li>
  <li>Any edge in <code>C</code> except the <em>heaviest</em> one belongs to <em>some</em> MST. That is, for each edge in <code>C</code> except the <em>heaviest</em> one there is an MST, which contains that edge.</li>
  </ul>
  
  <p>Could you prove the last claim?</p>