Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
vote
0answers
9 views

What is the lower bound of number of degree 1 vertices of a tree with no degree 2 vertices?

Here is the question: Let $G$ be a tree with $n$ vertices, and no vertex in the tree has degree $2$. Find a function of $n$ that indicates the lower bound of the number of degree $1$ vertices in ...
0
votes
1answer
10 views

Is my graph and tree proofing correct for this degree sequence?

I was wondering if you could help verify if my answer is correct. The question is: Is (1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 4, 5) a degree sequence of a graph? Is it a degree sequence of a tree? ...
0
votes
0answers
18 views

Number of distinct root trees

Suppose we know that the number of distinct regular brackets sequences of length $2n$ equals to $C_n$, where $C_n$ is nth Catalan number. I need to figure out the number of root trees with $n$ ...
-1
votes
0answers
15 views

Is this 2-3 tree correct?

I am helping a student in some material that I am not that familiar with. We are to make a 2-3 tree out of the word COMPUTING using alphabetical order. Is this correct? ...
3
votes
2answers
33 views

tree has exactly $k$ nodes with degree $4$. Show that this tree has $2k+2$ leaves.

Prove: If a tree has exactly $k \geq 1 $ nodes with degree $4$, then this tree has at least $2k +2 $ leaves. ( nodes with degree $< 4 $ are only allowed for the leaves ). So I think that we can ...
2
votes
1answer
111 views

Show that $M_k(G)$ is the set of independent sets of a matroid! [on hold]

Let $G = (V,E)$ be an undirected graph. Set $M_k(G) = (E,S)$ where $$S = \{F ∪M | F ⊆ E,(V,F) \;\text{acyclic},M ⊆ E,|M| ≤ k\}.$$ Show that $M_k(G)$ is the set of independent sets of a matroid! In ...
0
votes
0answers
17 views

Trees for which the Prufer code is a strictly monotone sequence

Problem: Find the number of trees on n labeled vertices such that the corresponding Prufer code is a strictly monotone sequence. So far I tried with some small Prufer code : (1,3,5) or (1,2,3) and in ...
0
votes
0answers
34 views

Number of spanning trees in a bipartite graph

I want to prove that in a complete bipartite graph with vertices $1,..,m$ and $m,..,m+n$, we have $n^{(m-1)}m^{(n-1)}$ spanning trees. Therefore I thought about the matrix tree theorem which states ...
0
votes
1answer
22 views

Tree of order $p$ with $p_i$ vertices of degree $i$ for $i\in\{1,\dots, p-1\}$.

Let $T$ be tree of order (number of vertices) $p$ and with $p_i$ vertices of degree $i$ for each $i\in \{1,\dots, p-1\}$. I am asked to prove that the following equation is satisfied: $p_1=\sum_{i=3}^...
-2
votes
0answers
9 views

Help understanding Pufer's mappings?

I really want to understand how it is that pufer proved that Cayley's formula works(Pgs. 8-9). The proof is uses 2 algorithms which are in page 9. However, in page 10, I do not understand how the ...
0
votes
0answers
57 views

What is the relationship between the external path length, internal path length and total number of nodes of a full ternary tree?

The closest proof I can find is for full binary tree, but I don't understand the last step, i.e. how he links the external path length, internal path length two variables together. Proof
1
vote
1answer
24 views

Time Complexity Of Binary Tree Subtree Algorithm

Given two binary trees, check whether one is a subtree of another one. This is my algorithm. Basically, it says: For two binary trees A and B, A is a subtree of B if they are the same tree. If ...
0
votes
0answers
27 views

Given $x\ y\ +\ x\ z\ +\ *\ y\ z\ *\ +$ recover the tree, write it in usual notation and simplify

Given the boolean expression given in reverse Polish notation $$x\ y\ +\ x\ z\ +\ *\ y\ z\ *\ +$$ recover the tree, write it in usual notation and simplify. The usual notation is $$\begin{array}{ll} ...
0
votes
1answer
10 views

Internal path length of a binary tree with 15 nodes

I am a bit confused about internal path length. I understand it as being the sum of the depth of all nodes except the leaves. Thus I get the internal path length as 10 for a binary tree with 15 nodes. ...
0
votes
0answers
11 views

Evolutionary tree metric

I met a student at the JMM poster session last year who was showing a project studying the distance between organisms, using the tree metric on the evolutionary tree. He had shown some statistical ...
1
vote
1answer
28 views

Find number of BST's possible with 6 nodes numbered 1,2,3,4,5 and 6 having 6 as root and height of 4? [closed]

Find the number of possible BST's with 6 nodes numbered $1,2,3,4,5,6,$ with $6$ as root, and height of four. Can anybody help?
1
vote
0answers
24 views

