Search code examples
python-3.xalgorithmgraphtreeminimum-spanning-tree

True or False: For an undirected graph, for every vertex, its edge with minimum weight is in a minimum spanning tree

I think this is true. With consideration to Prim's algorithm, the minimum edge of a vertex is either already in a tree, or will be selected eventually.

I also tried a lot of graph and they all seem correct.

If this statement is False, can someone give me a counter-example?

Thanks.

Solution

  • Your proof is almost there.

    Proof 1: Prim's algorithm can start at any vertex, and will immediately select the start vertex's minimum edge, or can select any minimum edge if there is a tie.

    Proof 2: In Kruskal's algorithm, one of every vertex's minimum edges will be the first to connect that vertex, and it could be any one of them, if there's a tie, depending on the initial sort.

    Proof 2 actually proves a stronger theorem: Every minimum spanning tree will include a minimum edge for every vertex.