Tag Info

Hot answers tagged trees

3

I would first prove that every tree has at least one leaf. Added: You have in fact tacitly assumed this in your first bullet point, when you say that every tree on $k+1$ vertices is obtained by adding a vertex to a tree with $k$ vertices. This requires that you be able to remove a vertex from a tree on $k+1$ vertices and still have a tree. This cannot be ...

3

The minimum number of edges that need to be removed to disconnect the graph is $3$, and there are just $4$ ways to do this: remove all of the edges incident at one vertex of degree $3$. There are $9$ ways to remove a set $E$ of edges so that (a) the resulting graph is disconnected, and (b) removing any proper subset of $E$ leaves a connected graph. However, ...

1

Is true. Take the subgraphs induced by the two spanning trees, these have $k$ vertices and are cycle-free. Any cycle-free graph with k vertices has at most $k-1$ edges. Is true. Let $v, w$ be vertices from different sets of the cut. Then by 3. there are two edge-distinct paths between $v$ and $w$. So at least one of the edges of each path needs to be cut. ...

1

No. The leftmost and rightmost top vertices are actually the same point on the cylinder, so your yellow "tree" actually contains a cycle. (Using 0, 1, 2, 3 to refer to the horizontal lines top to bottom and a, b, c, d to refer to the vertical ones from left to right, the cycle I mean is a0, b0, b1, b2, b3, c3, c2, c1, c0, d0=a0.)

1

Yes, that is right. If you forget about the internal simplices then it's easy to see that what you've got is correct: you start off with two loops $a$ and $b$ and then attach a 2-dimensional disk along the path given by $baba^{-1}$ (this is the outside of the square that you've drawn). This means that that loop is now contractible, so you need to add ...

1

The number of rooted subtrees of a tree is the product of the numbers of rooted subtrees of the root's children plus one. Here's code that recursively computes $f(s)$. The result is OEIS sequence A007601, which is a shifted version of OEIS sequence A000792. Apparently for $s\ge3$ we have  f(s)=1+\left(\left\{\frac ...

1

If you want to make use of pre-sorted lists, the the idea is to use the fact that the median will be located at $i = floor(\frac{N}{2})$, where $N$ is the length of the list you're looking for. The nice thing about splitting the list is that when we recurse, we can simply use the sub-lists from $[0, i)$ and $[i, N)$ to find the median again. However, as ...

1

I think you're confusing a couple of things here: When you split along an axis, you take a plane perpendicular to that axis and choose points that are "in front of" and "behind" this plane. While you're correct in saying that when you divide along the X axis you can simply look at the $x_0$ from the point $P(x_0, y_0)$, in general, you would like to ...

1

I was surprised to learn, recently, that a simple idea ( made up, it appears, by Tito Piezas, without him knowing it was a neologism) allowed me to get the information in Conway's topograph with a fairly simple computer program, as long as what I wanted was to guarantee finding all solutions $(x,y)$ to $ax^2 + bxy+ cy^2 = n$ with integers $x,y > 0$ and ...

1

another approach: Denote by $G_{e_i}$ the number of spanning trees on $K_n - e_i$ , where $e_i$ is the $i$-th edge in $K_n$ . Denote by $T_n$ the number of spanning trees on $K_n$ . We get the following equation wich I will explain bellow: ${\sum_{n=0}^{ n \choose 2} G_i} = ({n \choose 2} - (n-1))\cdot T_n$ Indeed any spanning tree of $K_n$ either ...

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