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

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 ...
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 ...
2
votes
1answer
23 views

Different trees of weighted graph , please check whether my explanation is correct $?$

Let G=(V, E) be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of vertices of degree $d$ in G. If S and T are two different trees with $\xi(S) = \xi(T)$, then ...
2
votes
3answers
146 views

Showing that the complete bipartite graph $K_{a,b}$ is a tree if and only if $a=1$ or $b=1$.

Let $K_{a,b}$ be the complete bipartite graph. Show that $K_{a,b}$ is a tree if and only if $a = 1$ or $b = 1$. The way my professor showed us for a complete graph is as below. I just don't know how ...
2
votes
1answer
67 views

Dual graph of a tree

It is stated here that: For any connected embedded planar graph G define the dual graph G* by drawing a vertex in the middle of each face of G, and connecting the vertices from two adjacent ...
2
votes
1answer
203 views

Furthest distance vertices undirected tree

I know in my mind that it's very obvious, but I just can't seem to prove the following statement: Let $G$ be an undirected non-trivial tree with at least $3$ vertices. Let $u$ be an arbitrary vertex ...
2
votes
1answer
138 views

what' is the number of full subtrees of a full binary tree?

I'm looking for the number of full sub-trees of a binary tree; all possible tress of height less than $4$ are: Now my question is: What is $N(h)$ the maximum number of full sub-trees of a ...
2
votes
1answer
127 views

Number of rooted subtrees with m edges of a p-regular tree

I have the following question: Assume I have an infinite $p$-regular tree, that is a tree where every node has degree $p$ (so also the root should have degree $p$). Then how many subtrees containing ...
2
votes
1answer
188 views

Relax function on Bellman Ford Algorithms

In a Weighted Directed Graph $G$ (with positive weights), with $n$ vertex and $m$ edges, we want to calculate the shortest path from vertex $1$ to other vertexes. we use $1$-dimensional array $D = ...
2
votes
2answers
332 views

Two disjoint spanning trees, spanning subgraph with all even degrees

Show that if a graph has two edge-disjoint spanning trees then it has a connected, spanning subgraph with all degrees even. I start by looking at the union of the two spanning trees. I know it has ...
2
votes
1answer
67 views

Prove in any tree with n vertices, the number of nodes with 3 or more neighbors is at most 2(n-1)/3

I know that the number of edges in the tree is n-1, and by the sum identity, the degree is 2(n-1)... I'm not sure how to go about completing the proof, or even starting it for that matter.
2
votes
1answer
40 views

Why doesn't Tutte polynomial T(1,1) equal 0?

If the formula for a Tutte polynomial is: then how does T(1,1) solve for spanning trees instead of just returning a 0?
2
votes
1answer
776 views

Preorder traversal, inorder traversal, postorder traversal

a) preorder traversal b) inorder traversal c) postorder traversal Ok, a) r,j,h,g,e,d,b,a,c,f,i,k,m,p,s,n,q,t,v,w,u b) a,b,d,c,e,g,f,h,j,i,r,s,p,m,k,n,v,t,w,q,u c) ...
2
votes
1answer
462 views

Proving that the height of a 2-3 tree is between $\log_3 N$ and $\lg N$

I am stuck on the problem of trying to prove the upper and lower bounds of a 2-3 tree. I think the most natural recourse is to use induction. However, my instructor told me that this was unnecessary ...
2
votes
1answer
40 views

tree structure on classes of elements in GL_2 over a field with discrete valuation

this is my first question here, so I hope I am doing it right. :) I'm currently reading a paper about the tree of GL_2 over a discretely valued field (similarly to Serre). Here's the setting: $k$ an ...
2
votes
2answers
65 views

Construction Types or Type Constructions?

