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

1
vote
1answer
312 views

How to convert parentheses notation for trees into an actual tree drawing?

Trees are usually drawn as a set of objects connected by edges. But sometimes one sees a non-graphical, parentheses-based notation, like on the example below. What does the indentation mean in such ...
1
vote
1answer
75 views

Number of spanning trees for these 2 figures

The solution to the number of spanning trees of the graph below is given by $6$ and $4 \times 4 - 1$ for Graph A and B respectively. I'm not sure how to get this. Please assist. I did ask a similar ...
1
vote
1answer
121 views

Number of spanning trees of this graph

The solution to the number of spanning trees of the graph below is given by $3 \times 2 \times 3 = 18$. I'm not sure how to get this. Please assist. Thanks! Notes: Just in case anyone was ...
1
vote
2answers
69 views

Can we construct from $[0,\omega_1)$ a space which is strictly-Frechet with no winning strategy in $G_{np}(q,E)$?

I have asked in here a question which tured out to make no sense. I think I have found the confusion and would like to try and rephrase my question: Let $E$ be a topological space, $q \in E$. ...
1
vote
1answer
2k 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 ...
1
vote
2answers
108 views

A bijection between ordered trees and ballot lists

Could you help me to prove that there is a bijection between ordered trees with $n+1$ leaves and ballot lists with $n$ A's and $n$ B's? A ballot list is a sequence of A's and B's such that all ...
1
vote
2answers
172 views

Is having no directed cycles in a directed acyclic graph (DAG) a byproduct of the design, or is it intentional?

According to Wikipedia: That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v ...
1
vote
1answer
78 views

Largest order of automorphism group on a rooted tree?

MacArthur, Sanchez-Garcia, and Anderson have used the ratio of the order of $|Aut(G)|$ and $n!$ (i.e., order of $S_n$) as a normalized measure of the symmetries present in a graph. I am working on ...
1
vote
2answers
148 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 ...
1
vote
1answer
187 views

Proofs involving subtrees of a tree

I have found some claims about trees in my graph theory text, and I am wondering if corresponding proofs can be found, as I cannot find any online or in another text. First, If $T_1$ and $T_2$ ...
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 ...
1
vote
3answers
36 views

The number of (non-equal) forests on the vertex set V = {1, 2, …,n} that contains exactly 2 connected components is given by

The number of (non-equal) forests on the vertex set V = {1, 2, ...,n} that contains exactly 2 connected components is given by $\sum_{k=1}^{n-1} {n-1 \choose k-1} k^{k-2} (n-k)^{n-k-2}$. I am unsure ...
1
vote
1answer
25 views

Existence of infinite subsequence of trees with a subtree contained in the sequence

Assume a statement: For every infinite sequence of rooted trees $\{T\}_{i=0}^\infty$ there is an index $j\geq0$ such that there are infinitely many trees in $\{T\}_{i=0}^\infty$ which contains ...
1
vote
3answers
89 views

is MST a Steiner tree?

I am a little bit confused about MST and Steiner tree? Is an MST a steiner tree?? and suppose we are given a weighted undirected connected graph G = (V,E) and S ⊆ V is the smallest subtree of an MST ...
1
vote
2answers
187 views

Generating function for planted planar trees

I need your help to solve this problem : Give a generating function for planted planar trees with all degrees odd. Show that the number of such trees with $2k+1$ non-root vertices is ...
1
vote
1answer
39 views

Graph G with two Spanning Trees

Let's assume that Graph $G = <V,E>$ has two Spanning Trees $G_a = <V, T_1>$ and $G_b = <V,T_2>$ where $T_1 \cap T_2 = \emptyset$ and $T_1 \cup T_2 = E$. Prove that $\chi(G) \le 4$ ...
1
vote
2answers
481 views

single elimination tournament, don't understand question?

A single elimination tournament is performed in rounds. In each round the teams each play exactly one game and the winners continue, and the losers are knocked out of the competition. So, in each ...
1
vote
3answers
1k views

Sufficient conditions on degrees of vertices for existence of a tree

I am answering a question for an assignment, but I am not sure if my proof is valid, can someone look at it for me? the question: "there is a tree with $p$ vertices. If $d_1, d_2, \dots , d_p$ are ...
1
vote
1answer
12 views

Proof of a tree with a vertex of degree k and less than k vertices of degree 1

The question is : Does there exist a tree with a vertex of degree k and less than k vertices of degree 1? I tried a lot but it is impossible to find. There is no tree with a vertex degree k and less ...
1
vote
3answers
80 views

Proof of an $\iff$ statement on binary trees

Let $x$ and $y$ be two nodes of a binary tree $B$. Prove that $x$ is an ancestor of $y$ $\iff$ $x$ stands before $y$ in the pre-order traversal of $B$ and $x$ stands after $y$ in the ...
1
vote
2answers
46 views

Proof that spanning trees can be converted into one another

Let $T_1$ and $T_2$ be two spanning trees of a graph $G$. Prove that if $e$ is an edge of $T_1$, there exists an edge $f$ in $T_2$ so $T_1-\{e\}+\{f\}$ also is a spanning tree. For $\{e\}\subset ...
1
vote
2answers
49 views

How to go from Tree to Total orders

Given a tree $T=(X,E)$, is it guaranteed for any orientation of the edges $E$, there exist a strict total order preserves it? For instance, let $X=\{x_1,x_2,..x_n\}$ and $E=(x_i,x_{i+1})$ the result ...
1
vote
2answers
143 views

How to prove that the smallest asymmetric tree has at least 7 vertices?

