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

193 views

### Find tree diameter or center

I want to find center in a graph that doesn't have cycles. I heard, that this is how I find a diameter: Take random vertex A Find such vertex B, that distance to it is maximal Find such vertex C, ...
34 views

### What function describes this problem of every possible breeding of a set of dogs?

If I have n dogs [a, b, c, ...], and I want to breed them in every possible combination (every possible binary tree made of ...
25 views

### Bounding the probability of landing at any point for a random walk on a tree

Fix $m\geq 2$ and a vertex $v_0$ in an infinite connected $2m$-regular tree, (in other words, the Cayley graph for the free group on $m$ generators) and consider the random walk on the tree starting ...
24 views

### Are these tree-related concepts redundant?

I've been doing a lot of work with trees lately, and have developed vocabulary that I've been using to describe them. Not having that strong of a background in graph theory, it occurred to me that I ...
23 views

### Cuts on complete binary trees

Claim : Suppose we have a complete binary tree of height $h$. We introduce a cut to partition this tree into two sets of vertices of size $x$ and $2^h - 1 - x$ for some $x$. For any $x$, we define the ...
41 views

### How Many Ways to Construct Trees With No More Than 4 Connections per Vertex.

I am a high school student (so sorry if my thinking is way off) with a problem related to chemistry essentially dealing with the number of ways you can arrange carbon atoms in a alkane. I saw that ...
1k views

### In binary tree, number of nodes with two children when number of leaves is given

For a binary tree what is the number of nodes with two children when the number of leaves is 20? I know that for complete binary tree, when the number of leaves is x then the number of internal nodes ...
46 views

### Bona “A Walk Through Combinatorics” Problem 10.29

Given a tree $T$, define the "total distance" of a vertex $v$ by $$td(v) = \sum_{w \in V(T)} d(v,w),$$ where $d(v,w)$ is the number of edges in the unique $vw$-path in $T$. In any tree, the value of ...
20 views

### Parsing a definition concerning trees and tuples

Definition: Let $T$ be a tree. Given a set $X$, we define a $T-tuple$ of elements of $X$ to be a function x: $T\rightarrow X$ Alternatively, we sometimes refer to a $T$-tuple as a tree of elements ...
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$ ...
85 views

### Relation between vertices and edges in a tree?

I know the following relation between vertices and edges of a tree - Any connected graph(undirected) with n vertices and $n-1$ edges is a tree. My question is suppose I have an undirected connected ...
64 views

### Closed Form for Sum of Nodes in Binary Tree

Consider a binary tree $T$ with nodes in $\mathbb{Z}^+$, where level $k$ of $T$ contains nodes $2^k$ through $2^{k + 1} - 1$. I have some problems that involve visiting the nodes of $T$ in their ...
40 views

### Finding log base 2 of a number .

I generally visualize $\log_{2}$ of a number as an inverted binary tree, for example to know how many times 8 needs to be divided to become one I image a inverted tree of 8 leaves then, the level ...
36 views

### How many vertices are of degree 1?

Given $T(n,m)$ which contains only vertices of degree 1 and 3. How many vertices are of degree 1? Is it similar to compute in thi link? How many vertices of degree 1 in a tree? Thank you.
56 views

### A little bit more difficult problem regarding rooted plane trees

A question regarding rooted plane trees bothers me. We know that the number of rooted plane trees with $n$ nodes equals to $n-{th}$ Catalan number, that is $|Tn| = Cn$. But what is this number if we ...
56 views

### Kelly's Proof Of Reconstruction Conjecture For Trees

The vertex reconstruction conjecture states that a graph on n>2 vertices can be discovered from only knowing its proper induced subgraphs. Kelly proved this for trees in 1961. I saw his proof and I ...
16 views

### Number of Plane Oriented Recursive Trees

The number of plane oriented recursive trees is $(2n-3)!!$ I understand that given a vertex $v$ with $k$ successors, there are $k+1$ ways to attach a new vertex to create a new tree of size one ...
27 views

### Entropy of a dictionary

I have an english dictionary (a file that contains a list of words) and I want to calculate: given a path tree (a word), measure $H(C_{l+1}|C_l=c_l, C_{l-1}=c_{l-1}, ...)$ for a few levels of the ...
73 views

### Set Theory: Tree Property

Why does the tree property hold for regular cardinals but not singular cardinals? (I.e. There exists a tree of height $\kappa$ with countable levels and no cofinal branch for $\kappa$ a singular ...
16 views

### Example of a Shortest Path Tree for a Directed Graph that contains a directed cycle of negative length

My colleague says this is possible, but I don't understand how. I know it is necessary for the directed Graph to contain no negative cycles in order to prove that the Shortest Path Tree exists. So I ...
42 views

### Black Depth in Red-black Tree?

Wikipedia's Red-black tree states the last property of a Red-black tree: Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes. Some definitions: ...
60 views

### Depth-first search binary tree problem

Professor Hastings has constructed a 23-node binary tree in which each node is labeled with a unique letter of the alphabet. Preorder and postorder traversals of the tree visit the nodes in the ...
36 views

### Relationship between ordered trees and integer partitions

I've found that there is a bijection between integer partitions and ordered rooted trees with roots of degree 2 or greater. The rigorous proof is complicated, but the gist of it is that you take the ...
44 views

### Must a minimum weight spanning tree for a graph contain the least weight edge of every vertex of the graph?

Currently learning about spanning trees and using Kruskal's algorithm and I was wondering whether a minimum weight spanning tree of a weighted graph must contain one of the least weight edges of every ...
64 views

### Finding a minimum spanning tree in a graph with edge weights in {1,2,.., R} where R is constant

I have recently been doing some research into algorithms for finding minimum spanning trees in graphs, and I am interested in the following problem: Let G be an undirected graph on n vertices with m ...
34 views

### Proving that the number of full nodes + 1 is equal to the number of leaves in a nonempty binary tree

I am looking at the proof of this and I am so completely lost on where they are getting some of the expressions. Here is the proof: Consider that $N$ is the number of nodes, $F$ is the number of full ...
30 views

### Set Theory: Graphs and $k$-Colorings

Let $G = (V, E)$ be a graph with $V = \omega$. Show that if for all $n < \omega$, the graph $G_{n} = (n, E \cap [n]^{2})$ is $k$-colorable, then $G$ is $k$-colorable. I know how to prove this ...
31 views

### Is there a way to obtain exactly 2 quarts in the 8-quart or 5-quart pitcher?

Suppose we are given pitchers of waters, of sizes $12$ quarts, $8$ quarts, and $5$ quarts. Initially the $12$ quart pitcher is full and the other two empty. We can pour water from one pitcher to ...
115 views

### Determine depth of node in perfect binary tree with depth-first in-order enumeration

Given a perfect, balanced and complete binary tree of height H with its nodes enumerated depth-first in-order, what formula can you use to calculate the depth of a node given its index in constant ...
103 views

### Computing shortest path including specific edge

Consider the weighted undirected graph with $4$ vertices, where the weight of edge $\{i, j\}$ is given by the entry $W_{i, j}$ in the matrix $W$. W = \begin{bmatrix} 0&2&8&5\\ 2&0&...
32 views

### Show that a simple connected graph G contains a cycle if and only if it contains more than one spanning tree.

This doesn't seem like a huge leap to prove this statement. However, I'm having trouble writing out a proof formally. I understand that I need to prove two directions. Thanks for your help
10 views

### Clustering via U(-W)PGMA

Given paiwise distance between 5 taxa: {a,b,c,d,e} 0 3 12 12 9 - 0 13 13 10 - - 0 6 7 - - - 0 7 - - - - 0 Calculate evolutionary tree, using UPGMA and ...
115 views

### Proving the smallest number of leaves in a tree

What is the smallest number of leaves in a tree with two vertices of degree 3, one vertex of degree 5 and two vertices of degree 6? I've come up with what I think is the correct drawing containing ...
45 views

### Can there be a walk between a tree and it's subgraph formed by removing an edge from the tree?

Say T is a tree and e is an edge in T. H is a subgraph of T obtained by removing edge e in T. Can there be a walk in H that connects to T? Edit: I've been trying to work it out, and what I have is ...
27 views

### Graph containing every tree

Let $G$ be a graph on $n$ vertices of size at least $(k-1)n - {k\choose 2} +1$. Show that $G$ contains all trees of order $k+1$. What I really would like to show is that there is a subgraph of ...
23 views

### How many types of distinct Binary Tree can be formed with a height of h?

How many types of distinct Binary Tree can be formed with a height of h? if we only know the height of binary tree, and we regard root-left and root-right as the same tree structure, this means if the ...
66 views

### $G’$ be the graph constructed by squaring the weights of edges in $G$.

Let $G$ be a weighted graph with edge weights greater than one and $G’$ be the graph constructed by squaring the weights of edges in $G$. Let $T$ and $T’$ be the minimum spanning trees of $G$ and $G’$,...
52 views

### Adding one edge to a tree creates exactly one cycle

I am having trouble proving this question. I am also having trouble visualizing how this works, using a binary tree as an example. I don't see how adding an edge creates one cycle? Isn't a cycle ...
44 views

### Determine Huffman Tree Depth Using any combinactory ways?

I see this link for determining depth (height) of Huffman tree, but not useful for me. My Question is: Knowing the frequencies of each symbol, is it possible to determine the maximum height or ...
16 views

### Number of full orderings in a full binary tree.

I'm trying to resolve an example from book. T = (V, E) is a full binary tree, and |V| = n. Show that there exist ...
83 views

### Number of binary search tree of height $6$

The number of ways in which the numbers $1, 2, 3, 4, 5, 6, 7$ can be inserted in an empty binary search tree, such that the resulting tree has height $6$, is______ . Note: The height of a tree with a ...
8k 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 by ...
33 views

### Prove that for every two graphs G & H as explained, $\tau(H)=k^{v-1}\tau(G)$

A spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. Suppose that for every graph $G$, $\tau(G)$ is the number of spanning trees of G. ...
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, ...
58 views

### Shortest Path Via Dynamic Programming Formulation?

We have a directed Graph $G=(V,E)$ with vertex set $V=\left\{ 1,2,...,n\right\}$. weight of each edge $(i,j)$ is shown with $w(i, j)$. if edge $(i,j)$ is not present, set $w(i,j)= + \infty$. for ...
21 views

### Proving statement for a tree-graph theory

So i need help with this: Let T be a tree. And degree of every vertice is an odd number. So i need to prove that there is an odd number of paths in that tree. So i basically need to prove that there ...
18 views

### How many degrees of freedom exist in an agglomerative hierarchical clustering?

The computational complexity of generating an agglomerative hierarchical clustering from n vectors is $O(n^2)$ (calculating the pairwise distance matrix) dendrogram example However, the total number ...
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 ...
Let we have a forest $F_n(P)$ with $n$ nodes defined by set $P$ of all pairs $\{\text{father}, \text{son}\}$. For instance $P=\{\{1, 2\}, \{3, 4 \}, \{1, 3 \}\}$ defines a forest $F_5(P).$ Let \$...