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

6
votes
2answers
3k 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 ...
2
votes
1answer
232 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
234 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
328 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: ...
9
votes
2answers
338 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
536 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
79 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 ...
2
votes
1answer
193 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 ...
7
votes
2answers
2k 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. ...
4
votes
2answers
90 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
67 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
52 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
6k 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
2answers
73 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
66 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
375 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?
4
votes
3answers
469 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 = ...
4
votes
3answers
5k 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 ...
12
votes
2answers
916 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 ...
4
votes
2answers
224 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 ...
4
votes
3answers
884 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 ...
2
votes
3answers
599 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
2answers
203 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 ...
1
vote
1answer
3k 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 ...
7
votes
2answers
759 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
7answers
400 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 ...
5
votes
1answer
98 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 ...
4
votes
2answers
223 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
533 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
73 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
390 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
87 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
1k 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 ...
6
votes
4answers
151 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 ...
5
votes
2answers
1k 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 ...
3
votes
1answer
243 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
3answers
120 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 ...
1
vote
1answer
39 views

Existence of infinite subsequence of trees with a subtree contained in the sequence

Assume a statement: For every infinite sequence of rooted trees $\{T\}_{i=0}^\infty$ there is an index $j\geq0$ such that there are infinitely many trees in $\{T\}_{i=0}^\infty$ which contains ...
1
vote
1answer
122 views

Complete Binary Tree [closed]

A balanced binary tree is a full binary tree in which every leaf is either at level l or l-­1 for some positive integer l. The set of balanced binary trees is defined recursively by: Basis step: A ...
1
vote
2answers
700 views

graph theory and forests

We were given an this question in my class: Prove that a forest with n vertices and m components has n-m edges using induction on m. Induction is not my strongest point and I was wondering if anyone ...
1
vote
1answer
546 views

Prove that in every tree, any two paths with maximum length have a node in common.

Prove that in every tree, any two paths with maximum length have a node in common. This is not true if we consider two maximal (i.e. non-extendable) paths. What does this even mean?
1
vote
3answers
2k views

Sufficient conditions on degrees of vertices for existence of a tree

I am answering a question for an assignment, but I am not sure if my proof is valid, can someone look at it for me? the question: "there is a tree with $p$ vertices. If $d_1, d_2, \dots , d_p$ are ...
0
votes
1answer
181 views

Let $G$ be a connected graph, then $G$ is a tree iff $G$ has no cycles

Prove the following: Let $G$ be a connected graph, then $G$ is a tree $\iff$ $G$ has no cycles. $\Rightarrow$ If $G$ is connected and a tree then by the definition of tree it has no cycles. ...
0
votes
1answer
54 views

Existence of infinite subsequence of trees assuming two tree operations

Assume two operations on rooted trees: contract an edge: choose an edge $E$, join two vertices adjacent to $E$ grow a leaf: choose any vertex and connect it to a new leaf Starting with any rooted ...
0
votes
1answer
80 views

Increase by one all edges, Min-Cut, changes or not?

My Friends, as i ask a new question recently, Increase by one, Shortest path, changes the edges or not? i want to ask a related question as a new post Suppose we have a Graph G in which weight ...
0
votes
1answer
72 views

Number of distinct Binary tree formed with respect to height h

How many types of distinct Binary Tree can be formed with a height of h? assuming height starts from 0 when the tree has only the root. example: if the height of tree is 1 then root-leftchild ...