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

5
votes
2answers
135 views

Maps of primitive vectors and Conway's river, has anyone built this in SAGE?

I am attempting to teach number theory from John Stillwell's Elements of Number Theory in the upcoming semester. There are two sections (5.7 and 5.8) which describe the diagrammatic method for the ...
8
votes
2answers
7k views

Show that there's a minimum spanning tree if all edges have different costs

Show that there's a unique minimum spanning tree (MST) in case the edges' weights are pairwise different $(w(e)\neq w(f) \text{ for } e\neq f)$. I thought that the proof can be done for example ...
5
votes
2answers
374 views

Number of all labeled, unordered rooted trees with $n$ vertices and $k$ leaves.

I've been trying to do the following exercise: The problem Find the number of all labeled, unordered rooted trees with $n$ vertices and $k$ leaves. I know that I should try to write an ...
2
votes
1answer
315 views

Number of rooted subtrees of given size in infinite d-regular tree

Currently I am reading a paper where the author states: [...] It is well-known that an infinite $D$-regular rooted tree contains precisely $\frac{1}{(D-1)u + 1} \binom{Du}{u}$ rooted subtrees of ...
3
votes
2answers
278 views

König's Infinity Lemma and Aronszajn Trees

I am working through the notes of my Set Theory lecture. There my professor wrote: 'Is there an uncountable $\kappa$ such that König's Infinity Lemma holds for $\kappa$? There are models where ...
2
votes
1answer
332 views

Evaluating 'combinatorial' sum

Help me please to calculate the following sum. I have seen such kind of formulas in the papers related to combinatorics, specifically 'trees'. I am curious how to calculate or approximate this sum: ...
8
votes
3answers
1k views

Number of spanning trees in a ladder graph

Let $L_n$ be the ladder graph formed from two $n$-vertex paths by joining corresponding vertices. For example $L_4$ is the following I have to find a recurrence $\langle t\rangle$ where $t_n$ is ...
9
votes
2answers
349 views

How can I prove the identity $2(n-1)n^{n-2}=\sum_k\binom{n}{k}k^{k-1}(n-k)^{n-k-1}$?

How can I prove the identity $$2(n-1)n^{n-2}=\sum_k\binom{n}{k}k^{k-1}(n-k)^{n-k-1}?$$ I know that the number of trees on $n$ vertices is $n^{n-2}$, and that a tree with $n$ vertices has $n-1$ ...
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
568 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 ...
2
votes
2answers
88 views

Introductions to posets on algerbaic structures (Everything I need to know about them)

I need a good and complete introduction to Tree-like orders and partial orders on algebraic structures with one operations. I accept basic texts too. I'm looking for free online texts mostly because ...
8
votes
2answers
3k views

Condition on degrees for existence of a tree

Here is what I need to prove: Let $d_1,d_2,...,d_n$ be a sequence of natural numbers (>0). Show that $d_i$ is a degree sequence of some tree if and only if $\sum d_i = 2(n-1)$. I know that: 1. ...
5
votes
2answers
2k views

How many vertices of degree 1 in a tree?

How many vertices of degree 1 are there in a tree with no vertices of degree more than 4? The only thing that I have right now is that the number of edges in a tree is n-1 where n is the number of ...
4
votes
2answers
145 views

Need a counter example for cycle in a graph

Could anyone give a counter example for that theorem : A graph G has exactly one vertex of degree $1$, then it contains a cycle. I am so confused. I wonder that may I give a counter example ...
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
64 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
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?
1
vote
1answer
81 views

Finding connected components of the graph [duplicate]

suppose that I have the following undirected graph with the following adjacency matrix showing if there is an edge between the nodes: \begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 ...
1
vote
3answers
70 views

The number of (non-equal) forests on the vertex set V = {1, 2, …,n} that contains exactly 2 connected components is given by

The number of (non-equal) forests on the vertex set V = {1, 2, ...,n} that contains exactly 2 connected components is given by $\sum_{k=1}^{n-1} {n-1 \choose k-1} k^{k-2} (n-k)^{n-k-2}$. I am unsure ...
1
vote
2answers
75 views

Can we construct from $[0,\omega_1)$ a space which is strictly-Frechet with no winning strategy in $G_{np}(q,E)$?

I have asked in here a question which tured out to make no sense. I think I have found the confusion and would like to try and rephrase my question: Let $E$ be a topological space, $q \in E$. ...
1
vote
3answers
1k views

Graph with cycles proof questions

