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
2answers
112 views

In a tree, is there always a sink where every longest path ends in?

Let $T$ be an undirected tree. Can we always find a leaf vertex $s$ such that every longest path of $T$ has its other endpoint in $s$? It's easy to see that every longest path passes through the ...
1
vote
1answer
41 views

Connection Trees and Partition

In our lecture we just had a short excursion into the tree-world. But the professor mentioned some connection between Ramsey and König's Infinity Lemma (If $T$ is a tree of hight $\omega$ with all ...
1
vote
2answers
261 views

Draw Graph from distance to other nodes

I have a matrix that shows the distance from a node to another node: A B C D E A 0 2 4 3 1 B 2 0 2 1 3 C 4 2 0 2 1 D 3 1 2 0 2 E 1 3 1 2 0 To clearify: The 2 ...
1
vote
1answer
543 views

What is the length of the Minimum Spanning Tree

What is the length of the Minimum Spanning Tree for the following weighted graph? Solution. The length of any minimum spanning tree for this graph (and there is more than one) is 60. The graph and ...
1
vote
1answer
119 views

spanning trees of graphs

Assume we have a simple connected graph G, how would start a prove of the following statement? For any edge of G, there is a spanning tree of G that contans it. I have decided that this is a true ...
1
vote
1answer
281 views

For BSP generation, How to intersect or locate a triangle with a plane defined by another triangle?

I've hit a stumbling block in my project to draw the Utah teapot. I want to generate a binary space partition tree of a set of 3D triangles. The decision step in the recursive tree-construction ...
1
vote
2answers
181 views

existence of a spanning tree

Let $T$ and $T'$ be two spanning trees of a connected graph $G$. Suppose that an edge $e$ is in $T$ but not in $T'$. Show that there is an edge $e'$ in $T'$, but not in $T$, such that ...
1
vote
1answer
37 views

If $G$ is a tree and $\forall v_1, v_2 : dist(v_1, v_2)$ is even, where $v_1, v_2-$ are leaves $\Rightarrow \exists!$ a maximal independent set.

If $G$ is a tree and $\forall v_1, v_2 : dist(v_1, v_2)$ is even, where $v_1, v_2-$ are leaves of the tree $\Rightarrow \exists!$ a maximal independent set. Give some clue please! Thanks anyway!
1
vote
1answer
293 views

Prove equivalence of conditions for a tree

Let $G=(V,E)$ denote a nonempty graph. Show that the following conditions are all equivalent. $G$ is a tree. Any two vertices in $G$ can be connected by a unique simple path. $G$ is ...
1
vote
1answer
175 views

Existence of a spanning tree with certain properties

Let $\Gamma$ be a finite, connected graph (multiple edges between two vertices are allowed). Fix a vertex $u_0\in V\Gamma$. Does there exist a maximal subtree (i.e., a spanning tree) $T\subset\Gamma$ ...
1
vote
1answer
218 views

Depth distribution of normalized decision trees?

Lets work with the following inductive definition of a decision tree: 1) $\bot$, $\top$ are decision trees. 2) If $x_i$ is a variable and $T_0$, $T_1$ are decision trees then $(\lnot x_i \land T_0) ...
1
vote
2answers
585 views

Graph - Minimum spanning tree

I have a graph with a cycle ($v_1,\ldots,v_k, v_1=v_k$). Claim: If there is a cycle with 2 edges of the same weight, and they are the heaviest edges in this cycle, then there is more than one Minimum ...
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" ...
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] ...
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 ...
1
vote
3answers
28 views

Finding element in binary min-heap

I am trying to answer two questions. Can some one check my answer and let me know if its correct or not? Question 1: Which locations in a binary min-heap of n elements could possibly contain the ...
1
vote
1answer
27 views

Prove that minimum spanning tree is a tree

From the the Wikipedia page Minimum spanning tree: A minimum spanning tree is a spanning tree of a connected, undirected graph. It connects all the vertices together with the minimal total ...
1
vote
1answer
21 views

Set of edges not contained in any spanning tree

The question is as follows: Prove that in a graph $G$ a set of edges $X$ which is not contained in any spanning tree is a cycle (or possibly an edge disjoint union of cycles). My thoughts: Proceed by ...
1
vote
1answer
51 views

