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.

learn more… | top users | synonyms

0
votes
2answers
47 views

Finding an equation for a growth formula

Given a tree that has three nodes each level I want to find the formula that predicts the number of all nodes with a given tree height. I fitted the data into Numbers with an exponential function ...
2
votes
4answers
856 views

How many labeled trees exist on n vertices with exactly 3 vertices of degree 1?

My combinatorics class is covering spanning trees right now and one of the questions being asked is "What is the number of labeled trees on n vertices with exactly $3$ vertices of degree $1$?" I've ...
0
votes
0answers
100 views

max number of keys in a 2-3-4 tree

Let $M(L)$ be the largest number of keys (a $2$-node has $1$ key and two children, a $3$-node has $2$ keys and $3$ children, and a $4$-node has $3$ keys and $4$ children) in a $2-3-4$ tree that ...
2
votes
1answer
128 views

spanning trees of an edge transitive graph

Let $G$ be an edge transitive graph. Let $t(G)$ be the number f spanning trees on $G$. Show that each edge lies in exactly $\tfrac{(n-1)t(G)}{m}$ spanning trees. Where $|V(G)|=n$ and $|E(G)=m$. ...
2
votes
2answers
1k views

Can Prims and Kruskals algorithm yield different min spanning tree?

In this problem I am trying to find the min weight using the Prims and Kruskals and list the edges in the order they are chosen. For Prims I am getting order ...
0
votes
0answers
192 views

D ary tree node math

A d-ary tree is a rooted tree in which each node has at most d children (c) Suppose the tree has n nodes. What is the minimum the depth could possibly be, in terms of n and d? You can leave your ...
0
votes
1answer
60 views

Counting the number of trees on $[n]$

Let $T_{n}$ be the number of trees on $[n]$. Explain the identity below in terms of $T_{n}$ and prove it. $2(n-1)n^{n-2}=\sum_{k=1}^{n-1}\binom{n}{k}k^{k-1}(n-k)^{n-k-1}.$ So far I've got that ...
0
votes
1answer
25 views

Question Concerning Family of Trees

I have the following problem where I am asked to construct a family of trees (one for each $n$) that have exactly 2 leaves. I am having difficulty with this problem mainly because I cannot find a ...
1
vote
0answers
35 views

automorphism of a rooted tree

Nowadays i'm working with tree automorphisms. I couldn't find information about rooted tree automorphism concerning the root. Does an automorphism of a rooted tree fix the root or not? Logically it ...
3
votes
3answers
3k views

How to show that every connected graph has a spanning tree, working from the graph “down”

I am confused about how to approach this. It says: Show that every connected graph has a spanning tree. It's possible to find a proof that starts with the graph and works "down" towards the ...
1
vote
2answers
70 views

In a tree, is there always a sink where every longest path ends in?

Let $T$ be an undirected tree. Can we always find a leaf vertex $s$ such that every longest path of $T$ has its other endpoint in $s$? It's easy to see that every longest path passes through the ...
1
vote
2answers
97 views

Some equivalence relation from flipping binary trees

I know almost nothing in combinatorics, so this question might be very easy, or well-known. Fix a number $n$. We will consider rooted planar binary trees with $n$ leaves. We will distinguish between ...
0
votes
0answers
16 views

Measuring values at nodes of two independent but now connected trees

I am not sure if this the right forum for this question and I hope I am providing enough details on what I want to accomplish. I have an application that has multiple trees - Tree 1 - is categories/ ...
2
votes
1answer
76 views

Given an $n$ level tree with $b$ branches at each node, how many unique paths are there from the root to the leaves?

I have a tree where, at each node, it splits into $b$ branches for a total number of $n$ levels. I enumerate the paths from the root to the leaf nodes. For example, if $n = b = 2$ then I have the ...
1
vote
1answer
38 views

Connection Trees and Partition

In our lecture we just had a short excursion into the tree-world. But the professor mentioned some connection between Ramsey and König's Infinity Lemma (If $T$ is a tree of hight $\omega$ with all ...
3
votes
2answers
172 views

König's Infinity Lemma and Aronszajn Trees

I am working through the notes of my Set Theory lecture. There my professor wrote: 'Is there an uncountable $\kappa$ such that König's Infinity Lemma holds for $\kappa$? There are models where ...
1
vote
1answer
493 views

Prove that in every tree, any two paths with maximum length have a node in common.

Prove that in every tree, any two paths with maximum length have a node in common. This is not true if we consider two maximal (i.e. non-extendable) paths. What does this even mean?
3
votes
1answer
173 views

