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

0
votes
0answers
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 ...
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
65 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
42 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
43 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 ...
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
71 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. ...
2
votes
1answer
45 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
57 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
24 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
28 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
382 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
10k 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 ...
2
votes
1answer
44 views

Finding DFS in undirected graph

Consider the following sequence of nodes for the undirected graph given below. a b e f d g c a b e f c g d a d g e b c f a d b c g e f A Depth First Search (DFS) is started at node a. The nodes ...
0
votes
1answer
27 views

Are subgroups of automorphism groups of trees direct product of symmetric, cyclic and dihedral groups?

My question is triggered by my confusion with the notation $\Psi$ in Constructive Approach to Automorphism Groups of Planar Graphs by Klavík et al. The notation $\Psi$ was first used expressing ...
0
votes
0answers
30 views

How to find the best-case and average-case number of comparisons performed by a comparison tree?

So I'm reviewing some material before a midterm tomorrow and I came across this question: ...
2
votes
1answer
26 views

Find depth of three node tree

I am trying to write a formula to find the depth of a three node tree and having issues doing it. Each node will have an index number going from top to bottom, left to right. It will look something ...
0
votes
2answers
36 views

Given a forest, adding k edges would result in a cycle Proof

Assume you have a forest with k connected components. Prove that if you added $k$ edges, you would obtain a cycle. I’m thinking these facts/theorems may be useful... In a forest, each component ...
0
votes
1answer
16 views

What's the complexity class of Sub-Polytrees isomorphism?