What is a “linear chain” in Graph Theory?

What is a linear chain in the context of graphs and trees? For example: a topological sort forms a linear chain What does a linear chain mean in the example above? Another example from ...
1
vote
1answer
50 views

A tree has a root, leaves, and what?

The root of a tree is special, in that it has no parents. The leaves are special in that they have no children. The other nodes each have exactly one parent and more than zero children. Is there a ...
1
vote
1answer
42 views

how to define a “directed spanning tree”?

In all my books and articles about "graph theory", I didn't find the definition of "directed spanning tree". Could you please give this definition and the reference? How to judge if a directed graph ...
1
vote
1answer
50 views

How to determine lexicographically the smallest Prüfer-Code of a spanning tree?

First, lexicographically the smallest means e.g. 112 < 121 and 121 < 211. EDIT: Then how to determine the minimal Prüfer-Code of a spanning tree from the given graph: Should I first find ...
1
vote
1answer
61 views

Tree-related problem, counting leafs

I am studying Graph Theory right now, and I have solved tons of problems so far. However, I got a tree-related problem, where it asks me to prove that a tree, in which maximum node degree is 6, the ...
1
vote
1answer
17 views

Get number of vertices when number of internal vertices is known ofr a full binary tree

But I can find a counter example: * / \ * * / \ / \ * * * * Here $k = 2$, but number of vertices is 6, and number of terminal ...
1
vote
1answer
225 views

Remove edge from tree, number of vertices

Prove that if $T$ is a tree on at least $k+1$ vertices and max degree at most $d$, then there exists an edge $e$ such that the removal of $e$ causes $T$ to split into two trees where at least one of ...
1
vote
1answer
45 views

Determine if there is a node in a binary postorder anti-sorted tree with key $k$

A binary postorder anti-sorted tree is a binary tree for which the post-order traversal gives the keys that are saved at the nodes of the tree in descending order. Present a pseudocode for the most ...
1
vote
1answer
65 views

Rotations after inserting element in AVL-tree

