# Tagged Questions

For questions about trees in graph theory, which are connected graphs with no cycles. Also can be used for questions about forests, which are graphs that are disjoint unions of trees.

9 views

35 views

### Find a minimum spanning tree using Prim's algorithm

I have the adjacency matrix: Where we have nodes a to g, and with their respective weights x means symmetry, and the spaces left out are positive infinity \begin{array}{c|c|c|c|c|c|c|c|} & ...
17 views

### Finding the smallest decision tree of a Boolean function

From Computational Complexity: A Moden Approach, A decision tree is a model of computation used to study the number of bits of an input that need to be examined in order to compute some ...
91 views

### Prove that at least one edge of minimum weight is in the minimum spanning tree of a graph.

Let G be a connected graph with edge weights w. Suppose T is a minimum spanning tree of G. Let X be any nonempty proper subset V(G). Prove that at least one edge of minimum weight in the cut induced ...
### Depth first search tree in an undirected graph $G$.
Let $T$ be a depth first search tree in an undirected graph $G$. Vertices $u$ and $ν$ are leaves of this tree $T$. The degrees of both $u$ and $ν$ in $G$ are at least $2$. which one of the following ...