$\kappa$-Suslin (Aronszajn, Kurepa) subtree of the complete binary tree, $2^{\lt \kappa}$

This is from chapter 2 of Kunen, Set theory: an introduction to independence proofs. Given $\kappa$ a regular cardinal, and the existence of a $\kappa$-Suslin (Aronszajn, Kurepa) tree, show that ...
0
votes
4answers
3k views

How many edges does an undirected tree with n nodes have?

The following options: a) $n$ b) $n + 1$ c) $n - 1$ d) $n(n - 1)$ e) $(n + 1)(n - 1)$ f) $\frac{n(n - 1)}2$ g) $\lceil \log_2n \rceil$
1
vote
0answers
116 views

Generating Function for edge-rooted labelled trees

Let $T_v(z)$ be the (exponential) generating function for vertex-rooted (non-plane) trees. Im trying to construct the generating function $T_e(z)$ for edge-rooted trees from this. I know the ...
0
votes
1answer
422 views

How many vertices does a complete binary tree of height 1 have?

How many vertices does a complete binary tree of height 1 has? Height 2? Height d? Any hints on how to start to tackle these set of questions?
1
vote
0answers
97 views

Binary Tree and Geometric Distribution

I have the following algorithm for "constructing" a binary tree: A probability $p_g$ for elongation, i.e. adding an edge A probability $p_b$ for branching, i.e. adding to a node two "child" edges ...
1
vote
2answers
143 views

Draw Graph from distance to other nodes

I have a matrix that shows the distance from a node to another node: A B C D E A 0 2 4 3 1 B 2 0 2 1 3 C 4 2 0 2 1 D 3 1 2 0 2 E 1 3 1 2 0 To clearify: The 2 ...
1
vote
0answers
176 views

Binary Tree and Overhead fraction Caluculation

Find the overhead fraction (the ratio of data space over total space) for each of the following binary tree implementations on n nodes: 2) Only leaf nodes store data; internal nodes store two child ...
0
votes
3answers
729 views

What is the main difference between a free tree and a rooted tree?

In graph theory what is the difference between a rooted tree and a free tree ? What is normally meant when just the plain "tree" is used ?
0
votes
1answer
80 views

Unique solution for a given pre- and post-order of a rooted tree

Decide the picture of a rooted tree with pre-order $a,b,c,d,e,f,g,h$ and post-order $d,e,f,g,h,c,b,a$. Show that there always is a unique solution for a given pre- and post-order of a rooted tree. My ...
3
votes
2answers
76 views

Number of undirected trees

Given n numbered vertices I want to know the number of different trees that can be created with them. I know that cayley's theorem says it's $n^{n-2}$, but why can't it also be: ...
2
votes
1answer
606 views

Number of distinct path in a graph with $n$ vertices

Let $T = (V , E)$ be a tree with $|V | = n\geqslant 2$. How many distinct paths are there (as sub graphs) in $T$? I already have the answer to this question as $(n/2)$. The problem that I'm having is ...
2
votes
1answer
49 views

Is there a tree $T$ such that $\text{diam}(T) \geq k$, where $k$ is the number of vertices with degree less than 3?

Let $T$ be an undirected tree, let $d$ be the diameter of $T$, and let $s$ be the number of vertices in $T$ with degree less than 3. Recall the diameter of a graph is the length of the longest ...
0
votes
1answer
50 views

Getting a values from nodes

The goal: get horizontal values of vertical level N where level 1 is pinacle node (1). Example: level 4 as input should produce: | 1 | 3 | 3 | 1 | Note: the sum ...
2
votes
3answers
2k views

Minimum Number of Nodes for Full Binary Tree with Level $\lambda$

If the level ($\lambda$) of a full binary tree at zero is just a root node, than I know that I can get the maximum possible number of nodes (N) for a full binary tree using the following: N = ...
0
votes
1answer
56 views

Correspondence between fractal sets and trees

In Hillel Furstenberg's series lectures on ergodic theory in fractal geometry, he mentioned his search on finding a one-to-one correspondence between fractal sets and trees, however, I couldn't not ...
1
vote
1answer
242 views

No of labeled trees with n nodes such that certain pairs of labels are not adjacent.

