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

5
votes
2answers
473 views

How many vertices of degree 1 in a tree?

How many vertices of degree 1 are there in a tree with no vertices of degree more than 4? The only thing that I have right now is that the number of edges in a tree is n-1 where n is the number of ...
0
votes
2answers
91 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 ...
1
vote
2answers
125 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
228 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 ...
1
vote
1answer
240 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 ...
3
votes
2answers
2k views

Finding number of homeomorphically irreducible trees of degree N

There is a scene in Goodwill Hunting where professor challenges students with task of finding all homeomorphically irreducible trees of degree 10. This is discussed in many places, such as here and is ...
0
votes
2answers
109 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
89 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 $ ...
2
votes
1answer
51 views

Proof of the Converse of Kraft's Theorem

So I have already proven Kraft's theorem for ternary trees, and I have been tasked with proving the converse. That is, I need to show that there is a ternary tree with $k$ leaves, such that leaf $i$ ...
0
votes
0answers
21 views

Simplification of a dervived binary tree with n nodes [duplicate]

hi I need help with this problem how do simplify this equation and what are the steps and approaches to this problem
14
votes
2answers
286 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, ...
0
votes
0answers
288 views

What is the algorithm to sort 5 elements in 7 binary comparisons?

I'm tasked with finding the algo that sorts 5 elements in 7 binary comparisons. (The 7 is derived from ceilingFunction(log 5!), which our text states is the minimum number of comparisons required for ...
2
votes
2answers
876 views

Tree pruning question…

all. I'm facing the question: "A chain letter starts when a person sends a letter to five others. Each person who receives the letter either sends it to five other people who have never received it ...
3
votes
0answers
85 views

Mathematical notation for formulas involving trees

I am working on document that requires me to write such things as "$T_1$ is a descendant of $T_0$", or "$N_1$ is an parent of $N_2$". For now, I've been highjacking set notation for use in formulas, ...
2
votes
1answer
1k views

Show that Minimum Spanning Tree is unique

Show that MST is unique in case the edge weights are pairwise different $(w(e)\neq w(f) \text{ for } e\neq f)$. I thought that the proof can be done for example by contradiction, saying that we ...
1
vote
1answer
377 views

How can I tell how many non-isomorphic unrooted trees with 6 edges exists without drawing them all?

Typically my professor asks that we draw them all, but I would like to save some time to confirm how many I need.
1
vote
0answers
49 views

Red Black Binary Search Trees

Give an example of a Red-Black tree and a value, for which inserting the value, and then immediately deleting it yields a tree that is different from the tree before the insertion.
0
votes
1answer
41 views

Identify Type of Recursive Sequence?

I would love to learn techniques for solving the following, but I can't seem to identify this type of sequence: let $N > 0$ and let $k$ be an arbitrary positive integer between $0$ and $N-1$ ...
0
votes
1answer
174 views

Let T be a tree with sub-trees which each set has a vertex in common - hence T has a vertex in all of its sub-trees?

The question is: Let T be a tree with sub-trees $T_1,T_2,..,T_n$ such that all trees $T_i,T_j$ have a vertex in common which each set has a vertex in common - show that T has a vertex in all $T_i$. ...
0
votes
0answers
105 views

Nilpotency of the adjacency matrix of a directed tree network

Say I have a directed network that is organized in a tree, with all connections going downstream (genealogically). By that I mean that there is one root node connected to $c_{00}$ child nodes, and ...
1
vote
1answer
161 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$ ...
0
votes
1answer
106 views

Recurrence relation for the number of spanning trees in a connected graph proof

The number of spanning trees in a graph $G$ containing an edge $e$ is equal to the number of spanning trees in $G/e$. The number of spanning trees in a graph $G$ not containing an edge $e$ is equal to ...
1
vote
1answer
187 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 ...
6
votes
1answer
920 views

Height of a full binary tree

A full binary tree seems to be a binary tree in which every node is either a leaf or has 2 children. I have been trying to prove that its height is O(logn) unsuccessfully. Here is my work so far: I ...
3
votes
1answer
80 views

Prong Corollary, $G$ has a subgraph isomorphic to $T$

There is a corollary in Diestel textbook Graph Theory. Corollary 1.5.4. if $T$ is a tree and $G$ is any graph with $\delta(G) \geq |T|-1$, then $T \subseteq G$, i.e. $G$ has a subgraph isomorphic ...
0
votes
2answers
505 views

Proving a simple connected graph is a tree if adding an edge between two existing vertices of T creates exactly one cycle

When proving a simple connected graph is a tree if adding an edge between two existing vertices of T creates exactly one cycle, is it sufficient to just remove that edge that created a cycle, then it ...
3
votes
0answers
271 views

Algorithm for generating homeomorphically irreducible trees of size n

In this video they talk about generating all the homeomorphically irreducible trees of size 10. I was wondering if there is a generating algorithm for generating all the homeomorphically irreducible ...
8
votes
2answers
212 views

Ordinal interpretation of Friedman's $n$?

I heard that Kruskal's tree theorem can be turned into a finite form that creates an extremely fast growing function because ordinals could be encoded into trees. On this wiki page it mentions that ...
1
vote
2answers
91 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 ...
3
votes
1answer
57 views