Does the Laplacian of a path graph have the smallest eigenvalues for any tree graph of equal number of vertices?

Suppose there are two connected graphs with $|V|=n$. One is a path graph $P$ and the other is an arbitrary tree graph $T\neq P$. If $L(G)$ is the Laplacian of the graph $G$, is it true that $$L(T) - L(...
0
votes
1answer
22 views

Counting leafs of a perfect binary tree without knowing number of nodes?

Is it possible to be able to count the number of leafs in a perfect binary tree where the number of nodes is not given? I wanted to use the formula $2l-1$ in my proof for how many nodes are in a ...
3
votes
1answer
31 views

How many different tournament orderings are there?

Assume you have 4 people or teams in a tournament. There will be three games: 3 1 2 a b c d The people/teams in this case are the letters, ...
0
votes
0answers
23 views

Number of Nodes on a Logic Tree

Consider the tree for $(\leftrightarrow)$: The image was found here. Is the number of nodes for this $2$ or $4$? I would think two because $p$ and $q$ are in one node and $\neg p$ and $\neg q$ are ...
0
votes
1answer
26 views

How to calculate the number of items that can fit into a tree

Wondering how to calculate the number of items that can fit into a tree. For example, say at each level of a tree you can have 10 children (aka 10 different "types"). Say you're only considering ...
0
votes
2answers
44 views

Existence of tree for a given degree sequence.

Let $(d_1,..., d_n)$ be a sequence of positive integers with $\sum_{i=1}^n d_i=2(n-1)$. Then there exists a tree $T$ with vertex set $v_1,..., v_n$ and $d(v_i)= d_i , 1\leq i \leq n$. My attempt:- ...
3
votes
1answer
74 views

Proving property of two trees.

Consider a graph $G$. Let $A, B$ are two trees in a graph and $T_a, T_b$ represents their corresponding edge sets. Also an edge $e \in E$ is an extension of tree $A$. If $T_b \cup \{e\}$ forms a cycle ...
0
votes
1answer
22 views

What does the underlined statement mean?

- Since $T_i'$ s are trees it doesn't contain multiple edges. Why it not having the edge from G? What does the statement mean?How do I justify this claim?
0
votes
3answers
42 views

Is any tree a Hamiltonian Graph

Hamiltonian path is a graph where every vertex is visited exactly once. And a tree can be anything, like a BST. I think that this answer is no because in a BST, it could find an element before ...
0
votes
1answer
58 views

Understanding a proof about how counting spanning trees relates to edge deletion and contraction

qerwn Can you please explain the essence of the proof? I understood till the underlined statements. After that, I am not able to understand the proof. What does the author do here? update on the ...
3
votes
2answers
21 views

Let T be tree, the pendant vertices of T cannot be central vertices.

Let $v$ be a pendant vertex and $v$ be a central vertex. So, $e(v)=r(G)=\max\{d(v,u):u \in V(G)\}$. Let $P$ be the longest path from $v$ with length $e(v)$. $e(v) \leq \{e(u):u \in V(G)\}[\because e(v)...
0
votes
0answers
39 views

Expected Size of Subtree Problem

Consider a random binary search tree T on a random permutation of the numbers 1 . . . n (i.e. each permutation is equally likely with probability 1/n!). What is the expected size of the subtree rooted ...
1
vote
0answers
42 views

Proof of well-founded order relation on the set of all finite directed binary trees.

Consider the set of all finite directed binary trees with vertices $V$ and edges $E$. If $T_i=(V_i, E_i)$, $i=1,2$ are trees in this set, then we say $T_1 \sqsubseteq T_2$ if and only if $V_1 \...
0
votes
0answers
23 views

How to prove convergence of the sequence using convergence of blocks?

Given a binary tree, each level $l$ of the tree consists of $2^l$ elements. When concatenating the continued fraction expansions of these elements and counting occurrences of a random block $d_1,\...
1
vote
1answer
45 views

I wanted to prove the claim “A graph is a tree if and only if it has one fewer edge than it has vertices.” Is this true or false, and why?

For this question I chose 4 as the answer however it was wrong. Can someone please explain the right answer This were the choices: Suppose I wanted to prove the claim "A graph is a tree if and only ...
0
votes
0answers
26 views

Prove that a BST for a limited set of contiguous elements [1, n] has at most n leaves

I define a Binary Search Tree as a tree in which the key in any node is larger or equal than the keys in all nodes in that node's left subtree and smaller than the keys in all nodes in that node's ...
0
votes
1answer
12 views

natural sub-class of trees in Sage

I want to calculate certain parameter for class of trees like path graphs, star graphs. I dont want to calculate it for all trees with n vertices as this wont help me in my problem. Basically I need a ...
8
votes
0answers
87 views

Frogs jumping on trees

The frog game on a graph: Default start of the game is placing one frog on each node (vertex). The goal is to move all the frogs to one single node. A single move consists of moving all $n$ frogs ...
2
votes
3answers
69 views

Why does a graph distance have to fulfill the four-point condition?

In Buneman's paper "A note on the metric properties of trees", he states that: "By checking the possible configuration of paths which can connect four points $x,y,z,t$ in a tree, it can be seen that ...
2
votes
1answer
72 views

lower bound for Kruskal's weak tree function

The wiki on Kruskal's tree theorum briefly mentions the weak tree function regarding unlabeled trees. It gives values of tree(1) = 2, tree(2) = 5 (trivial to prove) but then it gives tree(3) >= 262140....
0
votes
0answers
44 views

Cartesian Product as a tree

For any Cartesian product (at least for finite number of sets), I can associate it with a tree where the leaves are the sets and each node is the Cartesian product of node directly below it. For ...
5
votes
1answer
78 views

Number of labelled trees with exactly 3 leaves

I have seen some relevant questions here about that matter [1], [2] but I am getting a different result and I cannot understand if I am wrong. So the question is: Find the number of labelled trees ...
3
votes
1answer
84 views

Generating function for the number of unlabeled trees on $n$ vertices

According to OEIS sequence A000055, if $(T_n)$ denotes the sequence of number of trees with $n$ unlabeled vertices, then it has the generating function $$G(x)=1+A(x)-A^2(x)/2+A(x^2)/2=\sum_{n=0}^{\...
0
votes
0answers
16 views

What is the min/max number of leaves/non-leave nodes in B+ tree?

Let $n=100$ be the order of a B+ tree which is represents $10^4$ unique values (e.g. primary keys in a database). What is the minimum and maximum number of leaves and non-leave nodes in the tree? ...
1
vote
1answer
19 views

The number of Laplacian eigenvalues of a graph in interval [3,n].

There are several upper and lower bounds for $m_G[2,n]$ (the number of Laplacian eigenvalues of a graph $G$ with $n$ vertices in the interval $[2,n]$). I want to know whether there exists any bound ...
1
vote
2answers
52 views

Is a 'root' an intrinsic property of a tree

Is root an intrinsic property of a given tree?(Given a tree, can you uniquely determine the root?) Can't any vertex of a tree be chosen as a root? Aren't all trees rooted in that case?
1
vote
1answer
104 views

For each edge in a tree, counting paths passing through this edge

I have a tree and for its each edge, I want to know the numbers paths passing through this edge. For example: a tree with vertex-set = [1, 2, 3, 4, 5, 6] and edge-set = [(1,2), (2,3), (2,4), (4,5), (...
1
vote
1answer
21 views

If an orientation of a tree graph has no source vertices, must the in-degree of each vertex in said orientation be equal to one?

Given any polytree $T$ (any orientation of a tree graph) such that $\forall v\in V(T)(\text{indeg}(v)\neq 0)$ does this imply that $\forall v\in V(T)(\text{indeg}(v)=1)$? I'm pretty sure its true, but ...
0
votes
0answers
20 views

Find K Closest pairs in a spatial database (Without specific query object)

Input: • N points {P1, …. , Pn} - each point is from the same dimension t: Pi = {x_1, …., x_t} where k is between 18-30 . • Distance function – dist(Pi, Pj) - returns a number that is the distance ...
2
votes
0answers
137 views

When does the busy beaver function surpass TREE(n)? [closed]

Since TREE is a computable function the BB function grows faster than it, but TREE seems to grow much more quickly early on, so when does Busy Beaver surpass it?
0
votes
2answers
61 views

What type of tree is this?

The checkmarks I've drawn means that the branch ends or a node with the same number allready exists in the tree. I.e it means it reaches some cycle or ends the branching. I don't know if this is even ...
0
votes
0answers
36 views

Draw a specific graph with a branching.

I want to draw the following graph: it is a tree it can have up to four children nodes there should be no edges intersections The part with which I struggle is the 3. I am not sure how ...
2
votes
1answer
94 views

Minimum number of nodes present in binary tree with constraint $|P – Q| ≤ 2$

Question Consider a binary tree; define its height as $0$ if it consists of a single node, and $1$ plus the maximum height of its subtrees otherwise. For a generic node $u$ in the tree, let $P(u)$ ...
1
vote
2answers
111 views

Binary Tree Equation Describing Path

I have a perfect binary tree with an arbitrary depth. I have been trying to come up with an equation to describe how many times in a row a leaf node has moved the same direction. For example, the ...