A tree is a graph that is connected but contains no cycles.
2
votes
2answers
26 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 ...
4
votes
2answers
51 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 ...
1
vote
3answers
30 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?
...
5
votes
1answer
136 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 ...
0
votes
2answers
44 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 ...
0
votes
1answer
122 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
1answer
127 views
What is the fairest solution/formula for rewarding points in a hierarchical network?
Introduction
The nature of this hierarchical network is based on the concept of Multi-Level Marketing strategy.
Example 1 - Unfair Situation
Ancestor receives 1 point for every descendant ...
1
vote
2answers
39 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 ...
3
votes
1answer
40 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
140 views
No of labeled trees with n nodes such that certain pairs of labels are not adjacent.
Moderator Note: This is a current contest question on codechef.com.
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 ...
1
vote
0answers
26 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
57 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
1answer
132 views
has deleting node in a binary search tree Displacement feature?
I am developing an academic project about graph and tree theory.I searched a lot but I didn't find a clear answer. In a part of project we want to delete some nodes from tree for example we want to ...
0
votes
2answers
35 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
191 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, ...
2
votes
1answer
18 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$ ...
5
votes
3answers
189 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
0answers
20 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
0
votes
0answers
43 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 ...
4
votes
1answer
87 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 ...
2
votes
2answers
89 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 ...
0
votes
0answers
17 views
2-3-4 Tree: how to insert numbers to optimise the layers?
Let's imagine I have number in a list from 1 to 15, then the way to have 2 full rows is to insert them with this order into an empty 2-3-4 tree
2,4,6,8,10,12,14,1,3,5,7,9,11,13,14,15
(you can test ...
0
votes
1answer
37 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$ ...
2
votes
0answers
30 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, ...
1
vote
1answer
56 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 ...
9
votes
2answers
279 views
How can I prove the identity $2(n-1)n^{n-2}=\sum_k\binom{n}{k}k^{k-1}(n-k)^{n-k-1}$?
How can I prove the identity
$$2(n-1)n^{n-2}=\sum_k\binom{n}{k}k^{k-1}(n-k)^{n-k-1}?$$
I know that the number of trees on $n$ vertices is $n^{n-2}$, and that a tree with $n$ vertices has $n-1$ ...
1
vote
1answer
71 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
36 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
30 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
42 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
49 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
46 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
31 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
1answer
75 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 ...
3
votes
1answer
71 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 ...
1
vote
2answers
126 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 ...
3
votes
1answer
26 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 ...
1
vote
2answers
127 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 ...
2
votes
0answers
190 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 ...
3
votes
1answer
47 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 ...
2
votes
3answers
98 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
125 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. ...
2
votes
1answer
47 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 ...
9
votes
2answers
280 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 ...
6
votes
2answers
109 views
Question about trees and generalizing the Principle of Dependent Choices.
One form of the Principle of Dependent Choices is that for any tree $T$ of height $\omega$ such that every node of $T$ has a successor, there is a branch of $T$ of length $\omega$. In this post, I ...
0
votes
0answers
55 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
1answer
42 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
1answer
69 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 ...
0
votes
1answer
138 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
0answers
26 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 ...