What's the rank of this well founded relation?

Definition A tree is an ordered list of trees. (N.B these are finite objects and there is a very simple computable bijection of them with $\mathbb N$) Examples [] and [[],[],[]] and ...
0
votes
0answers
89 views

Straight skeleton is a tree

Can anybody give me a hint on how to prove that the straight skeleton of every polygon is a tree. Here is the definition of the straight skeleton (taken from Wikipedia): The straight skeleton of a ...
2
votes
2answers
2k views

Determining Ambiguity in Context Free Grammars

What are some common ways to determine if a grammar is ambiguous or not? What are some common attributes that ambiguous grammars have? For example, consider the following Grammar G: $S \rightarrow ...
1
vote
1answer
137 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 ...
2
votes
3answers
360 views

Graphs: trees, induction proof

I was wondering if you could help me prove the following. $G$ is a tree $\iff$ deleting any edge will disconnect it. And a similar one: $G$ is a tree $\iff$ adding any edge will create a cycle. I ...
0
votes
2answers
351 views

Confusion related to a graph problem

I have this question related to this graph problem Suppose that an n-node undirected graph G = (V , E) contains two nodes s and t such that the distance between s and t is strictly greater than n/2. ...
1
vote
0answers
43 views

Enumeration of symbols in grammatical expressions or vertices in tree graphs

I have expressions (type of a function) like e.g. $$f:(A\to B)\to C \to (D\to E)\to F.$$ (Where I understand $A\to B\to C$ as $A\to (B\to C)$, in case that is relevant.) There might be information ...
2
votes
1answer
50 views

Number of upper sets of size $n$ in a finite tree

Consider a finite tree $T = (V, <)$, where $y < x$ means that $y$ is the parent of $x$. We assume that $T$ has a unique root $r$ that has no parent. An upper set of $T$ is a subset $S$ of $V$ ...
1
vote
2answers
315 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 ...
6
votes
1answer
403 views

Is the graceful labeling conjecture still unsolved?

From the Wikipedia article on graceful labeling: ... A major unproven conjecture in graph theory is the Ringel–Kotzig conjecture, named after Gerhard Ringel and Anton Kotzig, which hypothesizes that ...
0
votes
1answer
121 views

Computational Complexity of Parallel Algorithms

Does parallelism factor in when deriving the computational complexity of a parallel algorithm? Suppose I have a perfect binary tree $T$ with leaves numbered $1$ to $n$, and an algorithm ...
2
votes
0answers
74 views

Presentation of tree decompositions (and related concepts) in terms of continuous maps?

A tree decomposition of a graph $G$ is commonly defined in terms of a tree $T$ with the following structure: Each vertex $t \in V(T)$ is associated to a set $X_t \subseteq V(G)$; The union ...
2
votes
1answer
70 views

A way to codify (pre-calculatate) if a one Tree Node is a descendant of another

I have a simple, 1-directional tree representing the veins in a human body. It looks somewhat like this (red dots are nodes, blood flow is always downwards, sorry for my drawing): What I need is a ...
3
votes
2answers
1k views

What does lg x mean? is it $\log_2 x$ or $\log_{10} x$ in binary trees

I'm a bit confused, $\log_{10} x = \log x $ right? I believe I've read somewhere that $\log_{2} x = lg x$ but some people say lg = $\log$. So what does lg really stand for? specifically when talking ...
0
votes
1answer
306 views

Is this formula for the number of nodes for a complete tree or a full and complete tree?

In a lecture it was said that "How many nodes are there in a complete k-ary tree with height h?" and this was the answer: $$ \sum^{h}_{i = 0}k^i $$ where h is the height and k is the max number of ...
2
votes
2answers
1k views

Proof by induction and height of a binary tree

I need some help with a simple proof. I want to know if this proof is correct: Let's define the height of a binary tree node as: 0, if the node is a leaf 1 + the maximum height of the children ...
3
votes
2answers
89 views

Real tree and hyperbolicity

I seek a proof of the following result due to Tits: Theorem: A path-connected $0$-hyperbolic metric space is a real tree. Do you know any proof or reference?
3
votes
1answer
61 views

Tree formalisms

The intuitive notion of a tree in mathematics is quite straightforward. However, there are several different formalisms of the tree concept. The link http://ncatlab.org/nlab/show/tree lists several ...
8
votes
0answers
108 views

Free medial magmas

A medial magma is a set $M$ with a binary relation $*$ satisfying $(a*b)*(c*d) = (a*c)*(b*d)$. Medial magmas constitute an algebraic category $\mathsf{Med}$, therefore there is a functor $\mathsf{Set} ...
3
votes
1answer
111 views

Virtually infinite cyclic groups act on a tree

A virtually infinite cyclic group $G$ is quasi-isometric to $\mathbb{Z}$ and thus has two ends; by Stallings theorem, $G$ acts (without inversion) on a tree with finite edge-stabilizers. But the ...
0
votes
1answer
203 views

Relationship between ordered and binary trees

I am looking for a formula for the number of ordered trees with $n$ vertices and $l$ leaves as well as for a formula for the number of binary trees with $l$ left and $r$ right children. Finally, I ...