47 votes
Accepted

Do any two spanning trees of a simple graph always have some common edges?

No, consider the complete graph $K_4$: It has the following edge-disjoint spanning trees:
user avatar
18 votes
Accepted

Does a graph always have a minimum spanning tree that is binary?

There is nothing to be done: for instance, let $S_k$ denote the star graph with $k$ leaves. The graph $S_k$ has a unique spanning tree (which is $S_k$ itself), and it has a vertex with degree exactly $...
user avatar
  • 22.1k
16 votes

Minimum spanning tree vs Shortest path

Though Minimum Spanning Tree and Shortest Path algorithms computation looks similar they focus on 2 different requirements. In MST, requirement is to reach each vertex once (create graph tree) and ...
user avatar
  • 271
14 votes

Do any two spanning trees of a simple graph always have some common edges?

For the more interested readers, there are some research on decomposition of graph into edge-disjoint spanning trees. For example, the classical papers On the Problem of Decomposing a Graph into $n$ ...
user avatar
  • 34.7k
13 votes
Accepted

When is the minimum spanning tree for a graph not unique

in the first picture: the right graph has a unique MST, by taking edges $(F,H)$ and $(F,G)$ with total weight of 2. Given a graph $G=(V,E)$ and let $M=(V,F)$ be a minimum spanning tree (MST) in $G$. ...
user avatar
  • 548
12 votes

Is it possible for a graph to have two different minimum spanning tree

It is possible to have different minimum spanning trees for a graph. Consider a simple example: a cycle graph with all weights equal. Removing any edge from the graph produces a minimum spanning tree ...
user avatar
10 votes

Minimum spanning tree vs Shortest path

I think an example will make it clearer.. The spanning tree looks like below. This is because if we add up the edges in this configuration, we get the least total cost possible: 2+5+14+4=25. ...
user avatar
  • 363
10 votes
Accepted

Algorithm to get any spanning tree not necessarily a minimum spanning tree

Use the BFS or the DFS algorithms. They work in $O(n)$ and output a spanning tree if the input is a connected graph
user avatar
  • 10.9k
10 votes

Algorithm to get any spanning tree not necessarily a minimum spanning tree

Just do a graph traversal algorithm, like DFS or BFS.
user avatar
  • 7,193
9 votes
Accepted

Is there a flaw in this Wikipedia proof of cycle property of Minimum Spanning Tree?

First off to answer your main question: there is no flaw in the proof. The point where you are not following the reasoning of the proof is that: E belongs to a cycle in the graph and to the MST. ...
user avatar
9 votes

Do any two spanning trees of a simple graph always have some common edges?

EDIT: This is incorrect as pointed out in the comments. As the other answer says, a spanning tree for $K_4$ can be done without sharing edges. No, it's not true that any two spanning trees of a graph ...
user avatar
  • 500
8 votes

Minimum spanning tree vs Shortest path

The difference lies in what is the ultimate goal of this algorithms- Dijkstra's - Here the goal is to reach from start to end. You are concerned about only this 2 points, and optimize your path ...
user avatar
8 votes

Diameter-constrained Minimum Spanning Tree Problem

Consider the complete graph $K_n$ in which all edges have the same cost. All trees are MSTs. They have diameter ranging from $2$ all the way to $n-1$.
user avatar
7 votes

Difference between spanning tree and a tree?

Given a graph $G$, a spanning tree is a subgraph of $G$ that (i) is a tree, and (ii) has all the vertices in $G$. There can be many spanning trees for $G$. If you put weights on the edges, one of ...
user avatar
  • 20.4k
7 votes
Accepted

Need a hint! Karger's algorithm versus Kruskal, spanning tree distribution

You should show that at each step, both algorithms select an edge with the same probability distribution. For example, the first edge that is contracted by Karger's algorithm is a uniformly random ...
user avatar
7 votes
Accepted

Diameter-constrained Minimum Spanning Tree Problem