We want to insert $58$ at the following AVL-tree and then we have to make rotations so that the tree is balanced. According to my notes, we are at the case RL (The first edge leads to the right and ...
1
vote
1answer
52 views

If the inorder traversal of a binary tree produces ordered output, is the tree a binary search tree?

Given a binary search tree, it's easy to see that the inorder traversal returns values from the underlying set in order (according to the comparator that set up the binary search tree). My question ...
1
vote
1answer
152 views

How to check homeomorphic embedding relation programmatically?

This is a follow up to this question and Deedlit's answer. I'm looking for a precise definition of the "hem?" (tree A homeomorphically embeddable in tree B?) relation, preferably in terms of a ...
1
vote
1answer
516 views

Proving number of edges in F = n - k

So if we let F = (V,E) be a forest with n vertices and k connected components (trees), how can I prove that the number of edges in F = n - k ? I was thinking of using induction, but I'm super lost. ...
1
vote
1answer
301 views

Proof: How many edges need be removed from this graph to produce the spanning tree?

Assume the graph,$G$ has the degree sequence $6,4,4,3,3,3,3,2,2$. How many edges must be removed from $G$ to produce the spanning tree $T$? We can construct this graph using Havel-Hakimi's ...
1
vote
1answer
56 views

How to prove that at Complete Binary Tree (CBT) at height $h$ we have $2^h$ leaves

I try to prove it by induction, please tell me if I'm right... The induction assumption - For every CBT at height $h$ there is $2^h$ leaves. The base of the induction is right (I'm writing this proof ...
1
vote
1answer
29 views

Height of the tree : $T(n) = 4T(n/4)+2T(5n/8)+T(n/8)+\theta(1)$

Let the tree described by $T(n) = 4T(n/4)+2T(5n/8)+T(n/8)+\theta(1)$ Can someone explains why the height is $\log_{8/5}{n}$ I don't know how to proceed
1
vote
1answer
89 views

$k$-connected graphs containing trees

I've encountered the following problem in the book "Graphs and Digraphs" and I'm not sure how to do it. Show that every $k$-connected graph contains any tree of order $k+1$ as a subgraph.
1
vote
1answer
237 views

Complete Binary Tree [closed]

A balanced binary tree is a full binary tree in which every leaf is either at level l or l-­1 for some positive integer l. The set of balanced binary trees is defined recursively by: Basis step: A ...
1
vote
1answer
48 views

Graph theory: tree vertices

How can I calculate the number of vertices of a tree knowing he has 33 vertices of degree 1, 25 vertices of degree 2, 15 vertices of degree 3 and all other vertices of grade 4?
1
vote
1answer
73 views

Iterations of Pascal's Identity

Pascal's Identity states that $n \choose k$ = $n-1 \choose k-1$ + $n-1 \choose k$ since if one element is separated from the rest we can claim that either it is chosen (resulting in $k-1$ elements ...
1
vote
1answer
63 views

Prove that every subgraph of forest has at least one vertex of degree < 2

So I know that a forest is a graph that has no cycles. This is what I had in mind: Assume that we have the subgraph T, which has two options: to be connected or not. if it's connected it has to be a ...
1
vote
2answers
69 views

When trees are the answer: what is the question?

For which optimization problems are (abstract) trees the best solution? E.g. binary search trees are somehow optimal data structures for quick search. But why for example do botanic trees grow as ...
1
vote
2answers
68 views

Spanning Tree, Network Modelling

I'm developing some software at the moment for voip communications (broadcast style comms, think ventrilo or teamspeak) between multiple users without a central server (send voice to server, server ...
1
vote
1answer
50 views

Proving this tree definition with pigeonhole principle

I am studying the following tree definition: Let $T$ be a finite set and a function: $p: T \mathbin{\backslash} \{r\} \rightarrow T$. Then, $(T,p)$ is a tree if and only if, for all $x \in T, p^k(x) ...
1
vote
1answer
61 views

Some questions about first-order logic (arising from a book by Raymond M Smullyan)

Recently, I got confused when reading a book about first order logic written by Raymond M smullyan. Chapter 1 page 9:When introducing the notion "Formation tree", smullyan define a formation tree for ...
1
vote
1answer
154 views

The complement of spanning trees is covered by a union of cycles

Is it true that in any (connected) graph $G=(V,E)$, if $T$ is a spanning tree than its complement (edge-wise) may be covered by a union of disjoint cycles? Here's a non-complete attempt to prove this ...
1
vote
1answer
69 views

Variance of Height of Tree

What is the asymptotic variance of the height of rooted plane trees (ie rooted, unlabelled, ordered trees with unbounded node degree) and of ordered binary trees (ie rooted, unlabelled, plane trees, ...
1
vote
2answers
747 views

Graph Theory(trees) problem?

I am practicing for my Discrete Math final and came across this question on trees in my textbook(Rosen). Suppose 1000 people enter a chess tournament. Use a rooted tree model of the tournament to ...
1
vote
1answer
37 views

Does the Prim algorith always create the same tree despite the starting node?

Does the Prim algorith always create the same tree despite the starting node? PD: sorry for my english.
1
vote
3answers
127 views

Parent and childs of a full d-node tree

i have a full d-node tree (by that mean a tree that each node has exactly d nodes as kids). My question is, if i get a random k node of this tree, in which position do i get his kids and his parent? ...
1
vote
1answer
314 views

No of labeled trees with n nodes such that certain pairs of labels are not adjacent.

What is the number of trees possible with $n$ nodes where the $i$th and $(i+1)$th node are not adjacent to each other for $i \in \left[0,n-1\right)$ and $$i/2 = (i+1)/2.$$ (integer division) (nodes ...
1
vote
1answer
733 views

How can I tell how many non-isomorphic unrooted trees with 6 edges exists without drawing them all?

Typically my professor asks that we draw them all, but I would like to save some time to confirm how many I need.
1
vote
2answers
408 views

Breadth first search tree's cycles [duplicate]

Possible Duplicate: Proof related to breadth first search I'm trying to prove the following: Suppose a connected graph $G$ has a cycle $C$ of length $n$. Prove that in any breadth-first ...