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

4
votes
4answers
997 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 ...
3
votes
1answer
43 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 ...
0
votes
0answers
18 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 ...
2
votes
1answer
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$ ...
0
votes
2answers
49 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 ...
1
vote
1answer
58 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 ...
0
votes
1answer
39 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 ...
0
votes
2answers
33 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.
0
votes
1answer
54 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 ...
1
vote
1answer
47 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 ...
1
vote
1answer
14 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 ...
1
vote
0answers
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 ...
2
votes
1answer
62 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 ...
1
vote
0answers
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 ...
0
votes
2answers
27 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: ...
1
vote
1answer
57 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 ...
1
vote
1answer
35 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 ...
3
votes
1answer
39 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 ...
0
votes
1answer
40 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 ...
0
votes
2answers
27 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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
2
votes
2answers
88 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 ...
1
vote
3answers
98 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\\ ...
0
votes
2answers
29 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
0
votes
0answers
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 ...
2
votes
1answer
107 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 ...
1
vote
1answer
43 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 ...
0
votes
0answers
24 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 ...
1
vote
1answer
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 ...
1
vote
1answer
64 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 ...
2
votes
1answer
37 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 ...
1
vote
0answers
41 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 ...
0
votes
0answers
26 views

Prove a connected graph has n-1 edges and has no cycle

I am new to proving graph theory and would like some help on how to prove these. I am required to prove both directions because this is an "If and only if" question. A. G is a tree (Connected and ...
1
vote
1answer
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 ...
1
vote
2answers
65 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 ...
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 ...
0
votes
0answers
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. ...
1
vote
1answer
43 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, ...
2
votes
1answer
56 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 ...
0
votes
1answer
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 ...
0
votes
0answers
13 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 ...
3
votes
3answers
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 ...
1
vote
1answer
23 views

Need combinatorial formula

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 ...
0
votes
1answer
27 views

Proof of Mutually Inclusive Tree Properties

I don't know if that's the most accurate title. I'm trying to prove that one property of trees implies another without using any of the other properties. This is for homework. But I'm really just ...
1
vote
1answer
380 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. ...
1
vote
0answers
23 views

Prove that a connected graph with $n$ vertices is a tree iff it has $n-1$ edges. [duplicate]

What are different ways of proving this theorem, using different definitions for a tree (e.g. maximally acyclic graph, minimally connected graph, there's a unique path between any two vertices, etc.)
0
votes
1answer
39 views

Depth first search tree in an undirected graph $G$.

Let $T$ be a depth first search tree in an undirected graph $G$. Vertices $u$ and $ν$ are leaves of this tree $T$. The degrees of both $u$ and $ν$ in $G$ are at least $2$. which one of the following ...
0
votes
1answer
23 views

There are at least 22 vertex-disjoint paths between every pair of vertices?

$G$ is a graph on $n$ vertices and $2n−2$ edges$.$ The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for $G?$ For every subset of $k$ ...
7
votes
2answers
9k views

Determining Ambiguity in Context Free Grammars

What are some common ways to determine if a grammar is ambiguous or not? What are some common attributes that ambiguous grammars have? For example, consider the following Grammar G: $S \rightarrow ...