There is no direct relationship between the diameter of a (minimum) spanning tree and the total cost of the tree1. Consider the following example: The spanning tree on the left (whose edges are ...
user avatar
7 votes
Accepted

How does Dijkstra's problem 1 (tree of minimal total length) work and what does it do?

In modern terms, this problem is called Minimum Spanning Tree: Find the subtree of the input graph that minimizes the total weight of its edges. The algorithm here suggested by Dijkstra is today known ...
user avatar
  • 552
6 votes

Minimum spanning tree and its connected subgraph

Flaws in the accepted answer: When I re-read the accepted answer given by @Mahmoud A. today, I find flaws in it. Consider the figures for an example: In this example, $e = CE$. In figure (5),...
user avatar
  • 9,219
6 votes

Find an MST in a graph with edge weights from {1,2}

Alternatively use Prim's algorithm. No need to keep track of components. Prim considers each edge once (assuming adjacency-lists). The most costly part of Prim is looking for the next vertex to add: ...
user avatar
  • 27.7k
5 votes

Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?

Here is a slightly simpler argument that also works for other matroids. (I saw this question from another one.) Suppose that $G$ has $m$ edges. Without loss of generality, assume that the weight ...
user avatar
  • 2,886
5 votes

What edges are not in any MST?

A Google search for "edges not in MST" leads me to this question. The answer included in the question has already been found wrong, as OP said in the last comment. For future references, ...
user avatar
  • 34.7k
5 votes

Determining if an undirected connected graph is minimally connected

If $G$ is an undirected graph, it's a standard lemma that the following are equivalent: $G$ is a tree. $G$ is connected and has no cycles. $G$ is connected and the number of edges is one less than ...
user avatar
  • 143k
5 votes
Accepted

Finding MST after adding a new vertex

As stated in your post, the idea is to use Prim's algorithm with only the edges from $T$ and the new edges, let's call them $E'$. For the sake of simplicity, let's assume that $T$ is the unique MST. ...
user avatar
  • 166
5 votes

When is the minimum spanning tree for a graph not unique

A previous answer indicates an algorithm to determine whether there are multiple MSTs, which, for each edge $e$ not in $G$, find the cycle created by adding $e$ to a precomputed MST and check if $e$ ...
user avatar
  • 34.7k
5 votes
Accepted

Is every edge of a graph included in some spanning tree?

Note that the initial graph $G$ needs to be connected or it has no spanning trees at all. (Though the same argument applied to each component would show that any graph has a spanning forest ...
user avatar
5 votes
Accepted

Christofides algorithm (by hand) (suboptimal solution - is it my fault?)

As mentioned by Yuval, Christofides’ algorithm is an approximation algorithm to the travelling salesman problem. It is not guaranteed to produce an optimal solution. So it is not unexpected that you ...
user avatar
  • 34.7k
5 votes

How does Dijkstra's problem 1 (tree of minimal total length) work and what does it do?

The tree of minimum total length is nothing but the minimum spanning tree. The algorithm that you are talking about is nothing but Prim's algorithm, also called Prim–Dijkstra algorithm. Answer to Your ...
user avatar
4 votes

Borůvka cleanup in linear time?

This depends on what you mean by linear time. If you want $O(n)$, then you're out of luck, there's too many edges to consider in the worst case. If you mean $O(n+m)$, then it is possible, and it is ...
user avatar
4 votes

Minimum spanning tree vs Shortest path

The key is to understand that they are different problems: The spanning tree looks to visit all nodes in one "tour", while shortest paths focuses on the the shortest path to one node at a time. As ...
user avatar
4 votes
Accepted

Find an MST in a graph with edge weights from {1,2}

Since you have only 2 possible edge weights you can perform a linear time sort on the edges, then perform Kruskal's algorithm. The complexity of Kruskal's algorithm comes from its need to sort the ...
user avatar
  • 1,602

Only top scored, non community-wiki answers of a minimum length are eligible