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

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
2answers
26 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 ...
0
votes
1answer
38 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 ...
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 ...
0
votes
2answers
28 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
2
votes
2answers
86 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 ...
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
105 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 ...
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
40 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
64 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 ...
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, ...
1
vote
3answers
97 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
1answer
20 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 ...
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
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 ...
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
25 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
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
0answers
22 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
25 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
28 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
24 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
31 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
16 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
0answers
43 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
67 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 ...
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
24 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
1answer
25 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 ...
0
votes
0answers
29 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
27 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
115 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
53 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}$. ...
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 ...
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$? ...
2
votes
1answer
31 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 ...
0
votes
2answers
45 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\}$?
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. ...