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.

Filter by
Sorted by
Tagged with
-1
votes
0answers
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.
2
votes
1answer
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 ...
3
votes
3answers
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 ...
0
votes
0answers
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-...
0
votes
0answers
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 ...
0
votes
0answers
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$ ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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$.
0
votes
1answer
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 ...
0
votes
0answers
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 ...
-1
votes
0answers
80 views

Minimizing Area of Nodes from a Stern-Brocot Tree

Consider a subtree of the Stern-Brocot tree consisting of $n$ nodes or fractions $\frac{y_i}{x_i}$. I'm saying that a subtree $T$ of the Stern-Brocot tree is minimal if $Area(T) = \left( \sum_{i=1}^{n}...
1
vote
1answer
51 views

Will this function grow faster than Busy Beavers as $n \to \infty$

Consider the following function: $$f(x)=x \uparrow ^{x} x$$ Where the notation $\uparrow$ is Knuth's up-arrow notation and $\uparrow ^{n}$ means $n$ number of up-arrows. For example, $2\uparrow ^{4}...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
4
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
3
votes
2answers
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. ...
0
votes
1answer
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. ...
0
votes
1answer
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 ...
0
votes
1answer
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$...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
3
votes
1answer
123 views

Show that the number of leaves in a tree equals to $\frac{1}{2}\left(\sum_{v\in V}|\text{deg}(v)-2|+1\right).$

Show that the number of leaves in tree equals to. $$\frac{1}{2}\left(\sum_{v\in V}|\text{deg}(v)-2|+1\right).$$ I know the theorems, For any graph, $\sum_{v\in V} \text{deg}(v) = 2 \left\vert E \...
1
vote
0answers
12 views

Minimum number of nodes perfect binary tree

definition of perfect binary is "which all internal nodes have two children and all leaves are at same level" perfect binary tree i know max. node number: 2^h - 1 (h>=1) but i cant figure out, ...
0
votes
1answer
19 views

Prove that a red-black tree with $n$ internal nodes has height at most $2\lg(n+1)$

I cannot understand the first paragraph of the proof, which comes from the known book Introduction to Algorithms, third-edition, and I consider it has some errors, could anyone help me check about it? ...
0
votes
2answers
71 views

Maximum cut vertices of an Eulerian graph

How can I find maximum number of cut vertices of a Eulerian graph with $n$ vertices?
0
votes
0answers
14 views

A few birds to all three trees

As we know, birds called Darsa are guests of Arak every year on special days A number of these trees attacked a garden full of fruit trees If we know that 100 birds have attacked the apple tree, 50 ...
0
votes
0answers
16 views

subset S of a MST of a given graph

Is a subset S of a MST of a given graph necessarily a collection of trees which are MSTs of the graph defined by the edges included in S, component by component?
1
vote
2answers
58 views

maximum number of leaves in spanning tree

We have a graph with $9n^2$ vertices and put vertices in a $3n*3n$ table. two vertices are adjacent in graph if they are adjacent in table. what is maximum number of leaves in a spanning tree of this ...
2
votes
1answer
30 views

2 edge-disjoint trees in graph

Under what conditions can we construct 2 edge-disjoint trees in a finite undirected graph? I think might be addressed by "On the Problem of Decomposing a Graph into $n$ Connected Factors" by W. T. ...
1
vote
0answers
23 views

Number of non-planar increasing labeled trees

I want to calculate the number of non-planar increasing labeled trees with generating functions. Where increasing means that the labels of a path starting at the root form an increasing sequence of ...
2
votes
1answer
53 views

Why does $\bigcup_{i\in\emptyset}i=\emptyset$ (the empty union)

It seems that the consensus/convention is that the empty union, $\bigcup_{i\in\emptyset}i=\emptyset$ At first glance this seems intuitive, however please consider my following arguments and let me ...
1
vote
0answers
15 views

Monadic Second-order Logic of 2 Successors and Binary Tree Automata

I would like to find a good reference detailing the mapping between Monadic Second-order Logic of two successors (MS2S) and infinite binary tree automata. In particular I'd like to see a well ...
0
votes
0answers
7 views

binary search tree rotations

if I have two binary search trees with the same keys(n keys) but not identical, I can get from the first tree to the other by maximum n tree rotations. how can I prove it? for example I can get from ...
0
votes
0answers
31 views

AVL tree insertion + rotation example - doubt

This question is about a section of the "Mathematics for Computer Science" book (Meyer, Leighton, Lehman, 2018). In section 7.6.7, the text shows an example of AVL tree insertion with rotation. The ...
0
votes
0answers
6 views

Number of rooted trees when inserting operators in not completed expression

I was trying to solve the exercise but could not find any reasonable answer. Also tried to search for similar exercises but could not find anything. I can use binary operators +, -, *, / and ...
2
votes
1answer
45 views

Generate all nonisomorphic rooted trees from a vertex set with a common root

For a vertex set $v = \left\{v_1...v_n \right\}$ and a common root $r$, is there an efficient (maybe $O(1)$ per tree) algorithm that generates all non-isomorphic trees on all nodes $v$ and with root $...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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$ ...
1
vote
1answer
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. ...
0
votes
0answers
9 views

Under what conditions can we guarantee that all maximum branchings are maximum trees?

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 ...
0
votes
0answers
22 views

For any odd positive integer $n$, there is a recursive binary tree that has depth at most $\log_2(n)$ - why?

In chapter 7 of "Mathematics for Computer Science" (Lehman, Leighton, Meyers, 2018), I have a doubt concerning a theorem about binary trees. Relevant definitions Before going into the specific doubt,...

1
2 3 4 5
29