Two questions I'm stuck with: If C is a cycle, and e is an edge connecting two nonadjacent nodes of C, then we call e a chord of C. Prove that if every node of a graph G has degree at least 3, then ...
0
votes
1answer
71 views

Graph theory and tree company

I appreciate anyone who answer this question and I anyone who design appropriate graph.
0
votes
1answer
103 views

How would I find a minimum weight spanning tree for W?

If I were to let $W$ be the weighted graph formed by taking a complete graph $K_5$ on five vertices 1, 2, 3, 4, 5 with the weight of each edge $\{x,y\}$ given by $(\{x,y\}) = x + y$, how would I find ...
0
votes
1answer
423 views

Explicit bijection between ordered trees with $n+1$ vertices and binary trees with $n+1$ leaves

What is an example of a direct bijection between ordered trees with $n+1$ vertices and binary trees with $n+1$ leaves?
2
votes
2answers
242 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 ...
6
votes
3answers
7k views

How to show that every connected graph has a spanning tree, working from the graph “down”

I am confused about how to approach this. It says: Show that every connected graph has a spanning tree. It's possible to find a proof that starts with the graph and works "down" towards the ...
4
votes
3answers
682 views

Counting $k$-ary labelled trees

The (full) binary counting tree problems gives the number of binary trees can be formed using $N$ nodes $T(n)= C_n$, where $C_i$ are the Catalan numbers. The recursion form is $T_n = ...
12
votes
2answers
1k views

Partition a binary tree by removing a single edge

The question is : B-3 Bisecting trees Many divide-and-conquer algorithms that operate on graphs require that the graph be bisected into two nearly equal-sized subgraphs, which are induced by a ...
2
votes
0answers
118 views

Bounding the global intersection of a family of sets

Suppose that we have a decision tree of height $r + 1$ that describes how to increment an $n$-bit integer in the range $[0, 2^n -1]$. That is, the internal nodes are labelled with a bit position that ...
2
votes
3answers
753 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 ...
1
vote
1answer
4k views

Number of Trees with n Nodes

I am struggling with a question that asks the number of trees that exist with x nodes and max level z. During my research I found that the number of binary trees with x nodes can be obtained by ...
1
vote
3answers
107 views

Comparison trees

You have 60 coins. You know that 1 coin is either lighter or heavier than the other coins. How many comparisons are needed in a worst case scenario to discover which coin is the false one and ...
7
votes
2answers
889 views

Is the graceful labeling conjecture still unsolved?

From the Wikipedia article on graceful labeling: ... A major unproven conjecture in graph theory is the Ringel–Kotzig conjecture, named after Gerhard Ringel and Anton Kotzig, which hypothesizes that ...
6
votes
4answers
364 views

What is the number of full binary trees of height less than $h$

Given a integer $h$ What is $N(h)$ the number of full binary trees of height less than $h$? For example $N(0)=1,N(1)=2,N(2)=5, N(3)=21$(As pointed by TravisJ in his partial answer) I can't ...
6
votes
7answers
458 views

EGF of rooted minimal directed acylic graph

I am trying to find the exponential generating function of directed minimal acyclic graphs (which I now call dag), where every non-leaf node has two outgoing edges. Context: A simple tree ...
4
votes
2answers
6k views

What does lg x mean? is it $\log_2 x$ or $\log_{10} x$ in binary trees

I'm a bit confused, $\log_{10} x = \log x $ right? I believe I've read somewhere that $\log_{2} x = lg x$ but some people say lg = $\log$. So what does lg really stand for? specifically when talking ...
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$ ...
3
votes
2answers
656 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 ...
3
votes
1answer
450 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
2answers
6k 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
1answer
100 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
2answers
475 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 ...
0
votes
2answers
250 views

Increase by one, Shortest path, changes the edges or not? [closed]

as i read the following text : "Let P be a shortest path from some vertex s to some other vertex t in a graph. If the weight of each edge in the graph is increased by one, P will still be a shortest ...
0
votes
2answers
2k views

Number of nodes in binary tree given number of leaves

How would I prove that any binary tree that has n leaves has precisely $2n-1$ nodes ? Given that a binary tree is either a single node "o" or a node with the left and right subtrees contains a binary ...
0
votes
2answers
2k views

About balanced and complete binary tree

I found this and I just couldn't verify it. How come it is true? The maximum number of nodes that a balanced binary tree with depth $d$ is a complete binary tree with $2^d-1$ nodes. Let say I have ...
3
votes
1answer
253 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. ...
3
votes
1answer
385 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 ...
2
votes
0answers
74 views

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 ...
2
votes
3answers
221 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
2answers
3k views

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