Articles of trees

Prove the existence of a Tree of 15 vertices with some vertices degree given

this is the exercise: If possible draw a Tree with $15$ vertices having 3 vertices with degree $4$; 4 vertices with degree $3$; 6 vertices with degree $2$; 0 vertices with degree greater than the ones of the above. This is what I have done: considering the definition of a tree: with $d_i \ge 1, […]

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 how to prove it mathematically. It makes sense, because vertices of degree […]

Generating all coprime pairs

The Wikipedia article on coprime integers has a brief section on generating all coprime pairs. All pairs of positive coprime numbers $(m,n)$ (with $m>n$) can be arranged in two disjoint complete ternary trees, one tree starting from $(2,1)$ (for even-odd and odd-even pairs), and the other tree starting from $(3,1)$ (for odd-odd pairs). The children […]

If $G$ is an acyclic graph, How can we prove that $G$ is connected?

How to Prove $G$ is connected, if $G$ is an acyclic graph on $n \ge 1$ vertices containing exactly $n − 1$ edges?

Proof by induction and height of a binary tree

I need some help with a simple proof. I want to know if this proof is correct: Let’s define the height of a binary tree node as: 0, if the node is a leaf 1 + the maximum height of the children The height of the tree is the height of the root. I have […]

Any tree degree sequence is a caterpillar degree sequence

In this question Joffan comments My intuition says that any degree sequence that corresponds to a tree can be laid out… in a caterpillar. That would be cool to have a proof of. So I am asking and answering the question.

Local central limit theorem for sum of random variables (size of unrooted trees) with infinite variance

Following set up: We have $i.i.d.$ integer valued random variables $\tau_1,\dots,\tau_n$ with \begin{align*} \mathbb{P}(\tau_1=k)=2k^{k-2}\frac{e^{-k}}{k!} \end{align*} for $k\in\mathbb{N}$. It holds that \begin{align*} \mathbb{E}[\tau_1]=2,\quad \mathrm{Var}(\tau_1)=\infty. \end{align*} The aim is to investigate the asymptotic behaviour of \begin{align*} \mathbb{P}\left(S_{n/2}=n\right), \end{align*} where $S_{n/2}:=\sum\nolimits_{i\leq n/2}\tau_i$, as $n$ tends to infinity. Obviously $\mathbb{E}[S_{n/2}]=n$, but as the variance is not finite, there is […]

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 trees with 6 vertices, 7 vertices and so on).

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 vertex of degree at most 2n-1, thus I can […]

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 know that if a tree $T$ has two or more vertices, meaning $|V(T)| \geqslant 2$, then $T$ has […]