Hot answers tagged

13

There is a well-developed theory of trees in set theory that allows transfinite heights. The general definition is that a tree $(T,<_T)$ is a partially ordered set such that for every node $x\in T,$ the initial segment $\{y\in T : y <_T x\}$ is well-ordered. The idea of a complete binary tree (i.e. a tree where every node has exactly two immediate ...


5

Second part is not correct. Intuition: since trees are not 2 vertex connected, you can fix one vertex and construct the tree such that vertices on the left has to pass through this vertex to reach vertices on the right. Then, construct 2 such trees and you will get counterexample for second part. Counterexample: $𝑇_1=𝑣_1βˆ’π‘£_2βˆ’π‘£_3βˆ’π‘£_4βˆ’π‘£_5βˆ’π‘£_6βˆ’π‘£_7βˆ’π‘£_8βˆ’...


4

Assume $G$ is a graph and $X$ is a set such that every vertex is in $X$ or adjacent to a vertex in $X$. We prove there is a spanning tree $T$ of $G$ such that every vertex is in $X$ or adjacent to a vertex in $X$. For each vertex $v$ not in $X$ we add exactly one edge from $v$ to $X$ that is in $G$. After doing this the graph has no cycles, because it is ...


4

Yes, and what's more, for any dominating set $W$ of $G$, there is a spanning tree $T$ for which $W$ is also a dominating set. Begin choosing $T$ by going through all vertices $v \notin W$, and adding an edge from $v$ to some vertex $w \in W \cap N(v)$. This gives us a star forest in which $W$ is a dominating set. It can be extended to a spanning tree however ...


4

Let $T$ be the Cayley graph of the subgroup $F$ generated by $a$ and $b$ (wrt these two generators). Since $F$ is free on $\{a, b \}$, $T$ is a tree of valence $4$, on which $F$ already acts by an action which is transitive on the vertices. We need to extend this action to an action of $G$. In other words, we need to extend a morphism from $F$ to $Isom(T)$ ...


3

There is only one tree which has exactly one leaf - the tree which doesn't branch. Thus, $|T_1| = 1$. Now consider $T_n$ for $n > 1$. A tree with $n$ leaves can only be made by combining a tree with $k$ leaves with a tree with $n - k$ leaves, where $1 \leq k < n$. That is, $T_n \approx \coprod\limits_{k = 1}^{n - 1} T_k \times T_{n - k}$. So we have $|...


2

Gathering data for $m=1,2,3,4$ should suggest a very simple formula, but it’s also possible to work out the answer without those data. Suppose that $T$ is a quadrivalent tree with $m$ vertices of degree $4$ and $\ell$ leaves. Then the sum of the degrees of the vertices of $T$ is $4m+\ell$, and you know that this is twice the number of edges. Since $T$ is a ...


2

Second, is by a stem meant ambiguously any node of the linearly ordered beginning of the tree in question, from the first to last such node, or only unique last such node ? The stem is the unique last node (this is implied by the second bulletpoint, which says that every node not below the stem has infinitely many successors - including the stem itself). So ...


2

Hope you are doing well. So, you know that the sum of degrees over the $18$ vertices of $G$ is 34. What degree does each leaf contribute to this and what degree do the other vertices contribute? Well, the leaves add $1$ and the other vertices add $3$-$6$ (since the max is 6 and the min is 3). Let $\ell$ denote the number of leaves. From the above statements ...


2

In the left free tree, the two vertices of degree $3$ are not connected by a single edge, and in the right free tree they are. This difference implies there is no isomorphism between the two free trees.


2

If the graph is a complete graph with $n$ vertices, it then has $n^{(n-2)}$ spanning trees by Cayley's formula. If the graph isn't a complete graph, you can use Kirchoff's theorem. Here's an example of it (I took the example from this video): For the following graph, you first take the adjacency matrix: \begin{pmatrix} 0 & 1 & 1 & 1\\ 1 & 0 &...


1

We have that $C_{n-1}$ is the number of ordered trees with $n$ vertices. Each ordered tree clearly induces an unordered tree, and every unordered tree is reachable as an ordered tree (in fact always in more than $1$ way when the graph has more than $2$ vertices). Proof that the number of ordered trees is $C_{n-1}$: Let $O_n$ be the quantity. We can show it ...


1

Much more straightforward combinatorial proof: $n^{n-2}$ counts the number of functions $[n-2]\to [n]$ On the other hand, if we try to count the number of functions $[n-2]\to [n]$ via inclusion-exclusion that at least one number from $[n]$ does not appear in the image... that is letting $A_k$ count the functions $f$ such that $k\notin\operatorname{Image}(f)$,...


1

There appears to be the start of a good proof there. This is how you could finish building on what you already did. By the inductive hypothesis, there is one common vertex $u$ in all of the nonempty $T'_i$. [Keep in mind that $v$ as you remove the vertex from $T$ the subtrees may get smaller as well and so there may be a $T'_i$ may have no vertices which ...


1

I don't understand the problem. $T^\prime$ has a vertex $u$ which is in all of the $T_i^\prime.$ Since $u \in V(T_i^\prime),$ and $V(T_i^\prime) \subseteq V(T_i),$ it follows that $\in V(T\prime)\subset V(T)$ is in all of the $V(T_i)$


1

Take a collection of finite trees, such that your collection contains trees of every possible finite height. Graft them all onto a single new root node. Then the combined tree has height $\omega$ (it certainly can't have any finite height) -- but it can't contain any infinite branch. Such a branch would have to contain one of the successors of the new root ...


1

It seems to me that you are misunderstanding KΓΆnig's lemma. It gives a sufficient (and not necessary) condition for a tree to have an infinitely long ray/path. Namely, if a tree is infinite (has infinitely many vertices) and finitely branching (locally finite/each node has finitely many children), then it has infinite ray/path from the root (note this is ...


1

A tree with a single root and infinitely many children (which all are leaves) is an infinite tree without infinite branch.


1

In a sense, you just defined which additional nodes we should have in the completion, the problem is that we cannot add edges to them, because then they would be accessible via finite paths and intuitively we would only want them accessible via infinite paths. We cannot get to a good completion in the framework of graphs with the nodes/edges definition. The ...


1

I think the easiest way to prove this is with a minimality argument. Let $T = (V,E)$ be our tree, and for any vertex $u\in V$, define the function $C:V\rightarrow \mathbb{N}$ that gives you the max number of vertices in a connected component of $T-u$: $$C(u) = \max\{|V(T')| : T' \text{ a connected component of } T-u\}$$ For our proof, we will assume to the ...


1

The theorem is false when $|V(G)|=2$ as there is no separator vertex. We assume that $|V(G)|>2$. Then there is a vertex of degree $>1$, and we can assume that $V$ is rooted at such a vertex. Let $M=<\left\lfloor\frac{2}{3}V(G)\right\rfloor$. Consider the subtrees rooted at the children of the root. If all have at most $M$ vertices, then the root ...


Only top voted, non community-wiki answers of a minimum length are eligible