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

137 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 ...
39 views

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

### Name for a Type of Tree Diagram (Simplified Family Tree)

I just want to know what the name for this type of tree diagram is. In order to be clear, I want terminology like "binary tree" or something like that (but a name which actually applies). If I ...
22 views

### finding heap child and partents

I did anwer the question but I'm not sure if this is right. can you guys double check my answer and let me know if its wrong. Question 1: For the heap element at position i in the underlying array of ...
56 views

### Graph Theory: Are Infinite Trees Planar?

Graph theory: Are infinite trees planar? I think countable trees are, but not uncountably infinite trees, apparently. How does one construct such a tree?
52 views

### Finding element in binary min-heap

I am trying to answer two questions. Can some one check my answer and let me know if its correct or not? Question 1: Which locations in a binary min-heap of n elements could possibly contain the ...
60 views

### How to prove that a connected graph with $|V| -1= |E|$ is a tree?

I could neither show myself nor find a proof of the following result: if $G=(V,E)$ is a connected graph with $|E|=|V|-1$ then $G$ is a tree. Could somebody please provide an argument to establish ...
22 views