# Tag Info

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:
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.
• 15.8k

### 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$ ...
• 39.1k
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$. ...
• 558

### 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. ...
• 393
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
• 11.6k

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

Just do a graph traversal algorithm, like DFS or BFS.
• 15.8k

### 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 ...
• 520

### 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$.
• 278k
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 ...
• 3,724
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. ...
• 176

### 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$ ...
• 39.1k

### 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, ...
• 39.1k
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 ...
• 1,075
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 ...
• 81.9k
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 ...
• 39.1k

### 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 ...
• 6,187
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 ...
• 16.7k

### 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 ...

### 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 ...
• 39.1k
Accepted

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 ...
• 81.9k

### 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 ...
• 159
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 ...
This is not the case. If an edge $e$ is a bridge in the graph, then every MST has to include $e$. There can exist some cut in which $e$ is the heaviest edge, but this does not change the fact that $e$ ...