# Questions tagged [trees]

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.

1,437 questions
Filter by
Sorted by
Tagged with
33 views

### Is there a version of TREE($n$) for non-finite $n$?

Is there a version of the TREE function for non-finite $n$ (eg. TREE($\omega$))? I wasn't able to find anything online and I am curious if this is something that has already been studied or not.
20 views

### Does removing the “heaviest” edge of all cycles in an (unweighted) graph result in a minimum spanning tree?

Background: A graph is connected if there is a path between all pairs of vertices. A graph has a cycle if there exists two vertices with an edge between them and a path between them that doesn’t use ...
38 views

### Discrete Mathematics - Trees

Question: Prove that if a tree has a node of degree $n$, it has at least $n$ nodes of degree $1$. My answer: From each of $n$ edges adjacent to the node of degree $n$ a path starts. Each of these ...
23 views

### Kruskal's algorithm for the connector problem with pre-assignment

I am solving the following exercise. Could someone tell me if my algorithm is correct or if there is some more efficient method? Adapt Kruskal's algorithm to solve the connector problem with pre-...
17 views

### Max min spanning tree diameter

For $d \geq 1$ determine: $$\max_{\text{diam}(G) = d} \min \{\text{diam}(T): \, T \, \text{spanning tree of} \, G \}$$ I'm having trouble understanding what this quantity represents. Does this ...
27 views

### Prove that if MST T1 has k edges with weight 1 then T2 has also k edges with weight 1

We have two different minimum spanning trees ($T_1$ and $T_2$) of $G$. The graph $G$ has edges with weight $1$ or $2$. How can I prove that if $T_1$ has $k$ edges with weight equal to $1$ then $T_2$ ...
22 views

### Automorphism group of rooted tree is a profinite group

I'm working with the book Self-similar Groups by Volodymyr Nekrashevych. In the chapter $1$ he statements the following proposition: We have an equality $St_{Aut(X^*)}(n) = RiSt_{Aut(X^*)}(n)$. The ...
28 views

### Use structural induction to prove that $v(G) = e(G) + 1$

$G$ is an element of FBRT (full binary rooted trees), $v(G)$ = total vertices in $G$, and $e(G)$ = total edges in $G$. I know logically that this is true, but I'm not sure how to prove it using ...
34 views

### How to find number of spanning tree?

Suppose $G$ is a $k$-regular graph with $n$ vertices and with eigenvalues $k = λ_1 > λ_2 ≥ \cdots ≥ λ_n.$ Find the number of spanning trees in $G$.
23 views

### Definition of chain of tree

I am trouble understanding the definition of chain of tree at p15. Here is a rooted tree. The root is "a". abc is clearly chain. However, I cannot understand whether bc is chain or not. a | bーd | c ...
4 views

### Logical way to compare vectors to construct binary search tree

In a binary search tree we can sort elements by their size. But what if I would like to organize multidimensional arrays into a binary search tree? We can't directly compare vectors by size. They have ...
80 views

31 views

### What theory should I be applying to these questions about minimum spanning trees?

Was recommended to post this here from stack exchange: Got a couple questions to answer from an assignment and I'm a little stuck on how to go about it, I can't find any similar questions to ...
15 views

### Given an eigenvalue of a tree, what about that eigenvalue when you remove a path from it?

Let $T$ be a tree and $\theta$ an eigenvalue of multiplicity m $\gt$ 1. Let $P$ be a path in $T$. Then prove that $\theta$ is eigenvalue of $T$ \ $P$ with multiplicity at least $m-1$. I tried ...
105 views

### Can Anyone Explain This Property of the Collatz Conjecture ($3n + 1$ problem)

I'm making a program that draws out a tree containing the first $n$ numbers, and how they all reduce to $1$. I noticed something interesting about the number of nodes that are required to connect ...
32 views

### Proving Kirchhoff's Theorem using techniques appreciated by a first year undergrad

I would like to prove Kirchhoff's theorem. Briefly, it states that cofactor of a certain matrix $M$ is equal to the number of spanning trees of the graph. $M$ is equal to the difference between the ...
17 views

### Exponential Growth and Decay Model for Human Genealogy (Common Ancestor)

