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

4
votes
2answers
671 views

Show that if G is a simple graph with at least 4 vertices and 2n-3 edges, it must have two cycles of the same length.

For $n\ge4$, let G be a simple n-vertex graph with at least $2n - 3$ edges. Prove >that G has two cycles of equal length. (West's Introduction to Graph Theory Q 2.1.42) I am trying to prove the ...
4
votes
4answers
1k views

In binary tree, number of nodes with two children when number of leaves is given

For a binary tree what is the number of nodes with two children when the number of leaves is 20? I know that for complete binary tree, when the number of leaves is x then the number of internal nodes ...
4
votes
2answers
152 views

Some equivalence relation from flipping binary trees

I know almost nothing in combinatorics, so this question might be very easy, or well-known. Fix a number $n$. We will consider rooted planar binary trees with $n$ leaves. We will distinguish between ...
4
votes
1answer
688 views

How many vertices of degree 3 or more can 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 ...
4
votes
2answers
236 views

On the number of caterpillars

A caterpillar is a tree with the property that if all the leafs are removed then what remains is a path. Could you help me to prove that there are $2^{n-4}+2^{\lfloor n/2\rfloor-2}$ caterpillar on $n$ ...
4
votes
1answer
83 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 ...
4
votes
1answer
309 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 ...
4
votes
3answers
187 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 ...
4
votes
1answer
264 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
2answers
122 views

Computing Ancestors of # for Stern-Brocot Tree

Reading about the Stern-Brocot tree, the article gives this example: using 7/5 as an example, its closest smaller ancestor is 4/3, so its left child is (4 + 7)/(3 + 5) = 11/8, and its closest ...
4
votes
1answer
196 views

Exercise 1.1 in Serre's trees

I have in fact become stuck by the very first problem in Serre's book on Trees. It is a little bit embarrassing but ho-hum. I start with Serre's definition of direct limits. Let $(G_i)_{i \in I}$ be ...
4
votes
2answers
2k views

Show that a graph has a unique MST if all edges have distinct weights [duplicate]

Prove that if all edge-costs are different, then there is only one cheapest tree (minimum spanning tree or MST). (Use contradiction and make sure to keep track of the costs of the different trees ...
4
votes
0answers
69 views

Why is the intersection of countably many homogeneously Suslin subsets of $\,^{\omega} \omega$ homogeneously Suslin?

I found this assertion in these notes: The derived model theorem (Steel) right in the beginning on page 3, together with the remark that this is 'not too hard to show'. Unfortunately, I'm ...
4
votes
0answers
27 views

Simple criteria to know if the p-nary notation of an integer can generate a tree by preorder traversing?

I am treating with a preorder tree traversal structure(which means sequences where the children of each tree node are listed behind it) now for some other problems and the structure is like: ...
4
votes
1answer
56 views

Expected number of subtree removal in a tree.

I was solving this problem. In a gist the problem is as follows: You are given a rooted tree. On each step you choose a node randomly and remove the subtree rooted by that node and the node itself,...
4
votes
2answers
5k 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 ...
4
votes
0answers
175 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, ...
4
votes
0answers
354 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 ...
4
votes
0answers
249 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,\dotsc, x_n$ for which a directed Eulerian circuit exists. A spanning arborescence ...
4
votes
0answers
107 views

Identify this combinatorial construction

I am no combinateur, but I stumbled across the following construction when studying an operad arising from information theory (actually it's a special algebra of an A$_\infty$-operad). It looked ...
4
votes
0answers
137 views

Are almost all rooted trees asymmetric?

It's well known that almost all graphs are asymmetric (have trivial automorphism group) and that almost all free trees are symmetric. By which argument do I see whether almost all rooted trees are ...
3
votes
5answers
300 views

Halting probability of random tree-generating algorithm

Suppose I have a tree-generating algorithm as follows. Begin with one root vertex. With equal probability, create either three subvertices or none. Recurse and repeat for each of the subvertices (if ...
3
votes
5answers
9k views

How many edges does an undirected tree with $n$ nodes have?

How many edges does an undirected tree with $n$ nodes have?
3
votes
2answers
7k views

How to find non-isomorphic trees?

"Draw all non-isomorphic trees with 5 vertices." I have searched the web and found many examples of the non-isomorphic trees with 5 vertices, but I can't figure out how they have come to their ...
3
votes
2answers
434 views

In any tree, what is the maximum distance between a vertex of high degree and a vertex of low degree?

In any undirected tree $T$, what is the maximum distance from any vertex $v$ with $\text{deg}(v) \geq 3$ to the closest (in a shortest path sense) vertex $y$ with $\text{deg}(y) \leq 2$? That is, $y$ ...
3
votes
2answers
371 views

Find a Generating Function for Ordered Rooted Ternary Trees

The Full Question If we let $T=$ the family of rooted ternary trees, $t_n =$ be number of trees in $T$ with $n$ nodes and $T(x) = \sum\limits_{n=0}^{\infty}w_nx^n$ be the generating function of $T$. ...
3
votes
1answer
65 views

Number of spanning trees of a labeled graph

This labeled graph is given, I need to find the number of its spanning trees. The number of spanning trees of the following graph is 3 and the number of spanning trees of this is 8 So as a ...
3
votes
2answers
6k 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 ...
3
votes
2answers
87 views

Number of undirected trees

Given n numbered vertices I want to know the number of different trees that can be created with them. I know that cayley's theorem says it's $n^{n-2}$, but why can't it also be: $\binom{\binom{n}{2}}...
3
votes
3answers
372 views

Cheapest spanning tree

I am trying to prove the following: Let $x_1$ be any vertex of a weighted connected graph $G$ with $n$ vertices and let $T_1$ be the subgraph with the one vertex $v_1$ and no edges. After a tree (...
3
votes
1answer
813 views

what is an “edge disjoint spanning tree”?

if there are n = 2 vertices in a connected graph, i am supposed to have "n/2 edge disjoint spanning trees". This means i should have 1 edge disjoint spanning tree for a n = 2 graph? My best guess ...
3
votes
1answer
173 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 ...
3
votes
2answers
289 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 ...
3
votes
2answers
30 views

You can always delete a vertex from a tree $G$ such that the remaining connected components have size at most $|V(G)|/2$.

I want to prove the statement in the title: for any tree on $n$ vertices, it is possible to delete a vertex such that the deletion leaves connected components with at most $n/2$ vertices each. I drew ...
3
votes
1answer
73 views

Set Theory: Tree Property

Why does the tree property hold for regular cardinals but not singular cardinals? (I.e. There exists a tree of height $\kappa$ with countable levels and no cofinal branch for $\kappa$ a singular ...
3
votes
1answer
109 views

Proofs involving some general formulae for trees and binary trees.

So here I have 3 tree-related questions. 1) Let $n\geq2$ and let $d_1 ≤d_2 ≤···≤d_n$ be a sequence of integers. Show that there is a tree with degree sequence $d_1,d_2,...,d_n \Leftrightarrow \sum ...
3
votes
1answer
48 views

Height of quasi-complete binary tree

Let us define a quasi-complete binary tree as a rooted binary whose nodes have all two children except at most those of the penultimate level, which can have either one or two children. I read that ...
3
votes
1answer
76 views

Is this random binary tree finite?

Consider the following procedure for generating a random binary tree: Starting with a full binary tree (i.e., each node has either two or no children) we iterate over the leaves and (independently) ...
3
votes
1answer
145 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)?
3
votes
1answer
6k 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 ...
3
votes
2answers
2k 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 ...
3
votes
2answers
483 views

Bijection between binary trees and plane trees?

I would like to describe a bijection between binary trees and plane trees. A binary tree has a root node and each node of the tree has at most 2 children (left and right). A plane tree has a root node ...
3
votes
1answer
570 views

Spanning Trees of the Complete Graph Avoiding a Given Tree

EDIT: I think everyone understood, but I never explicitly stated that I am looking at labeled spanning trees. Let $T$ be a tree contained in $K_n$ (the complete graph on $n$ vertices). How can one ...
3
votes
1answer
45 views

Bona “A Walk Through Combinatorics” Problem 10.29

Given a tree $T$, define the "total distance" of a vertex $v$ by $$ td(v) = \sum_{w \in V(T)} d(v,w), $$ where $d(v,w)$ is the number of edges in the unique $vw$-path in $T$. In any tree, the value of ...
3
votes
1answer
42 views

Must a minimum weight spanning tree for a graph contain the least weight edge of every vertex of the graph?

Currently learning about spanning trees and using Kruskal's algorithm and I was wondering whether a minimum weight spanning tree of a weighted graph must contain one of the least weight edges of every ...
3
votes
1answer
49 views

How many ways can I connect labeled trees into a tree.

Suppose I have the labeled trees $T_{1}, \ldots, T_{n}$ with $b_{1}, \ldots, b_{n}$ vertices respectively. I would like to know how many ways I can compose a tree from these trees by using all trees? ...
3
votes
1answer
217 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 ...
3
votes
1answer
389 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
2answers
130 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
2answers
505 views

Number of undirected trees with labeled edges, one repeating

I need to find the number of undirected trees on $n$ vertices such that the edges (and not the vertices) are labeled and exactly one label appears twice (i.e. there are $n-2$ possible labels and they ...