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

2,043 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
• 543
159 views

• 2,271
1 vote
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 ...
• 31
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 ...
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 ...
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 ...
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$...
• 229
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) ...
• 4,212
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$ ...
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 ...
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 ...
• 197
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 ...
• 741
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 ...
• 183
1 vote
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 ...
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. ...
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, ...
• 669
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$ ...
• 6,340
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 ...
• 63
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 ...
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. ...
43 views

1 vote
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 ...
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 ...
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 ...
• 123
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}$ ...
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 ...
• 20.9k
1 vote
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 ...
• 39
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 ...
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 ...
• 183
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 ...
• 21