Find the smallest possible number of vertices an asymmetric tree can have (i.e. prove that no smaller tree can be asymmetric). I think that the answer is 7, but I don't know how to prove it.
1
vote
1answer
39 views

Number of binary trees with same X-order and Y-order

What is the number of binary trees which have the same X-order and Y-order as the given tree? Example: X-order: POSTORDER(T) = POSTORDER(TL) POSTORDER(TR) root Y-order: ANTIORDER(T) = ...
1
vote
2answers
84 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
1answer
40 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 ...
1
vote
2answers
173 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
2answers
967 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
1answer
273 views

What is the length of the Minimum Spanning Tree

What is the length of the Minimum Spanning Tree for the following weighted graph? Solution. The length of any minimum spanning tree for this graph (and there is more than one) is 60. The graph and ...
1
vote
2answers
101 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 ...
1
vote
1answer
214 views

For BSP generation, How to intersect or locate a triangle with a plane defined by another triangle?

I've hit a stumbling block in my project to draw the Utah teapot. I want to generate a binary space partition tree of a set of 3D triangles. The decision step in the recursive tree-construction ...
1
vote
1answer
36 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!
1
vote
1answer
191 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
1answer
170 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$ ...
1
vote
1answer
208 views

Depth distribution of normalized decision trees?

Lets work with the following inductive definition of a decision tree: 1) $\bot$, $\top$ are decision trees. 2) If $x_i$ is a variable and $T_0$, $T_1$ are decision trees then $(\lnot x_i \land T_0) ...
1
vote
2answers
517 views

Graph - Minimum spanning tree

I have a graph with a cycle ($v_1,\ldots,v_k, v_1=v_k$). Claim: If there is a cycle with 2 edges of the same weight, and they are the heaviest edges in this cycle, then there is more than one Minimum ...
1
vote
1answer
21 views

Rotations after inserting element in AVL-tree

We want to insert $58$ at the following AVL-tree and then we have to make rotations so that the tree is balanced. According to my notes, we are at the case RL (The first edge leads to the right and ...
1
vote
1answer
28 views

If the inorder traversal of a binary tree produces ordered output, is the tree a binary search tree?

Given a binary search tree, it's easy to see that the inorder traversal returns values from the underlying set in order (according to the comparator that set up the binary search tree). My question ...
1
vote
1answer
48 views

A decision tree has an expected depth of at least $\log n!$

I am looking at the proof of the following theorem and I have some questions. The theorem is the following: On the assumption that all permutations of a sequence of $n$ elements are equally ...
1
vote
1answer
62 views

Proof: How many edges need be removed from this graph to produce the spanning tree?

Assume the graph,$G$ has the degree sequence $6,4,4,3,3,3,3,2,2$. How many edges must be removed from $G$ to produce the spanning tree $T$? We can construct this graph using Havel-Hakimi's ...
1
vote
1answer
24 views

Height of the tree : $T(n) = 4T(n/4)+2T(5n/8)+T(n/8)+\theta(1)$

Let the tree described by $T(n) = 4T(n/4)+2T(5n/8)+T(n/8)+\theta(1)$ Can someone explains why the height is $\log_{8/5}{n}$ I don't know how to proceed
1
vote
1answer
60 views

$k$-connected graphs containing trees

I've encountered the following problem in the book "Graphs and Digraphs" and I'm not sure how to do it. Show that every $k$-connected graph contains any tree of order $k+1$ as a subgraph.
1
vote
1answer
62 views

Complete Binary Tree [closed]

A balanced binary tree is a full binary tree in which every leaf is either at level l or l-­1 for some positive integer l. The set of balanced binary trees is defined recursively by: Basis step: A ...
1
vote
1answer
41 views

Graph theory: tree vertices

How can I calculate the number of vertices of a tree knowing he has 33 vertices of degree 1, 25 vertices of degree 2, 15 vertices of degree 3 and all other vertices of grade 4?
1
vote
1answer
64 views

Iterations of Pascal's Identity

Pascal's Identity states that $n \choose k$ = $n-1 \choose k-1$ + $n-1 \choose k$ since if one element is separated from the rest we can claim that either it is chosen (resulting in $k-1$ elements ...
1
vote
1answer
29 views

Prove that every subgraph of forest has at least one vertex of degree < 2

So I know that a forest is a graph that has no cycles. This is what I had in mind: Assume that we have the subgraph T, which has two options: to be connected or not. if it's connected it has to be a ...
1
vote
2answers
58 views

When trees are the answer: what is the question?

For which optimization problems are (abstract) trees the best solution? E.g. binary search trees are somehow optimal data structures for quick search. But why for example do botanic trees grow as ...
1
vote
1answer
168 views

Number of rooted subtrees of given size in infinite d-regular tree

Currently I am reading a paper where the author states: [...] It is well-known that an infinite $D$-regular rooted tree contains precisely $\frac{1}{(D-1)u + 1} \binom{Du}{u}$ rooted subtrees of ...
1
vote
1answer
37 views

Proving this tree definition with pigeonhole principle

I am studying the following tree definition: Let $T$ be a finite set and a function: $p: T \mathbin{\backslash} \{r\} \rightarrow T$. Then, $(T,p)$ is a tree if and only if, for all $x \in T, p^k(x) ...
1
vote
1answer
123 views

Find Minimal Spanning Tree Using Prim's Algorith

What will be the minimal spanning tree using Prim's Algorithm for this graph Also can i draw a tree and assign the weights as i like,will there be a minimal spanning tree for such a graph