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

75 views

### Prove by induction: A tree on n≥2 vertices has ≥2 leaves

This is what I have. I'm pretty sure this is quite incorrect, but am I at least headed in the right direction? Base Case: $P(2)$: Tree on 2 vertices can only have one edge, the edge connecting the ...
47 views

### How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees: Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...
26 views

### Is the path from u to v is diameter of the tree?

The diameter of a tree is the longest (simple) path in the tree. Let u be a vertex in a tree and let v be the farthest from u vertex in T. Show that the path from u to v may not be a diameter I am ...
18 views

### Minimal spanning trees in multigraphs with constraints

I have a multigraph G whose edges have three identities. Let's say I have three colors of the edges red, blue and green and each two nodes may be connected by a red, blue and/or green edges. The graph ...
32 views

### Is there an efficient algorithm to find all the maximum matching in any tree?

A matching in a graph (G) is a set of mutually non-adjacent edges of (G). A maximum matching is a matching maxima cardinallity. A tree is an acyclic connected graph. Is there an efficient algorithm ...
12 views

### Minimum number of pages in a B-Tree of order n?

How can I calculate the minimum number of pages in a B tree of order n and height 3? 1st level = 1 page 2nd level = 2n+1 pages 3rd level = ? 3rd level is 1? Or how many pages?
19 views

### Completion of acyclic sub graph

Statement: Given an acyclic subgraph of a connected graph, show that this subgraph can be completed into a spanning tree of the graph. I know that there is a theorem that states that any connected ...
68 views

### Difference between Depth first search and Breadth first search algorithm

Currently I am studying Depth first search algorithm and Breadth first search algorithm. Both these algorithms are looking quite similar to me except for some differences. In BFS, we start with a ...
14 views

### Minimum Path Cover in Trees

We have a Tree with $m$ nodes and $m-1$ edges. We are given $Q$ queries. Each query consists of a list of nodes of size $k$, $[n_1, n_2, ..., n_k]$. I need to answer the minimum number of paths that ...
23 views

### Nodes lying on Same Path in Trees

Given a Treen with $n$ nodes and $n-1$ edges, I have to answer $Q$ queries. In every query, I get a list of nodes of size $k$, $n_1, n_2, ..., n_k$. I need to answer the minimum number of paths that ...
21 views

### Binary Decision Trees

I know the basics to a binary decision tree, but this problem has me a little stumped, and I'm looking for some verification on my ideas. The problem is: "Create a binary decision tree that reflects ...
34 views

### Constructing a computably infinite tree with no computable infinite branches using PA

Define an infinite tree as any set of sequences closed under prefix restriction, i.e. any prefix restriction of a sequence in the set is also in the set, where a prefix restriction is a restritcion of ...
30 views

### Show that in a binary tree, if B is the number of branch points (including the root) and L is the number of leaves, then one has the relation L = 1+B

We have been discussing trees lately, but have yet to even touch on the topic of a binary tree. I understand what a leaf is, but we didn't have one for the term "branch points" Without being 100% sure ...
51 views

### How to prove that each edge of tree is a bridge?

How to prove that each edge of tree is a bridge? My attempt: Tree is a connected graph which has no cycle, and in a connected graph, bridge is a edge whose removal disconnects the graph. Let G ...
28 views

### Question about theorem with trees

I know the theorem: for an undirected graph on $n$ nodes, any of the following two imply the third: $G$ is connected $G$ does not contain a cycle $G$ has $n-1$ edges (source) ...
21 views

### Minimum biconnected graph from spanning tree algorithm

I'm thinking about if there exist an algorithm, which can build a biconnected graph from spanning tree? The problem is that it should be minimal-weight (each edge between every pair of nodes has it ...
44 views

### Finding the probability using a tree.

Let's say a specific exam has 3 levels (I, II, III). The candidates who pass the first exam are then eligible to take the next level of the exam. Let's say the pass rates for levels I, II, and III are ...
16 views

### Treewidth Of Graphs And Chordal Completion

https://en.wikipedia.org/wiki/Treewidth The above page explains what a tree decomposition is, and states that treewidth of G is equal to the minimum clique number, minus one, of a chordal ...
32 views

### You can always delete a vertex from a tree $G$ such that the remaining connected components have size at most $|V(G)|/2$.

I want to prove the statement in the title: for any tree on $n$ vertices, it is possible to delete a vertex such that the deletion leaves connected components with at most $n/2$ vertices each. I drew ...
16 views

### Finding Height, Number of Leaves, and Value at of Each Node on Recursive Trees

I have an exam tomorrow and am struggling to understand how to get the height of a tree, the number of leaves, and the value of each node. The image is a practice exam. Any tips and help on the first ...
19 views

### Domain of Injectivity of Analytic Map

Suppose we have an analytic map $f: \mathbb{D} \to \mathbb{C}$. Then the set of points where the function is not locally injective is a discrete set. Suppose first for simplicity that the points ...
43 views

21 views

### Maximum number of strict binary trees that can be made, each having exactly n leaf nodes.

I am trying to evaluate(Mathematical expression) the number of strict binary trees that can be made with n leaf nodes. I already know that a strict binary tree with n leaf nodes would have exactly ...
20 views

### Uniqueness of spanning trees made using search algorithms?

For undirected graphs, the corresponding spanning trees can be obtained using various search algorithms like Depth-first search algorithm , Bredth-first algorithm, etc. I am not sure whether the ...
33 views

16 views

### Example of a Shortest Path Tree for a Directed Graph that contains a directed cycle of negative length

My colleague says this is possible, but I don't understand how. I know it is necessary for the directed Graph to contain no negative cycles in order to prove that the Shortest Path Tree exists. So I ...
42 views

### Black Depth in Red-black Tree?

Wikipedia's Red-black tree states the last property of a Red-black tree: Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes. Some definitions: ...