What is the number of trees possible with $n$ nodes where the $i$th and $(i+1)$th node are not adjacent to each other for $i \in \left[0,n-1\right)$ and $$i/2 = (i+1)/2.$$ (integer division) (nodes ...
6
votes
4answers
190 views

Recursive Sequence Tree Problem (Original Research in the Field of Comp. Sci)

This question appears also in http://cstheory.stackexchange.com/questions/17953/recursive-sequence-tree-problem-original-research-in-the-field-of-comp-sci. I was told that cross-posting in this ...
0
votes
1answer
145 views

Need help performing a tree method to test for satisfiability

For those who commented on my previous questions, sorry for the lack of information and explanation. Clearly I did not do a good job of explaining myself so I deleted the question and hope this one ...
6
votes
3answers
380 views

$n$-ary trees with $k$-internal nodes - Catalan numbers

It is known that the Catalan numbers count the number of binary trees with $k$-internal nodes. I was thinking of how to count ternary trees or in general $n$-ary trees with $k$ internal nodes and got ...
0
votes
1answer
90 views

Prove that there are two end points in a tree with a common neighbor

Let $T=(V,E)$ be a tree with at least $3$ vertices. Assume that every vertex has either degree $1$ or a degree of at least $3$ (so there are no vertices with degree $2$). Prove that there are two end ...
1
vote
2answers
523 views

Gallery of unlabelled trees with n vertices

Can anyone point me to a gallery (printed or online) of unlabelled trees, sorted according to their order (i.e., number of vertices)? That is, for each order n in oeis.org/A000055 (up to maybe n=11 ...
1
vote
2answers
93 views

spanning trees of graphs

Assume we have a simple connected graph G, how would start a prove of the following statement? For any edge of G, there is a spanning tree of G that contans it. I have decided that this is a true ...
0
votes
1answer
55 views

Minimal Red-Black tree with depth 3

I'd like to ask what is minimal RBT with black depth 3. Is this following RBT ? Values are not important. And that tree can't have depth 2 or 1.
0
votes
2answers
92 views

Prove there is a tree with $n$ vertices having degrees $d_1, d_2…d_n$

For $n ≥ 2$ suppose $d_1, d_2,....d_n$ are positive integers with sum $2n - 2$. Prove there is a tree with n vertices having degrees $d_1, d_2....d_n$. I'm at a loss on this one. I'm sure it's pretty ...
3
votes
2answers
171 views

In any tree, what is the maximum distance between a vertex of high degree and a vertex of low degree?

In any undirected tree $T$, what is the maximum distance from any vertex $v$ with $\text{deg}(v) \geq 3$ to the closest (in a shortest path sense) vertex $y$ with $\text{deg}(y) \leq 2$? That is, $y$ ...
2
votes
2answers
45 views

Embedding of Tree

Q. Proof for every Tree can be embedded into the plane. Conditions. We cannot use Euler Formula for Planar Graphs. We can use definition of tree, $V-E=1$, no-cycles, every edge is critical, there ...
1
vote
3answers
78 views

Parent and childs of a full d-node tree

i have a full d-node tree (by that mean a tree that each node has exactly d nodes as kids). My question is, if i get a random k node of this tree, in which position do i get his kids and his parent? ...
0
votes
1answer
157 views

How many arguments are there in a Merkle tree?

I want to calculate the amount of elements in a Merkle tree given the number of leaf elements. The number of elements at a given level n is equal to number of elements at a level n+1, divided by two ...
1
vote
2answers
132 views

Trees with vertex set

I am having hard time understanding and solving the following question: There are exactly three trees with vertex set {1,2,3}. Note that all these trees are paths; the only difference is which ...
4
votes
1answer
242 views

How many vertices of degree 3 or more can have a tree have at most?

It is known that a tree $T=(V,E)$ has at least $\Delta$ leaves, where $\Delta$ is the maximum degree of $T$. But how many vertices of specific degree at least $k$ can a tree have at most? I'm ...
0
votes
2answers
110 views

Question: Graph Theory and Trees

In a group of 2n schoolchildren each one has at least n friends. On an outing, the teacher tells them to hold hands in pairs. Show that this can be done with each child holding a friend’s hand, and ...
0
votes
2answers
91 views

how to store a math problem in a binary tree?

If I have the following problem: $\ 12 - (2 +3) - (3 *4)/ (5 -7) $ How would it be stored in a binary tree? following the order of operations, would you start with $\ (3*4) $ at the top or $\ 12 $ ...
14
votes
2answers
293 views

Is there a “tree-like” proof of compactness theorem in the case of uncountably many variables?

I like proofs using trees and König's lemma, since they are very visual. One of the applications of König's lemma you can show to students is proving compactness theorem for propositional calculus, ...