Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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:
Bjørn Kjos-Hanssen's user avatar
15 votes
Accepted

Can every spanning tree result from a depth-first search?

Consider a complete graph $K_n$. Then a depth-first search can only create a linear-path spanning tree, no matter what the edges processing order is.
Nathaniel's user avatar
  • 15.7k
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$ ...
John L.'s user avatar
  • 39k
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$. ...
dtt's user avatar
  • 558
12 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. ...
Pithikos's user avatar
  • 393
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
nir shahar's user avatar
  • 11.6k
10 votes

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

Just do a graph traversal algorithm, like DFS or BFS.
Nathaniel's user avatar
  • 15.7k
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 ...
Gokul's user avatar
  • 520
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$.
Yuval Filmus's 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 ...
Mario Cervera's user avatar
6 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, ...
John L.'s user avatar
  • 39k
6 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. ...
T. Silver's user avatar
  • 176
6 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$ ...
John L.'s user avatar
  • 39k
6 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 ...
Highheath's user avatar
  • 1,048
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 ...
David Richerby's 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 ...
John L.'s user avatar
  • 39k
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 ...
Inuyasha Yagami's user avatar
5 votes
Accepted

Finding existence(or non existence) of spanning tree with a specific degree on a specific vertex

First, verify that $G$ is indeed connected, otherwise say no. Second, if $G - v$ (the graph after deleting $v$) has more than $k$ components, we can say no. Pick any $k$ neighbors of $v$ with the ...
Pål GD's user avatar
  • 16.5k
4 votes

When is the minimum spanning tree for a graph not unique

Let $G$ be a (simple finite) edged-weighted undirected connected graph with at least two vertices. Let ST mean spanning tree and MST mean minimum spanning tree. Let me define some less common terms ...
John L.'s user avatar
  • 39k
4 votes
Accepted

safe edge for Minimum spanning tree

For a set $A$ which is a subset of some minimum spanning tree, an edge $e \notin A$ is safe if $A \cup \{e\}$ is a subset of some minimum spanning tree. In particular, if $|A| = n-2$, then any safe ...
Yuval Filmus's 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 ...
Jose H. Martinez's user avatar
4 votes
Accepted

Min spanning tree that preserves total weight of original graph

Let us represent the people involved by numbers $1,\ldots,n$. For person $i$, let $\delta_i$ be the total amount that person $i$ is owed minus the total amount that she owes; notice that $\sum_{i=1}^n ...
Yuval Filmus's user avatar
4 votes
Accepted

Kirchhoff's Spanning Tree Algorithm

It looks like magic because the proof of Kirchhoff's Matrix Tree Theorem is nontrivial. It relies on several algebraic properties of the matrix constructed in steps 1-3, which is called the Laplacian ...
Vincenzo's user avatar
  • 3,302
4 votes
Accepted

Prove finding a spanning tree with no more than 50 leaves is NP-hard

Yes, this problem is indeed $\text{NP}$-hard. Here is a hint of proof. Draw several trees with 2 leaves. What kind of graphs are they?
John L.'s user avatar
  • 39k
4 votes

Spanning tree - minimum difference between smallest and largest weight

You can solve the problem in $O(m \log n)$ time. For the sake of simplicity assume that all edge weights are distinct (this assumption can be easily removed). Let $e_1, e_2, \dots, e_m$ be the edges ...
Steven's user avatar
  • 29.5k
4 votes
Accepted

Spanning tree - minimum difference between smallest and largest weight

I realized that my answer is similar to Steven's answer but maybe suitable for someone. Based on increasing values of weights, sort the edges; e.g. $e_1,...,e_m$. For $i=1,...,m-n+1$ (we need atleast $...
Majid Zohrehbandian's user avatar
3 votes
Accepted

How to find total number of minimum spanning trees in a graph with n edges?

I'm hoping you misremembered the question, as the number of MSTs (minimum spanning trees) is not uniquely determined by the number of edges. It depends on what edges are and are not present and also ...
David Richerby's user avatar
3 votes

Spanning tree with chosen leaves

The solution can be found here which is similar to that suggested by @hengxin Minimum spanning tree with chosen leaves Outline of the algorithm Generate an induced graph ...
Stuxen's user avatar
  • 159
3 votes

Find a graph for which Kruskal's algorithm achieves worst-case running time

Let the answer be a complete graph $G = (V,E)$ with $|V| = n$ and a weight function $W : E \to \mathbb{R}$ Let the vertices be denoted by $1,2,\dots n$ and edges between $i$ and $j$ as $(i,j)$. Now ...
Banach Tarski's user avatar
3 votes

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

After observing the graphs presented by @Bjorn and @Gokul, I arrive at the conclusion that every complete graph $K_n$ with $n\geq4$ has at least two spanning trees with disjoint edges. The graph ...
Mr. Sigma.'s user avatar
  • 1,303

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