# Tagged Questions

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.

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 ...
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 ...
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 ...
71 views

### Is there tree-based numeral system? [closed]

Preferrably such that ((()) ()), (() (())), (((()))), (() () ()) all were different numbers and any tree can be a number.
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 [[[]],[[],[],[]],[...
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$ ...
33 views

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 ...
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)...
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 ...
97 views

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 ...
277 views

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)...
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 ?
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 ...
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 ...
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 ?