First time poster, and, as my post will intimate, not a mathematician, just someone searching for answers. My question has two parts: 1) In a genealogical chart for a single individual (called an ...
61 views

### How many labelled trees with $n$ vertices have a vertex of degree $n − 2$?

I have a labelled tree with $n$ vertices for $n > 1$. How do I find the number trees with vertices tree that has a degree of $n-2$? I have been trying to figure it out but cannot seem to solve it. ...
22 views

### Suppose T is a fixed labeled tree on $n$ vertices. how many labeled graphs on $n$ vertices have T as a subgraph?

Suppose T is a fixed labeled tree on $n$ vertices. How many labeled graphs on $n$ vertices have T as a subgraph? I know a tree is a graph in which all vertices have an edge and there are no circuits. ...
12 views

### The FlipBits tree

Take a number, say $n=99_{10}$. Express it in binary, $11000111$. Now flip the bits, $0011100$ and discard leading $0$'s: $11100 = 28_{10}$. Continue until $0$ is reached: $(99,28,3,0)$. Here's a ...
39 views

### Prove that $T$ is a tree of order $n$ if and only if $T$ is a connected graph with size $n-1$.

Prove that $T$ is a tree of order $n$ if and only if $T$ is a connected graph with size $n-1$. Here is my answer. Proof: ($\Rightarrow$) Let $T$ be a tree of order $n$ and let the size of $T$ be $m$...
26 views

### Why is the number of distinct labelings on n vertices the sum of the possible labelings of unlabeled trees on n vertices?

First of all, is this true? Since there is no closed formula for the number of unlabeled trees on n vertices it is not something I know how to prove using, for instance, induction. (This is an ...
11 views

### Take a random walk $X$ on $\mathbb{Z}^d$ with $\tau_v<\infty$, what is the probability that loop-erased random walk has length at most $N$?

More specifically, take $Z$ a random walk on $\mathbb{Z}^d$ for $d\geq3$ (allowing us to use transience properties, I'm unsure if this is helpful). The loop-erased random walk of $Z$, $LE(Z)$ is ...
31 views

### 100 spanning trees for graph G - prove existent of vertex v with degree at least 200

In not directed and connected graph $G=(V,E)$ there are $100$ spanning trees $T_1,T_2,...T_{100}$. Vertex $v$ in tree $T_i$ is signed $d(v,T_i)$ for $i=1,2,...100$. I need to prove the ...
8 views

### the height(h) of a Btree, with n keys, where every node that is not a leaf has exactly d sons, keeps this trait $h\le log_d((d-1)n+1)-1$

how can I prove that the height(h) of a Btree, with n keys, where every node that is not a leaf has exactly d sons, keeps this trait? $$h\le log_d((d-1)n+1)-1$$ I tried this with nodes, but i am ...
123 views

201 views

### rooted tree with internal vertices with exactly 2 children. Prove with induction that $|V| = 2k +1$

I am struggling to understand graph theory induction questions. I understand the basics of induction as well as graph theory, however, when working on these types of problems I seem to struggle to ...
26 views

### Find a hamiltonian path in $T^{3}$

The cube of a graph $T$, denoted $T^{3}$, is the supergraph of $T$ such that the edge $(u, v)$ is in $T^{3}$ if and only if there is a path between $u$ and $v$ in $T$ with three or fewer edges. My ...
22 views

### How many nodes does this graph problem have

Suppose 3 containers have sizes 10 pints, 7 pints and 4 pints respectively. Initially the 10 pint container is empty and the other two are full. This can be represented as (0,7,4) Contents can be ...
15 views

### Upper bound for vertices of degree one in a tree

I have to find an upper bound for vertices of degree one in a tree which has n vertices. I think it would be n-1 - we can always form a tree with one vertice in its center and the other ones are ...
24 views

### Counting Topological Sorts Of Graph With In Degree 1

I was asked this question recently and am struggling to come up with the closed form solution: How many topological sorts are there for a directed acyclic graph where each vertex only has one incoming ...
38 views

### Probability of reaching any node on a lattice tree

I have a tree which looks like N / \ N1 N2 / \ / \ N3 N4 N5 Say we have $L$ levels from $I=0$ to $L-1$ and each has $I+1$ ...
48 views

### Help on computing some property value of a binary tree.

I am trying to compute some properties of a binary tree, but I cant find its formula. What I did to get the initial value is, I draw the binary tree on paper and manually count the nodes, pairs, etc. ...
In graph theory, a rooted spanning tree of a digraph $D$ is a spanning subgraph $T$ such that (i) $T$ has no directed cycle. (ii) There is exactly one vertex $r$ of $T$ with indegree $d^-(r)=0$. All ...