Skip to main content

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
-3 votes
0 answers
36 views

Proof the number of nodes in a binary tree +1 is equal to the double of the leafs [closed]

This is a class problem from the book https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/resources/mit6_042js15_textbook/ Page 191. It asks to prove that for the recursive ...
Jery Lazman's user avatar
4 votes
1 answer
55 views

Every binary tree with $n$ leaves has a subtree with $k$ leaves where $\frac{n}{3} \leq k \leq \frac{2n}{3}$.

I want to show the following: Every binary tree with $n$ leaves has a subtree with $k$ leaves where $\frac{n}{3} \leq k \leq \frac{2n}{3}$. My approach: First thing I did was to draw a binary tree and ...
NTc5's user avatar
  • 543
2 votes
2 answers
159 views

Number of binary trees of given size, except some nodes are unary

The question is about number of trees, where all internal nodes (total number denoted as $n$) have degree 2 except of some ($k$) nodes with degree 1. Let's denote the total number of such trees as $F(...
zaa's user avatar
  • 740
1 vote
1 answer
41 views

Exercise regarding complete binary trees

Suppose $T$ is a complete binary tree with $n$ leaves Let $e$ denote the sum of the lengths of the leaves, $i$ denote the sum of lengths of the internal nodes. Prove that $e=i+2(n-1)$. My attempt: ...
NTc5's user avatar
  • 543
1 vote
0 answers
13 views

If $(q-1)|(n-1)$ then there exists a complete $q$-tree with exactly $n$ leaves.

I have been trying to figure out how to show the following statement: Let $n,q \in \mathbb{N}$ with $q \geq 2$. If $(q-1)|(n-1)$ then there exists a complete $q$-tree with exactly $n$ leaves. I have ...
NTc5's user avatar
  • 543
1 vote
1 answer
102 views

What is an ordered tree?

(Notice: The ordered tree here is irrelevant to any sorting utility in programming but is a term in graph theory or combinatorics.) The question comes in three-fold: the wiki says an ordered tree is ...
Xavier Z's user avatar
  • 133
1 vote
0 answers
49 views

Counting k-ary unlabeled unordered trees with n nodes

I wish to know the asymptotic estimate of counting the trees satisfying the following conditions: a total of n vertices; each vertex has at most ...
Xavier Z's user avatar
  • 133
2 votes
0 answers
33 views

Tiling of a tree to show that a group acting freely on a tree is free

Let me start giving some context: Let $G$ be a group acting freely on a tree $T$. Let $T'$ be the barycentric subdivision of $T$ (that is, the graph obtained by placing a new vertex at the center of ...
ABC's user avatar
  • 904
1 vote
0 answers
58 views

base-independent representation of numbers as a ternary-tree

