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
674 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
694 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
237 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
84 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
190 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
266 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
28 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
57 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
355 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
254 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
138 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
441 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
382 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
373 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
54 views

Amalgam of trees

Definition A tree is a partially ordered set $(T, <)$ such that for each $t \in T$, the set $\{s \in T : s < t\}$ is well-ordered by the relation $<$. For trees $(T,<_T)$, $(S,<_S)$, $...
3
votes
1answer
847 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
292 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
32 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
111 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
49 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
148 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
492 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
24 views

prove graph G with n vertices, vertex of degree $n-1$ and rest of the vertices of degree $1$ is a tree graph

I'm a discrete math student and I've bumped into the following question. I tried to prove it and specifically in first part I thought of two ways of proving it. but in each of the ways the proof looks ...
3
votes
1answer
46 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
44 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
2k views

Longest Path in undirected unweighted graph

I came across a problem where I have to find out the longest path in a given graph. I have list of edges ( eg.{AB, BC} ) which states there is an edge between vertices/nodes (A,B,C). Now i want to ...
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 ...