title: Weighted graph problems, TRUE/FALSE + explanation
body: <p>I'm trying to get some true/false questions done. I'm getting worried when I'm answering many of them with true... Please assume that all graphs are <strong>undirected</strong> and do <strong>not</strong> have <strong>distinct weights</strong>. Negative weights should be fine.</p>
  
  <p>Qa) If G has a cycle with a unique heaviest edge e, then e cannot be part of any MST.</p>
  
  <p>My answer is true.
  For example, we have a graph with nodes A, B, C, D, E.</p>
  
  <pre><code>AB = 1
  BC = 2
  BD = 3
  CD = 100
  DE = 4
  </code></pre>
  
  <p>As you can see, BCD is a cycle.
  My argument is that since it is a cycle, we can always avoid the unique heaviest edge CD by taking other routes. Therefore it is true. Is my argument sound (enough)?</p>
  
  <p>Qb) The shortest-path tree computed by Dijkstra's algorithm is necessarily an MST.</p>
  
  <p>My answer is true, but my instinct tells me something's wrong.
  Well... Disjkstra's and Prim's are both greedy algorithms. They both go for the lightest weighted edge every time.
  Are there any cases that a shortest-path tree is <strong>NOT</strong> a minimum spanning tree?
  I actually have a hard time understanding the difference between these two guys.</p>
  
  <p>Qc) Prim's algorithm works with negative weighted edges.</p>
  
  <p>My answer is true. Because that's what wiki said... :p
  The algorithm is about finding the lowest-cost edge among all edges. So a negative weighted edge shouldn't matter, is it? But what about negative weighted cycle?</p>
  
  <p>Qd) If G has a cycle with a unique lightest edge e, then e must be part of every MST.</p>
  
  <p>My answer is true.
  We have to access all nodes in an MST. In a cycle of length 3, for instance, we can always traverse all nodes in that cycle with 2 steps. If there is a unique lightest edge, we'll most certainly choose it in our MST.</p>
  
  <p>Are my claims sound? Perhaps they are insufficient? So are there any suggestions? </p>