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

3
votes
2answers
114 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 ...
3
votes
1answer
176 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 ...
3
votes
1answer
26 views

Automorphism of Tree

Let $\sigma$ and $\theta$ be two automorphisms of tree $X$. I want to show that min$_{v\in V(X)}d(v,\sigma(v))=$min$_{v\in V(X)}d(\theta^{-1}\sigma\theta(v),v)$. I know every automorphism of tree is ...
3
votes
2answers
84 views

How many vertices does this tree have?

Suppose that $T$ is a tree. It has $e$ edges and $n$ vertices, and $\overline{T}$ has $10e$ edges. What is n? I think $n = 1$ is a solution, because $T$ can have no edges then, so $0=10*0$. A ...
3
votes
1answer
104 views

A Graph as a Union of K forests.

I want to show that a graph G that is a union of k forests has a chromatic number of at most 2k. I have narrowed my problem down to trying to show that any graph G that is a union of n trees has a ...
3
votes
1answer
134 views

Understanding countable ordinals (as trees, step by step)

Even though ordinal numbers – considered as transitive sets – are perfect non-trees, it is worth (and natural) to visualize them as trees, starting from the finite ones which are given as ...
3
votes
1answer
89 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 ...
3
votes
1answer
59 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 ...
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 ...
3
votes
1answer
23 views

Shortest path between two vertex

How we can find Shortest path between two vertex in a weighted directed acyclic graph that has positive and negative weight. in O(|V|+|E|)? thanks to all.
3
votes
0answers
35 views

What are the algebraic and topological properties of a tree (graph theory), and what are any possible connections?

I'm a non-mathematician working with trees (mostly rooted and oriented trees). Typically, I understand them as join-semilattices, so they have an implicit algebraic structure: they form a subgroup ...
3
votes
0answers
40 views

Proof on Dyadic Trees [Smullyan: First-Order Logic, chapter 1, section 0]

I'm having difficult with a proof from Smullyan's First-Order Logic, Chapter 1 Section 0 (Reprint, Dover 1968, p. 4): Prove: In a dyadic tree, define x to be to the left of y if there is a ...
3
votes
0answers
41 views

maximizing the inverse degree in a graph

The inverse degree in the graph $G$ is defined as \begin{align*} r(G) = \sum_{i=1}^N \frac{1}{d_i}, \end{align*} where $d_i$ is the degree of node (vertex) $i$. Is the connected graph with maximum ...
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 ...
3
votes
0answers
89 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, ...
3
votes
0answers
280 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
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*} ...
3
votes
0answers
141 views

Number of spanning arborescences

I am trying to prove the following result from my book: Let $G$ be a directed graph with vertices $x_1,x_2,\cdots x_n$ for which a directed Eulerian circuit exists. A spanning arborescence with root ...
2
votes
1answer
88 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 ...
2
votes
2answers
3k 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 ...
2
votes
1answer
263 views

Proof about trees

Show that in any tree there exists a node such that, if we remove this node and the edges adjacent to it, we will obtain trees which have at most n/2 nodes (the removed node is not counted ...
2
votes
2answers
910 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 ...
2
votes
5answers
9k 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 ...
2
votes
1answer
276 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
1answer
94 views

How to establish bijective between the set of rooted trees and natural numbers, using Godel numbering?

Consider the structure of a rooted tree independent of its underlying set, (i.e. in the sense of trees as combinatorial species). I know a number of ways which we can encode any such tree in natural ...
2
votes
1answer
383 views

Recursive Generating function for enumerating leaf labeled binary trees

Let be B(z) the exponential generating function for the number $b_n$ of different rooted unordered binary trees with exactly n leaves labeled only at their leaves (so the internal nodes are ...
2
votes
2answers
492 views

Number of inner nodes in relation to the leaf number N

I am aware that if there is a bifurcating tree with N leaves, then there are (N-1) internal nodes (branching points) with a single root node. How is this relationship proved? Best,
2
votes
1answer
245 views

Fast question about minimum spanning trees

If any edge from a given spanning tree T0 is contained in some minimum spanning tree T*, does this imply that T0 is also a minimum spanning tree ? Right now, I'm trying to draw on paper some graphs ...
2
votes
1answer
47 views

Proof involving maximum weight of edge in minimum spanning tree

Let $G$ be a minimum spanning tree of a complete graph. Let $e$ be the maximum weight edge in $G$. I'd like to proof that given any other spanning tree $G'$ of this graph, being $j$ the maximum weight ...
2
votes
2answers
45 views

Finding an Isolated Maximum subset of tree

Given an Oriented Tree T(V,E) with n nodes, each node have an non-negative number (the numbers are not related to nodes order). A subgroup Z of V called an Isolated if it doesn't include two nodes ...
2
votes
1answer
129 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 ...
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 ...
2
votes
3answers
381 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 ...
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 = ...
2
votes
1answer
312 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: ...
2
votes
1answer
51 views

How to call a tree with a single branch?

How do you call a tree with only one branch (in other words, where every vertex has maximum one direct successor)?
2
votes
1answer
38 views

Number of trees of a certain size

Given a branching factor $b$ and a tree height $h$, a complete tree has $\sum_{i=0}^h b^i$ nodes. Define a partial tree as a sub-tree of the complete tree, with the same root. How many such partial ...
2
votes
1answer
49 views

Counting problem (should use Cayley's formula)

How many trees above $V=\{1,2,3,4,5,6,7,8,9\}$ are there, such that $deg(4)=5$? I know I should use Cayley's formula somehow.
2
votes
4answers
861 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 ...
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 ...
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 ...
2
votes
1answer
74 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 ...
2
votes
1answer
268 views

Length of Shortest Path in a Generated Binary Tree

Let's say I have a binary tree of $2$-tuples of positive integers starting with $(1,1)$. The left-child of any element $(A,B)$ is $(A,A+B)$, and the right-child of any element is $(A+B,A)$. Hence, the ...
2
votes
3answers
393 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 ...
2
votes
1answer
50 views

Infinite Tree Probability Question

Suppose I have 10 dollars and I'm able to make fair 50/50 bets like flipping a coin. Now suppose each bet is for 1 dollar. What is the probability that if I keep making bets until I hit 0 dollars ...
2
votes
1answer
166 views

Generating function for vertices distance from the root in a planar tree

I need you help to solve this problem: Consider a planar tree with $n$ non-root vertices. Give a generating function for vertices distance $d$ from the root. Proof that the total ...
2
votes
1answer
784 views

How to draw all nonisomorphic trees with n vertices?

I have a textbook solution with little to no explanation (this is with n = 5): Could anyone explain how to "think" when solving this kind of a problem? (for example, drawing all non isomorphic ...
2
votes
1answer
81 views

questions about binary search tree

Show that every n-node binary search tree is not equally likely (assuming items are inserted in random order), and that balanced trees are more probable than straight-line trees. How is it prove ...
2
votes
1answer
609 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 ...