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
1answer
9 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
10 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
32 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
11 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
23 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
0answers
23 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
19 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
16 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
21 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
19 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
15 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
12 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
26 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
49 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
25 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
19 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
20 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
23 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
106 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
49 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
59 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
22 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
43 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
17 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
1answer
9 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 ?
0
votes
0answers
41 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 ...
0
votes
1answer
27 views

how can i Prove that by adding one edge to G you create a cycle in G?

Any one help me to show the prove for this? Let the undirected graph G = (V, E) be a tree. Prove that by adding one edge to G you create a cycle in G.
1
vote
1answer
128 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
2answers
23 views

an intuition for $\sum {\frac{(n-2)!}{k_1!k_2!…k_n!}}=n^{n-2}$

in studying about Graphs I've faced to the problem which says that the number of trees on n points is $n^{n-2}$. In the solution manual of the book the problem is reduced to the summation $\sum ...
0
votes
2answers
30 views

The Hand Shaking Lemma

In any graph G=(V,E) [the hand shaking lemma] $$ \sum_{v \in V} \deg(v) = 2 |E| $$ (original at http://i.stack.imgur.com/af4en.png) where |E| donetes the number of edges I alredy tried to count ...
0
votes
0answers
37 views

In code sequence of tree replace every 0 with two 0 and every 1 with two 1 will it be tree again?

So i have this question If yes, explain how the structure of this graph depends on the structure of the original subgraph. In not, give an example of such sequence. I just want to be sure if i'm right ...
0
votes
0answers
14 views

Proving the treewidth of a graph is the maximum treewidth of the connected components

We have a graph $G = (V,E)$ and $C$ is the set of connected components of G. I want to prove that $tw(G) \geq $ Max $tw(C)$ where tw is the treewidth. I know the out sketch of the proof is to take ...
2
votes
2answers
67 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
1answer
23 views

Why does no minimal spanning tree contain the longest edge of a circuit?

Let $G=(V,E)$ be a graph with lengthfunction $l:E\rightarrow\mathbb{R}$. How do I prove that if $e$ is a line in a circuit $C$ such that $l(e)>l(f)$ for all $f\in C$ with $f\neq e$, then we get ...
1
vote
1answer
24 views

prooving graph with no cycles and |V | = |E| + 1 is a tree.

My assignment is to prove that G = (V, E) is a tree if and only if |V | = |E| + 1 and G has no cycles. However, I am having some trouble doing just that. We defined a tree as a graph which is ...
1
vote
1answer
71 views

Finding connected components of the graph [duplicate]

suppose that I have the following undirected graph with the following adjacency matrix showing if there is an edge between the nodes: \begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 ...
0
votes
0answers
176 views

DFS tree of a $K_{1,3}$-free connected graph

Let there be $G=(V,E)$ a connected, $K_{1,3}$-free graph. (A $K_{1,3}$-free graph is a graph which has no 'claw' structures in it, where a claw structure refers to a vertex that has $3$ edges ...
2
votes
1answer
39 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
16 views

Structual induction on mirror(mirror t) = t

I have to prove that for all binary trees $t$ the following property holds: $$mirror(mirror(t))=t$$ $mirror(t)$ is defined as: $$mirror(t) =\begin{cases} Empty, & \text{if $t$ is Empty} \\ ...
0
votes
2answers
35 views

Find a minimum spanning tree using Prim's algorithm

I have the adjacency matrix: Where we have nodes a to g, and with their respective weights x means symmetry, and the spaces left out are positive infinity $$\begin{array}{c|c|c|c|c|c|c|c|} & ...
0
votes
0answers
17 views

Finding the smallest decision tree of a Boolean function

From Computational Complexity: A Moden Approach, A decision tree is a model of computation used to study the number of bits of an input that need to be examined in order to compute some ...
-1
votes
1answer
91 views

Prove that at least one edge of minimum weight is in the minimum spanning tree of a graph.

Let G be a connected graph with edge weights w. Suppose T is a minimum spanning tree of G. Let X be any nonempty proper subset V(G). Prove that at least one edge of minimum weight in the cut induced ...
0
votes
1answer
29 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
0answers
20 views

Name for a Type of Tree Diagram (Simplified Family Tree)

I just want to know what the name for this type of tree diagram is. In order to be clear, I want terminology like "binary tree" or something like that (but a name which actually applies). If I ...