In terms of Subgraph isomorphism I believe Directed Acyclic Graphs (DAG's) are in the np-complete complexity class. What about Poly-trees (oriented trees)? These are DAG's where the possible paths ...
0
votes
0answers
19 views

Possible paths in trinomial tree with recombination

So I know that the number of possible paths to end up in node $i$ from the top in a binomial tree with recombination at step $n$ is equal to $\binom{n-1}{i-1}$. Is there a similar formula for the ...
2
votes
1answer
35 views

Graphs embeddable into tree like simplicial 2-complexes

A tree gives rise to a simplicial 1-complex. A tree like simplicial 2-complex would be simplicial 2-complex without any closed 2-subcomplexes (the analog of a cycle in graphs) and such that the ...
2
votes
0answers
48 views

Applications of Prüfer sequence

Reading a book about a graph theory I found out about Prüfer's sequences which converts a labeled tree of $n$ vertices into an array of $n-2$ numbers. I was actually pretty surprised by this and was ...
3
votes
1answer
80 views

How many trees on N vertices have exactly k leaves?

I need help on the topic of counting labeled trees (with its nodes numbered from 1 to N) with exactly k leaves. I have thought about surjective functions that return the father of a node, but I'm not ...
0
votes
1answer
30 views

Full 4-ary tree with 58 internal nodes

I'm not sure how to answer this question In a full 4-ary tree, there are 58 internal nodes. What is the number of leaf nodes in this tree? So a full 4-ary tree means every node has 0 or 4 ...
1
vote
0answers
30 views

Prove by induction a property of a tree graph

Prove by induction (and without the use of cycle definition) that if to delete a leaf vertex from a tree graph it will stay as a tree graph. I think Ive got it wrong but what I did is the following: ...
0
votes
1answer
29 views

Prove by induction the number of edges in a tree given the leaves.

Define a cs130A tree to be a single leaf node or an internal node (the root) connected to two disjoint subtrees, which are themselves cs130A trees. Prove by induction that for all cs130A trees the ...
0
votes
0answers
31 views

How to find total node in tree

I wonder that how to generalize formula of tree. For example, let T be a tree and height of this tree "h" generated in a way that starting from the root node with h children, the branch factor ...
0
votes
0answers
18 views

Get sister node of all nodes given edge list

I've run into this problem writing some code to do some analyses on phylogenetic trees in Python. Let's say I have a tree: ...
1
vote
1answer
28 views

Algorithm for equality of trees of restricted depth

Are there any efficient algorithms to decide whether two trees of limited depth, where all nodes have a finite number of childs, are equal interpreted as finite sets with the leaves the "atomic" ...
0
votes
1answer
20 views

What is the amount of non-isomorphic trees of order n with a maximum incidence of 4?

It's a graph-theory model of the theoretical amount of possible non-cyclic alkanes isomers. I can't find a way to compute it? Any hints appreciated.
0
votes
1answer
116 views

Tree question proving [closed]

Let $T_1$ be a tree of height $h$ such that the root has one child, and the branching factor at each level is one more than the branching factor at the previous level. Thus, the root has one child, ...
0
votes
0answers
54 views

Can Collatz's problem be used as a pseudo random prime sieve?

If you take the concept of $3x+1$, $\dfrac{x}{2}$ and starting at 2, create a tree. On the left nodes you apply the $3x+1$. On the right nodes, if the parent node is even apply the $\dfrac{x}{2}$. ...
2
votes
1answer
529 views

Proof involving maximum weight of edge in minimum spanning tree

Let $G$ be a minimum spanning tree of a complete graph. Let $e$ be the maximum weight edge in $G$. I'd like to proof that given any other spanning tree $G'$ of this graph, being $j$ the maximum weight ...
1
vote
1answer
47 views

Encoding the answers to questions somewhere in a binary tree

I have a sequence of binary questions $(U_1,\dots, U_N)$ with some distribution. I know the answer to $n\leq N$ (mod-)adjacent questions, and want to convey this knowledge with as few bits as ...
2
votes
2answers
75 views

In a full binary tree of depth $d$, what is the number of pairs of vertices at distance $t$ from each other?

I can come up with a dynamic-programming-type program to compute this number, but I am wondering if a nice closed form formula is known. By "full" I mean a binary tree where every vertex is within ...
0
votes
0answers
10 views

Proof by induction that $\sum \limits _{i=1} ^n d^{-l_i} = 1$ sentence in a full tree [duplicate]

How do I prove by induction that $\sum \limits _{i=1} ^n d^{-l_i} = 1$ where: $d$ = the number of children of each node; $n$ = the number of leaves; $l$ = the depth of each leaf $l_1, \ldots, l_n$? ...
0
votes
1answer
24 views

Every simple graph has at least $n-k$ edges.

From here on, $n$ will denote the number of vertices and $k$ will denote the number of connected components of the graph in question. Theorem. Let $F$ be a forest, then $F$ has $n-k$ edges. ...
0
votes
2answers
46 views

There are $n^{n-3}$ numbers of trees with named edges - how to proof?

How to proof that there are $$ n^{n-3} $$ trees with $n$ (unnamed) vertexes and $n-1$ named edges: $\left\{1, 2, 3, 4, ..., n-1\right\}$?
1
vote
1answer
135 views

Location of two “centers” in a tree

This problem came up during a recent (and already finished) coding competition on Hackerrank, I was wondering if someone stumbled upon a proof. [This question is my paraphrasing of the original] ...
0
votes
1answer
13 views

Finding a unique tree for given in order and postorder traversals

I just encountered a problem to find a tree for given inorder and postorder traversals.Can anybody elaborate the same using an example ?
1
vote
1answer
446 views

Prove that a graph cannot have two distinct spanning trees

Prove that a graph cannot have two distinct spanning trees. I'm confused with this proof. More so that I think I'm confused as what distinct in this context means? Initially I thought it was that ...
0
votes
0answers
43 views

Help with functions of vertex sets

Let vertex sets $V_1$ and $V_2$ be defined by $V_1= \{1, 2, 3\}$ and $V_2 = \{a, b, c \}$. Let $E_1 = \{ \{ 1, 2\}, \{2, 3\} \}$, and let $E_2 = \{ \{a, b\}, \{b, c\} \}$ be the edge sets ...