In any (simple) type theory there are base types (i.e. the type of individuals and the type of propositions) and type builders (i.e. $\rightarrow$, which takes two types $t,t'$ and yields the type of ...
2
votes
1answer
193 views

questions about binary search tree

Show that every n-node binary search tree is not equally likely (assuming items are inserted in random order), and that balanced trees are more probable than straight-line trees. How is it prove ...
2
votes
2answers
58 views

Embedding of Tree

Q. Proof for every Tree can be embedded into the plane. Conditions. We cannot use Euler Formula for Planar Graphs. We can use definition of tree, $V-E=1$, no-cycles, every edge is critical, there ...
2
votes
1answer
86 views

Proof of the Converse of Kraft's Theorem

So I have already proven Kraft's theorem for ternary trees, and I have been tasked with proving the converse. That is, I need to show that there is a ternary tree with $k$ leaves, such that leaf $i$ ...
2
votes
1answer
184 views

Probability of passing through 3 specific nodes along a binomial tree

Consider a re-combining binomial tree with probability of up = $p$ and probability of down = $(1-p)$. Let $n$ be the number of time steps in the binomial tree (the $x$-axis is time, and each column of ...
2
votes
1answer
166 views

Finite Rooted Binary Trees

I am new to learning about finite rooted binary trees. This lemma below is from John Meiers book: Groups, Graphs and Trees. There is no aval proof in the book. I was just wondering is I could catch a ...
2
votes
1answer
751 views

Oriented trees and ordered trees

I have this confusion regarding ordered and oriented trees. I know they are both rooted and in ordered trees, the order is important. So lets say I have four nodes 1,2,3,4 then it is given that the ...
2
votes
1answer
95 views

Showing two recurrences to be identical

I am trying to prove Cayley's formula for number of labelled trees on n vertices using multinomial coefficients. The multinomial coefficient satisfies the recurrence: $\tbinom{n}{r_1,\cdots ...
2
votes
2answers
488 views

Number of undirected trees with labeled edges, one repeating

I need to find the number of undirected trees on $n$ vertices such that the edges (and not the vertices) are labeled and exactly one label appears twice (i.e. there are $n-2$ possible labels and they ...
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 ...
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 ...
2
votes
0answers
114 views

Bounding the global intersection of a family of sets

Suppose that we have a decision tree of height $r + 1$ that describes how to increment an $n$-bit integer in the range $[0, 2^n -1]$. That is, the internal nodes are labelled with a bit position that ...
2
votes
0answers
23 views

Maximum number of subtree in a spanning tree

Is it possible to determine the theoretical maximum of number of subtree that can be extracted from a spanning tree? Some context (I don't know whether this is useful): I build the spanning tree by ...
2
votes
2answers
88 views

Graph Theory: Trees, leaves and cycles

So, a vertex is called a leaf if it connected to only one edge. a) Show that a tree with at least one edge has at least 2 leaves. b) Assume that G = (V, E) is a graph, V ≠ Ø, where every vertex ...
2
votes
0answers
53 views

Generating all coprime pairs

The Wikipedia article on coprime integers has a brief section on generating all coprime pairs. All pairs of positive coprime numbers $(m,n)$ (with $m>n$) can be arranged in two disjoint ...
2
votes
0answers
43 views

Possible Paths in Pipe Network

I'm working on this project for an oil and gas company. One of the main features is a visualization of their pipe network. I'm trying to create a tree of all possible paths. The only limit i have to ...
2
votes
1answer
149 views

What is the “true” minimum spanning forest of a connected graph?

Normally, a minimum spanning forest of a graph G is defined as the union of minimum spanning trees of each of its components. This definition is a generalization of the minimum spanning tree of a ...
2
votes
0answers
107 views

Tree decomposition by hand for understanding

I am implementing "algorithm 2" from the paper "Treewidth computations I. Upper bounds" by Bodlander and Koster[1,page5] and I am not sure if I understand it or not. As I understand, the algoritm ...
2
votes
1answer
150 views

Finding a node in a full binary tree: expected number of comparisons

Consider a full binary search tree of height $k$ (the root is on level $1$ and the leaves on level $k$). By full I mean that all leaves are on level $k$ and level $k$ has exactly $2^{k-1}$ leaves. In ...
2
votes
0answers
89 views

Graph Algorithm and Cycle Detection

In $O(|V|+|E|)$, we can detect whether a Directed Graph has a cycle or not. ---> True In depth-first seach on DAG, there is no Back Edge. ---> True With known Number of Edges, in $O(|V|)$ and not ...
2
votes
0answers
85 views

Counting unlabeled and non-uniquely labeled trees

I recently learned about Cayley's formula, which states that the number of trees on $n$ labeled vertices is $n^{n-2}$. As I understand it, this works because we can prove that there are $n^{n-2}$ ...
2
votes
0answers
72 views

Examples of forcings which add no “definable” Aronjain tree

Maybe a bit board question but: Fixing a regular cardinal $\kappa$ in the ground model, I am looking for examples of set forcing notions which preserve regularity of $\kappa$ and add no new $\kappa$ ...
2
votes
0answers
44 views

Delete nodes that satisfy a property

I want to write a function that takes as argument a pointer A to the root of a binary tree that simulates a (not necessarily binary) ordered tree. We consider that each node of the tree saves apart ...
2
votes
0answers
42 views

About the topology of a $d$-regular tree

What is the proof that the infinite $d$-regular tree is an universal covering space for any $d$-regular graph? Is it true that the infinite $d$-regular tree is a Ramanujan graph? (any easy way to see ...
2
votes
0answers
46 views

How can I infer order from partially ordered discrete sequences?

A really interesting problem that I can't stop thinking about! Have run in to this a couple of times but yet to find a smart approach to either solve or frame this problem. This is my try at ...
2
votes
0answers
122 views

Can “tit for tat” strategy be defined in monadic second-order logic?

Prisoner's dilema game can be represented as a game tree, which could be infinite game with corresponding infinite game (binary) tree in common case. There is well-known tit for tat strategy, which ...
2
votes
1answer
72 views

Shortest path between two vertex

How we can find Shortest path between two vertex in a weighted directed acyclic graph that has positive and negative weight. in O(|V|+|E|)? thanks to all.
2
votes
1answer
185 views

Width and height of binary tree is $\theta(n)$?

we know this definition: Given a binary tree, Width of a tree is maximum of widths of all levels. Let us consider the below example tree. ...
2
votes
1answer
87 views

Mathematics of genealogical trees

I really searched a lot but did not find anything meeting my needs: A place where questions of genealogy, especially the structural and combinatorial analysis of genealogical "trees" of descendants ...
2
votes
0answers
43 views

What are the automorphisms of an $n$-regular tree?

Let $T$ be the connected tree in which each vertex has $n$ neighbors. (So $T$ is infinite.) What is the full automorphism group of $T$?
2
votes
1answer
59 views

Number of upper sets of size $n$ in a finite tree

Consider a finite tree $T = (V, <)$, where $y < x$ means that $y$ is the parent of $x$. We assume that $T$ has a unique root $r$ that has no parent. An upper set of $T$ is a subset $S$ of $V$ ...
2
votes
0answers
105 views

Presentation of tree decompositions (and related concepts) in terms of continuous maps?

A tree decomposition of a graph $G$ is commonly defined in terms of a tree $T$ with the following structure: Each vertex $t \in V(T)$ is associated to a set $X_t \subseteq V(G)$; The union ...
2
votes
0answers
76 views

Groups acting on (regular) trees with finite quotient

Let $T$ be a regular tree, and suppose that $G \leq \mathrm{Aut}(T)$ has finite quotient graph, $T / G$. Is it true (in general) that $G$ will have trivial centralizer in the full automorphism group? ...
2
votes
0answers
938 views

Minimum Spanning Tree in a Complete Graph

We generate a complete euclidean graph by taking N random points from a limited (1.0 x 1.0 square) 2D space, connecting them all together (complete graph) and giving the edges weights proportional (or ...
2
votes
0answers
113 views

A few questions about a relationship between some integer sequences and infinite recursive trees

In his book Gödel, Escher, Bach Douglas Hofstadter defines the following two integer sequences: Hofstadter G-sequence: $a(n)=n-a(a(n-1))$ Hofstadter H-sequence: $a(n)=n-a(a(a(n-1)))$ He says ...