There is the concept of a super-prime OEIS A006450 which is a prime whose index/subscript is another prime number. E.g 11 is the 5th prime number and 5 is prime. 31 is the 11th prime number. [OEIS ...
swizzmilk's user avatar
0 votes
0 answers
30 views

Spanning Trees with 1/2 the edges in a Eulerian Graph

I was attempting the following problem: Let $G$ be a connected simple graph. (a) If $G$ is eulerian with an even number of vertices, then it has a spanning subgraph $G'$ such that every node $i$ has ...
Roh4n's user avatar
  • 11
0 votes
0 answers
34 views

Group which acts properly on a tree is closed in the automorphisms group

Let $G$ be a locally compact group which acts properly on a locally finite (simplicial) tree $T$ (i.e., for each compact subset $K \subseteq T$ it holds that the set $G_K=\{g \in G| gK \cap K \neq \...
Bargabbiati's user avatar
  • 2,271
1 vote
0 answers
43 views

Decomposing a graph into the minimum number of edge-disjoint trees

Given a graph $G = (V,E)$, what is the minimum number of edge-disjoint trees needed to cover $G$? How can we find such a decomposition? I've seen similar problems studied before (such as the ...
Catalyxx's user avatar
0 votes
1 answer
38 views

In a tree where each node value represents the number of its children, what is the parent node of the i-th child? the nodes are named in level order

A tree structure represents a hypothetical chain of processes as follows: Every process has child processes The number of child processes is equal to the process number i.e., process number 3 has 3 ...
Farida Maheeb's user avatar
-1 votes
0 answers
29 views

The connected game - Does player A always have a winning strategy?

I'm stuck on this game question and wondering if anyone here may have a better way of going about this. These are the games parameters: There are n dots on a plane (flat surface). There are two ...
user avatar
0 votes
0 answers
18 views

Has anyone tried “building” any convex uniform polyhedra from combinatorial tree graphs?

CONTEXT Convex uniform polyhedra, like tree graphs, can be described with vertices and unitary edges. QUESTION 1 Has anyone tried “building” any convex uniform polyhedra from combinatorial tree graphs ...
olivierlambert's user avatar
0 votes
1 answer
71 views

Approximation of $\mathrm{TREES}(3)$ [closed]

Define $\mathrm{TREES}(n)$ as count of all valid trees in definition of $\mathrm{TREE(n)}$, not necessarily a longest one. E.g. $\mathrm{TREES}(2) = |{1,2,1\ 2,2\ 1,1\ 22\ 2,2\ 11\ 1,1\ 22,2\ 11}| = 8$...
l4m2's user avatar
  • 229
0 votes
0 answers
19 views

Combinatorics: How to use the tree dissymmetry theorem to find singularities?

Denote by $T(z)$ the exponential generating function of the class $\mathcal{T}$ of labelled (unrooted) trees in which all vertices have degree $1$ or $3$. Use the tree dissymmetry theorem (see below) ...
3nondatur's user avatar
  • 4,212
0 votes
0 answers
20 views

Finding any spanning tree that covers a subgraph of a directed graph

My work (programmer) has a business use case that basically boils down to the following graph theory problem: Given a directed graph $F$ and a subset of vertices / subgraph $G = v_1, v_2, ... , v_k$ ...
Pranav Rudra's user avatar
0 votes
1 answer
39 views

Numner of Graph functions

Let, T(V, E) be an undirected tree with n vertices, where V={$v_1,v_2,...,v_n$}. Let d(i)represent the degree of verticex $v_i$. Let f be a function from V to {1,2,...,n}. Compute the number of such ...
Arnab Seal's user avatar
0 votes
1 answer
27 views

Lengths of binary Huffman codes for uniform distribution

A binary Huffman code for a pmf $(p_1,\dots,p_m)$ is constructed by starting with all $p_i$ as leaves and iteratively constructing a tree by merging the two nodes of lowest probability. Edges are then ...
hegash's user avatar
  • 197
2 votes
0 answers
41 views

Understanding the girth of trees

Reading about graph girth, I found out that girth of trees are defined to be infinite. According to the University of Chicago lecture: Definition 2.6. The girth of a graph is the length of its ...
Peyman's user avatar
  • 741
0 votes
0 answers
9 views

Explicit formula for $F(a,i)=p_iF(a-1,i-1)+(1-p_i)F(a,i-1)$

So, I have this node tree that I have constructed in this way: I start at 0 at the top and add 1 if I go left and do nothing if I go right. I go left with a probability $p_i$ for level $i$ in the tree ...
Vebjorn's user avatar
  • 183
1 vote
1 answer
38 views

Problem in proving that every tree has at most one perfect matching.

I would like to prove that every tree has at most one perfect matching. I approached it in the same way as described here: Perfect matching in a tree. However, I don't understand the concluding ...
user avatar
0 votes
1 answer
37 views

counting Eulerian circuits on complete directed graph

I have a complete directed graph $G$ (including self-loops). How can I count the number of Eulerian circuits on $G$? For example, in the simple case of $n=2$, there are clearly 4 Eulerian circuits. ...
lrussell's user avatar
0 votes
1 answer
40 views

Algorithms by Dasgupta-Papadimitriou-Vazirani Prologue confusion

We will see in Chapter 1 that the addition of two n-bit numbers takes time roughly proportional to n; this is not too hard to understand if you think back to the gradeschool procedure for addition, ...
Bob Marley's user avatar
4 votes
1 answer
81 views

Induction does not preserve ordering between cardinality of sets?

Consider building a binary tree and consider it as a collection of points and edges. Here is one with five levels, numbered level $1$ at the top with $1$ node to level $5$ at the bottom with $16$ ...
jdods's user avatar
  • 6,340
0 votes
0 answers
6 views

Possible root values of AVL tree

I have a question: given that an AVL tree holds numbers 1, 2, 3, ..., 1000, what are the smallest and largest possible values of the root? I have a feeling it is 500 and 501, but I don't know how to ...
HBH's user avatar
  • 63
3 votes
0 answers
52 views

Permutational wreath product and rooted trees

I am currently working with wreath products in the context of automorphisms of rooted trees, and I have troubles understanding the notation. Given a finite alphabet $X$, we can construct a rooted tree ...
Alice in Wonderland's user avatar
0 votes
1 answer
17 views

Constructing a tree starting from some initial vertex

Is it possible to always construct any required tree starting initially with any of the vertices? I had the following algorithm in mind: Take the initial vertex, scan all its neighbours, join them. ...
Anuj Bhadbhade's user avatar
0 votes
0 answers
43 views

Why isn't TREE(2) = 5?

I'm trying to comprehend $\operatorname{TREE (3)}$ but i can't even comprehend $\operatorname{TREE(2)}$ So there are $2$ rules: The $n$-th tree should contain at most $n$ nodes. All the previous $(n -...
loomysh's user avatar
2 votes
1 answer
63 views

How to determine number of isomorphic trees, and how to draw them?

The question is "How many nonisomorphic spanning trees does each of these simple graphs have? Draw them. a) K3 b) K4 c) K5" I found that there is only one nonisomorphic tree for K3, but I ...
MotherHorse's user avatar
1 vote
1 answer
38 views

Maximum weight edge in a cycle and Minimum Spanning Tree

Consider G a simple, connected, undirected graph. I know there exists a property called cut property, which states that for a given cut $(S, G-S)$, if an edge $e$ crossing that cut from $S$ to $G-S$ ...
piero's user avatar
  • 450
1 vote
1 answer
67 views

Distinct and valid parent arrays of a tree

A tree has 10 nodes, numbered from 1 to 10, and its parent array v = {0, 1, 1, 2, 2, 3, 3, x, y, z}. How many distinct and valid parent arrays can be formed by giving values to x, y and z? My (wrong?) ...
Leon's user avatar
  • 43
0 votes
0 answers
9 views

Calculate maximum degree of a tree given $x$ nodes and every node in tree has at max $y$ children.

Given a tree and the following data: The tree consists out of $x$ nodes Every node in the tree can have at maximum $y$ children. How can I calculate the degree of a tree? So the maximum number of ...
WG-'s user avatar
  • 932
0 votes
0 answers
34 views

Exponential Generating Function Trees with a certain number of children

Exponential Generating Function for certain trees I read the response to the SE post above and have a question. Let $T$ be the species of rooted unordered trees with 2 children (binary trees), then $T ...
Jonathan McDonald's user avatar
1 vote
0 answers
22 views

Alternative definition of inf-embeddable in TREE(n)

I am trying to come up with an explanation of TREE(n) for kids, and I need to come up with an explanation for what it means when a tree "contains" another, or "inf-embeddable" as ...
Bara Like's user avatar
0 votes
0 answers
15 views

Proof about properties of a complete binary tree

Let $T$ be a complete binary tree with $N$ nodes and suppose $N$ binary representation is $(b_{n}b_{n-1}...b_{0})$ where $n = \lfloor lg_{2} N \rfloor$. Let $T_{1}$ be the left subtree and $T_{2}$ be ...
Victor Feitosa's user avatar
2 votes
1 answer
60 views

Spanning trees and (induced) fundamental cycles

I had an idea about certain spanning trees of graphs and was wondering if any of you knows something about this. Given a connected graph $G$, does there always exist a spanning tree such that the its ...
Jonas's user avatar
  • 123
0 votes
0 answers
32 views

What is this kind of undirected metric tree called?

Definition of object of interest Suppose you have an undirected metric tree $T=(V,E,w)$ where $V$ is the set of vertices, $E$ is the set of edges and the function $w:E\to \mathbb{R}_{\geq 0}$ ...
Omri Shavit's user avatar
2 votes
0 answers
22 views

Necessary and sufficient condition for a finite rooted tree to be a redundancy tree

Let $S$ be a consistent finite set of axioms in some first-order language $L$. Recall the definition of an axiom $A$ in $S$ being redundant: $S$ - $\{A\}$ can prove $A$. Now, it can happen that even ...
user107952's user avatar
  • 20.9k
1 vote
0 answers
36 views

Number of spanning trees that contain a given edge and spanning trees that contain subtrees

I am stuyding my combinatorics syllabus and came across two claims, that are said to be generalisations of the Matrix Tree Theorem: G = (V,E) is a complete graph without loops. U is a subset of V. The ...
Mai's user avatar
  • 39
0 votes
0 answers
27 views

MST vs SPT for a 2 vertex graph

I have a graph with 2 vertices. They each have a directed weighed edge towards the other vertex. One of the weights is higher than the other. Would this graph count as a graph that has a different ...
cyphic's user avatar
  • 1
3 votes
1 answer
78 views

Prove that max number of edge-disjoint cycles in a graph is at least $(|E(G)| - |V(G)|)/2\lfloor \log_2(n+1)\rfloor$

I want to prove that for a graph with $n$ vertices, the size of the largest set of cycles that don't share edges with each other is at least $\frac{|E(G)| - |V(G)|}{2\lfloor \log_2(n+1)\rfloor}$. It ...
haha's user avatar
  • 183
2 votes
0 answers
58 views

Show that every finite and undirected tree has either one or two adjacent centres. [closed]

Is this proof vigorous enough? (Feel free to provide any suggestions for improvement as well). (A centre of a connected graph $G$ is a vertex $v$ with the property that the maximum of the distances ...
calphas's user avatar
  • 21
0 votes
0 answers
38 views

Maximum edge cover by paths defined by 3 vertices in a tree

Let's consider a tree $T$. $P(u, v)$ represents a path between $u$ and $v$ (set of edges). My task is to find $a$, $b$ and $c$ such that the set: $$\left\{ e \in E: e \in P(a, b) \cup P(a,c) \cup P(b,...
Umbra's user avatar
  • 55
1 vote
1 answer
95 views

Free and cocompact subgroup of the group of automorphisms on a tree

Let $T$ be a $k$-regular tree for some $k>2$ and let $G=\text{Aut}(T)$ the group of automorphisms on the tree. I need to find a closed subgroup $H$ of $G$, so $H$ is a free group (and therefore ...
Z17Math's user avatar
  • 235
1 vote
1 answer
48 views

How does making a spanning tree solution "strongly feasible" for the Network Simplex method assist in cycling prevention?

Question: How does making a spanning tree solution "strongly feasible" for the Network Simplex method assist in cycling prevention? To start, I was reading An Implementation of Network ...
Miss Mae's user avatar
  • 1,839
5 votes
1 answer
117 views

Is $\text{BRANCH}(n)$ finite for $n > 2$?

Is $\text{BRANCH}(n)$ finite for $n > 2$? Define $\text{BRANCH}(n)$ as the maximum length of a string that is composed of at most $n$ unique characters AND meets the following condition: Define a ...
Yash Jain's user avatar
  • 145
2 votes
1 answer
47 views

How many non-isomorphic, non-labelled, forests are there (asymptotically) on $n$ vertices?

Is there any formula known? There is the following asympotic formula for unlabelled trees: $$t(n) \sim C \alpha^n n^{-\frac{5}{2}}$$ With $t(n)$ the number of unlabelled non-isomorphic trees on $n$ ...
Wannes De Maeyer's user avatar
2 votes
1 answer
56 views

Moon's Proof of Matrix-Tree Theorem

I'm reading the following proof of the matrix-tree theorem: https://www.sciencedirect.com/science/article/pii/0012365X9200059Z in particular, his Theorem 3.1. I was not able to validate the last part: ...
taichi nekonoki's user avatar

1
2 3 4 5
41