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
1answer
397 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
131 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
507 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 ...
3
votes
2answers
71 views

Is there tree-based numeral system? [closed]

Preferrably such that ((()) ()), (() (())), (((()))), (() () ()) all were different numbers and any tree can be a number.
3
votes
1answer
54 views

Infinite graph theory: What's a tree?

Consider a finite graph $G$: $G$ is a tree if it satisfies any of the following equivalent conditions: (1) $G$ is connected and no cycle can be a subgraph of $G$. (2) $G$ is connected and no cycle ...
3
votes
1answer
48 views

MST, Cut in Graph, Some Claims?

I ready for taking a P.hD Entrance Exam. one of old-solution problem of Data Structure is as follows: Which of the following Claims is True about MST of Simple, ...
3
votes
1answer
98 views

How many trees on N vertices have exactly k leaves?

I need help on the topic of counting labeled trees (with its nodes numbered from 1 to N) with exactly k leaves. I have thought about surjective functions that return the father of a node, but I'm not ...
3
votes
2answers
225 views

Graph Theory: Trees, leaves and cycles

So, a vertex is called a leaf if it connected to only one edge. a) Show that a tree with at least one edge has at least 2 leaves. b) Assume that G = (V, E) is a graph, V ≠ Ø, where every vertex ...
3
votes
1answer
60 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
153 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
457 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
3answers
3k views

Number of binary trees with N nodes

I am trying to calculate the number of trees (non isomorphic) with n nodes (total including leaves). I think that there are n! such trees, but I don't know how to prove that. I know that the number ...
3
votes
1answer
171 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
103 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
0answers
86 views

Existence of $\lambda^+$ Aronszajn trees when $\lambda$ is regular and $2^{<\lambda}=\lambda$

While I was dealing with Aronszajn trees I found the following exercise from Kunen's old book. If $\kappa=\lambda^+$ and $\lambda$ is a regular uncountable cardinal and $2^{<\lambda}=\lambda$ ...
3
votes
1answer
33 views

Best way to find if a subgraph has a cycle

I am implementing Kruskal's algorithm to find a minimal spanning tree of a connected graph $G$. If $H$ is a subtree of $G$, does anyone know a smart way of checking if $H+e$, where $e$ is an edge of $...
3
votes
1answer
277 views

Tree having no vertex of degree 2 has more leaves than internal nodes

If $T$ is a tree having no vertex of degree 2, then $T$ has more leaves than internal nodes. Prove this claim by a) induction, b) by considering the average degree and using the handshaking lemma. I ...
3
votes
1answer
115 views

Number of spanning trees in a complete split graph

A graph is a complete split graph if we can partition it into an independent vertex set and a clique, such that every vertex of the independent vertex set is adjacent to every vertex in the clique. ...
3
votes
0answers
161 views

Condition for a graph to have only one MST (Minimum Spanning Tree)?

Can somebody tell me if there is a condition for an edge-weighted graph to have exactly one MST? I know that it can have more minimum spanning trees, but can it have only one? Thanks in advance!
3
votes
0answers
121 views

Tree decomposition by hand for understanding

I am implementing "algorithm 2" from the paper "Treewidth computations I. Upper bounds" by Bodlander and Koster[1,page5] and I am not sure if I understand it or not. As I understand, the algoritm ...
3
votes
0answers
132 views

Associativity of the tensor product of dendroidal sets

For any smal category $A$, I shall write $\widehat A$ for the category $[A^{\text op}, \mathbf{Set}]$ of presheaves on $A$, and $y_A\colon A \to \widehat A$ for the Yoneda embedding relative to $A$. ...
3
votes
1answer
66 views

Identifying Binary Search Trees from their Prufer Sequence

If you ignore its root, a Binary Search Tree generated by some permutation of $\{1, \ldots, n\}$ is a labeled tree. Which means you can calculate its Prufer Sequence. I did this in Python and I found ...
3
votes
0answers
105 views

a problem about finding an algorithm for a spanning tree in a 3-regular graph

"Consider the connected 3-regular graph G. Find an algorithm that produces a subgraph S of G which is a spanning tree and if you remove S from G then G is divided into some components that each of ...
3
votes
0answers
77 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
73 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
56 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 $r(...
3
votes
1answer
92 views

Number of nodes with even offspring

I've been working on a combinatorics assignment, and while the last few questions had clever solutions which didn't involve functional equations and the use LIFT, I fear I'm at my end. Given a ...
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*} T(1)...
2
votes
2answers
2k 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
1answer
97 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
1answer
277 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 anymore)...
2
votes
3answers
649 views

What is the maximal path of a tree?

Could anyone explain obviously what the maximal path is ? Is it necessary for a tree that has two maximal paths that share no common vertex ?
2
votes
3answers
240 views

In a Tree, show that the largest degree of a node <= number of nodes of degree 1

Let $T$ be a tree in which the largest degree of a node equals to $t$. Let $n_1$ denote the number of nodes of degree $1$ in $G$. Prove that $n_1 ≥ t$ I understand why this works but I am not sure ...
2
votes
3answers
1k 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
3k views

What is the main difference between a free tree and a rooted tree?

In graph theory what is the difference between a rooted tree and a free tree ? What is normally meant when just the plain "tree" is used ?
2
votes
2answers
201 views

A tree on n vertices where every vertex has degree 1 or 4. Prove that n ≡ 2 (mod 3)

Let T be a tree tree on n vertices where every vertex has degree 1 or 4. Prove that n ≡ 2 (mod 3)
2
votes
1answer
335 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
192 views

Prove that the vertex degree of a minimum spanning tree is in $\mathcal{O}(1)$

I have given a set of points $S$ in $\mathbb{R}^2$. From the this points I create a mininum spanning tree MST. The euclidean distance of the points is used as the weight for the edges. The ...
2
votes
2answers
69 views

could a spanning tree graph be expressed by a lower triangular matrix?

Suppose a directed spanning tree graph $G$, there are $n$ nodes, and the root is node $1$. We express this graph by a matrix $M_{n\times n}$. If there is an directed edge from node $i$ to node $j$, ...
2
votes
1answer
136 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
3answers
770 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 me)...
2
votes
1answer
660 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 unlabeled)....
2
votes
2answers
768 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
278 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
40 views

Constructing every spanning tree from addition and deletion of edges

Let $G = (V,E)$ be given (note that this is not necessarily simple), and consider the set of every spanning tree of $G$, $S$. Choose any $G_a, G_b \in S$. Is it possible to construct $G_b$ from $G_a$ ...
2
votes
1answer
363 views

The number of pendant vertices in a tree

Let $T$ be a tree with vertices $\{v_1, v_2, . . . , v_n \}$ for $n \geq 2$. Prove that the number of pendant vertices in $T$ is equal to $$\large{2 + \sum_{v_i,deg(v_i) \geq 3}\big( deg(v_i) - 2 \...
2
votes
2answers
72 views

Algorithm to cut the graph into a tree.

Given a finite connected graph $G$, I can make a finite number of cuts on the edges to obtain a tree. What is the most efficient algorithm to perform this procedure? Thanks, Vladimir
2
votes
1answer
71 views

Graph with fixed amount of spanning trees

"Find a graph with 8 vertices, which have exactly 27 spanning trees." How do I find such a graph, or prove one does not exist?
2
votes
1answer
602 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
246 views

Generating function for planted planar trees

I need your help to solve this problem : Give a generating function for planted planar trees with all degrees odd. Show that the number of such trees with $2k+1$ non-root vertices is $$\...