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

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

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

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

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

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

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

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

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

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

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

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

### Spanning tree with chosen leaves NP-Complete proof

The question you link to shows that the problem can be solved in polynomial time. If the problem was NP-complete, then this would prove that P = NP. Of course, it's a famous open problem to prove ...

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

### 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 ...
It doesn't matter which minimum spanning tree algorithm you use. All you need to notice is that for a tree $T$,  \begin{align*} \sum_{(i,j) \in T} m(e_{ij}) &= \sum_{(i,j) \in T} w(v_i) + w(v_j) ...