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
1answer
1k views

M-ary tree problem

A full $m$-ary tree $T$ has 81 leaves and height 4 1) Give the upper and lower bounds for $m$ 2) What is $m$ if T is also balanced? [with $m^h=l$ for maximum leaf in a m-ary tree $m^4=81$ then m=3 ...
0
votes
2answers
251 views

Tree problem about preorder notation

Show that an ordered rooted tree is uniquely determined when a list of vertices generated by a preorder traversal of the tree and the number of children of each vertex are specified.
2
votes
0answers
74 views

Groups acting on (regular) trees with finite quotient

Let $T$ be a regular tree, and suppose that $G \leq \mathrm{Aut}(T)$ has finite quotient graph, $T / G$. Is it true (in general) that $G$ will have trivial centralizer in the full automorphism group? ...
1
vote
0answers
84 views

How can I prove this property of a $d$-ary tree?

I have the following homework (algorithms lecture): Every $d$-ary tree $G=(V,E)$ contains a vertex $v$ such that the size of the subtree with root $v$ is at least $\frac{1}{d+1} \vert V \vert$ and at ...
3
votes
1answer
216 views

Cubic (3-regular) graph spanning tree

Considering loop free cubic graphs (graphs where every node has 3 neighboring nodes): Is is possible to construct a spanning tree that only has nodes with 3 neighbors in the spanning tree or 1 ...
0
votes
1answer
523 views

Help in understanding search of Vantage-Point tree

This is my reference: http://stevehanov.ca/blog/index.php?id=130 A vantage-point tree is a way of organizing a set of points so that finding the n-nearest neighbors is as efficient as possible. It ...
1
vote
1answer
37 views

If $G$ is a tree and $\forall v_1, v_2 : dist(v_1, v_2)$ is even, where $v_1, v_2-$ are leaves $\Rightarrow \exists!$ a maximal independent set.

If $G$ is a tree and $\forall v_1, v_2 : dist(v_1, v_2)$ is even, where $v_1, v_2-$ are leaves of the tree $\Rightarrow \exists!$ a maximal independent set. Give some clue please! Thanks anyway!
2
votes
4answers
4k 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
84 views

Constructing a tree from disjoint graphs

I will preface my question with the definition of a simple tree that applies to my question: -"A simple tree is an undirected and connected graph with no cycles."- I am having difficulty coming up ...
1
vote
1answer
239 views

Prove equivalence of conditions for a tree

Let $G=(V,E)$ denote a nonempty graph. Show that the following conditions are all equivalent. $G$ is a tree. Any two vertices in $G$ can be connected by a unique simple path. $G$ is ...
1
vote
3answers
1k 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
86 views

Natural order of rational trees?

What would be a natural order of rational trees? Rational trees arise naturally from free algebras if we view a term as a finite tree. For example the term f(a,g(b,c)) could be viewed as the ...
5
votes
1answer
719 views

Every automorphism of a tree with an odd number of vertices has a fixed point

If $T$ is a tree, and $T$ has an odd number of vertices, then $\forall f$, where $f$ is automorphism $\Rightarrow \exists$ fixed point (vertex). What it means: Formally, an automorphism of a tree $T$ ...
0
votes
1answer
676 views

How to make a parse tree for the following propositional logic formula?

I have a formula $\neg (( q \rightarrow \neg q) \vee p \vee ( \neg q \rightarrow ( r \wedge p)))$. As it contains 3 subformulas between the $\vee$'s, how can I put it into a parse tree. Would it be ...
0
votes
2answers
601 views

Proof for Full Binary Tree Using Handshaking Lemma?

I asked a question a few days ago and figured out the proof for this theorem using induction. ...
0
votes
1answer
711 views

Proving terminal vertices and total vertices of a full binary tree?

I am trying to make a proof by induction of the following theorem. ...
0
votes
1answer
225 views

A binary tree in 3-ary tree

We have an infinite $3$-ary tree, with root $R$. In coloring $C(p)$ each edge is black with probability $p$ and white with probability $1 - p$, and edges are independent. Show that there is a ...
3
votes
2answers
235 views

Why for number of leaves in a tree (all types of trees) is it true

I have to prove the following claim, given the tree $T=(V,E)$, $|V|\geq3$: $$|V_1| \leq \frac { |V| \times (\Delta (V) - 2) + 2 }{ \Delta (V) - 1 } $$ where $|V_1| - $ number of leaves in a tree, and ...
1
vote
0answers
54 views

How to formulate a best-search algorithm limited by a count of nodes visited?

The problem I'm doing a search by computer program. Each node takes about 5 minutes of wall time to get a result so I'm looking to carefully choose the nodes to inspect so as to find the best result ...
1
vote
2answers
705 views

graph theory and forests

We were given an this question in my class: Prove that a forest with n vertices and m components has n-m edges using induction on m. Induction is not my strongest point and I was wondering if anyone ...
2
votes
1answer
177 views

Probability of passing through 3 specific nodes along a binomial tree

Consider a re-combining binomial tree with probability of up = $p$ and probability of down = $(1-p)$. Let $n$ be the number of time steps in the binomial tree (the $x$-axis is time, and each column of ...
2
votes
1answer
92 views

About finiteness of trees

I am reading a book of Michael Sipser "Introduction to the theory of computation", and there is a theorem, which he gives without a proof: "If every node of a tree has only finitely many children and ...
3
votes
2answers
124 views

Bounds on how far away most leaves are from the average height of a binary tree

I'm wondering if anyone can help me prove (or disprove) this statement? Say there is a rooted full binary tree (each non-leaf node has exactly two children) with a height of $h$, an average height ...
0
votes
1answer
500 views

Proving by induction

I'm having a problem relating to proving by induction that the Preorder(T) and Postorder(T) algorithms both print out all the nodes in the tree without repetition. I'm not quite sure where to start.. ...
0
votes
2answers
614 views

Explanation of why the height of a binary tree $\theta({lg}(n))$.

From Heap Sort chapter of Introduction to algorithms : Since a heap of n elements is based on a complete binary tree , its height is $\theta({lg}(n))$. I know this is correct but how can this ...
4
votes
1answer
286 views

characteristic polynomial of the adjacency matrix of a tree

I have read that if $A$ is the adjacency matrix of a tree $T$, then we have that $$\det(\lambda I - A) = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k N_k(T) \lambda^{n-2k} $$ where $N_k(T)$ is the number ...
0
votes
1answer
80 views

Number of leaves in a tree that represents a kind of permutations

Consider the following rooted tree, each of whose vertices (except for the root) is labeled with an integer $\in\{1,\dots,n\}$: let $s(v)$ be the sequence consists of the labels on the path from the ...
3
votes
0answers
66 views

Recurrence relation induction [duplicate]

Possible Duplicate: Solving the recurrence $t(n)=(t(n-1))^2 + 1$ Show that the number of binary trees of height less than or equal to $n$ is given by the recurrence \begin{align*} ...
1
vote
1answer
3k views

Number of Trees with n Nodes

I am struggling with a question that asks the number of trees that exist with x nodes and max level z. During my research I found that the number of binary trees with x nodes can be obtained by ...
0
votes
0answers
558 views

Depth-first spanning tree?

I am going to identify tree edges and back edges in an undirected graph. The graph consists of $5$ nodes, the edges between these nodes are as shown below: Suppose starting with $v_1$, after a ...
4
votes
3answers
168 views

A “correct” hierarchical scoring scheme?

I have a situation where we are given a set of objects each with a numeric score stating it's importance. Let's call them Level 1 (or L1) objects. There is another set of objects that are similarly ...
10
votes
2answers
883 views

“Ballot numbers” sum up to Catalan numbers

Summing certain numbers and comparing the results with OEIS, I found that $ \sum_{k=1}^n \frac{k^2}{n} \binom{2n-k-1}{n-1} = C_{n+1} - C_{n}, $ where $C_n$ denotes the $n^{\textrm{th}}$ Catalan ...
0
votes
1answer
100 views

How can the jth level of a binary tree with n nodes has problems of size $({\frac{n}{2}})^j$?

I read from a book that the jth level (starting from j=0 or the root) of a binary tree with n nodes divides a problem into $2^j$ subproblems, each of size $\frac{n}{2^j}$. I understand where $2^j$ ...
2
votes
1answer
155 views

Finite Rooted Binary Trees

I am new to learning about finite rooted binary trees. This lemma below is from John Meiers book: Groups, Graphs and Trees. There is no aval proof in the book. I was just wondering is I could catch a ...
4
votes
3answers
474 views

Counting $k$-ary labelled trees

The (full) binary counting tree problems gives the number of binary trees can be formed using $N$ nodes $T(n)= C_n$, where $C_i$ are the Catalan numbers. The recursion form is $T_n = ...
3
votes
5answers
24k views

The maximum number of nodes in a binary tree of depth $k$ is $2^{k}-1$, $k \geq1$.

I am confused with this statement The maximum number of nodes in a binary tree of depth $k$ is $2^k-1$, $k \geq1$. How come this is true. Lets say I have the following tree ...
0
votes
2answers
2k views

About balanced and complete binary tree

I found this and I just couldn't verify it. How come it is true? The maximum number of nodes that a balanced binary tree with depth $d$ is a complete binary tree with $2^d-1$ nodes. Let say I have ...
2
votes
1answer
664 views

Oriented trees and ordered trees

I have this confusion regarding ordered and oriented trees. I know they are both rooted and in ordered trees, the order is important. So lets say I have four nodes 1,2,3,4 then it is given that the ...
0
votes
1answer
346 views

Graph Theory - Spanning Trees

Consider a graph $G$ composed of two cycles which share an edge. $C_x$ is the cycle of length $x$ and $C_y$ is the cycle length $y$, for $x,y \ge 3$. (for example, if $x = 6$ and $y = 5$, then $C_x$ ...
2
votes
1answer
328 views

Evaluating 'combinatorial' sum

Help me please to calculate the following sum. I have seen such kind of formulas in the papers related to combinatorics, specifically 'trees'. I am curious how to calculate or approximate this sum: ...
1
vote
1answer
172 views

Existence of a spanning tree with certain properties

Let $\Gamma$ be a finite, connected graph (multiple edges between two vertices are allowed). Fix a vertex $u_0\in V\Gamma$. Does there exist a maximal subtree (i.e., a spanning tree) $T\subset\Gamma$ ...
4
votes
1answer
234 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 ...
4
votes
3answers
5k 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 ...
2
votes
1answer
301 views

Proof involving a minimum weight spanning tree.

Please help with the following homework problem: Let G be an undirected graph, $v: E\to R$ and $w: E\to R$ be two weight functions on the edges of $G$. Let $z: E\to R$ be defined as the sum of ...
2
votes
3answers
607 views

Applications of the number of spanning trees in graphs

Let $G$ be a simple graph and denote by $\tau(G)$ the number of spanning trees of $G$. There are many results related to $\tau(G)$ for certain types of graphs. For example one of the prettiest (to ...
1
vote
0answers
209 views

A tree that does not satisfy: If $v$ and $w$ are vertices in $T$, there is a unique path from $v$ to $w$?

It is a strange question on a book. Give an example of a tree $T$ that does not satisfy the following property: If $v$ and $w$ are vertices in $T$, there is a unique path from $v$ to $w$. I ...
0
votes
2answers
123 views

Narrowing a Stern-Brocot tree

Say I only wanted to enumerate the rational numbers between 0 and $a$. Is there a way to "narrow" a Stern-Brocot tree to provide this? I tried keeping my left bound at "$\frac{0}{1}$" and setting my ...
1
vote
0answers
57 views

Keeping consistency in subjective ranking

I'm doing some work on a computer program that aids in ranking items which don't have a way to objectively compare to each other. As it is now, it takes each item and pairs it up with each other ...
1
vote
1answer
68 views

Looking to generalize a binomial tree with some constraints.

I've got a set of sample data and I'm looking to see if it's possible to generalize a binomial formula to give a closed form solution to this. If not, would it be possible to write a program to do ...
1
vote
3answers
1k views

Graph with cycles proof questions

Two questions I'm stuck with: If C is a cycle, and e is an edge connecting two nonadjacent nodes of C, then we call e a chord of C. Prove that if every node of a graph G has degree at least 3, then ...