# Tag Info

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 ...

2

Hint: Consider the most expensive edge that is in one of the two spanning trees but not in the other. Removing it will make its tree fall apart in two pieces. But you can connect it back together again by adding a cheaper edge from the other spanning tree. This shows that the tree was not minimal to begin with.

2

With that definition of a tree, your formulation is correct, it's just not very useful; the definition includes the first two statements. The power of the initial theorem is that from any two of the three statements, we can conclude the third.

2

Yes, this is a standard example. Fix a computable listing of the sentences in the language of arithmetic, $\{\varphi_i: i\in\mathbb{N}\}$. Each binary sequence $\sigma\in 2^{<\omega}$ now corresponds to a set of sentences: $$[\sigma]=\{\varphi_i: \sigma(i)=1\}\cup\{\neg\varphi_i: \sigma(i)=0\}.$$ (Note that this set is finite, since $\sigma$ has finite ...

2

Each edge $\{u,v\}$ of the tree partitions $V$ into two nonempty parts. Draw an arrow on the edge $\{u,v\}$ pointing in the direction of $v$ if the $v$-part of $V$ contains more than half of the vertices. Then no edge gets two arrows. Starting at a leaf proceed along arrows as long as possible. The resulting path has to end at some vertex $v$, because ...

1

Here's a proof by contradiction. Call the tree $T$. For some $V \subseteq V(T)$, $T - V$ is the graph obtained by removing the vertices $V$ from $T$. Suppose that your statement is false. Take the "best" vertex $x$. That is, removing $x$ leaves a component $C$ of size strictly greater than $n/2$, but $C$ is as small as possible among possible choices ...

1

Well, I personally wouldn't expect a particularly elegant way to count them, but maybe I'm overlooking a particularly beautiful argument here (different from Cayley's formula). The problem with considering complete degree sequences is that it is not immediately clear from a given sequence whether or not it occurs as the degree sequence of a graph (though it ...

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

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

Both DFS and BFS are essentially the same algorithm that expand and visit vertices in some order, but differ in the way they store these vertices, which impacts this order. Hence, differ in their internal data-structure. DFS uses a stack where as BFS uses a queue, which means DFS explores newly discovered vertices first (LIFO) and BFS explores adjacent ...

1

Suppose the starting vertex is $r$. BFS visits vertices in the order of non-decreasing distance to $r$. In other words, for two vertices $u$ and $v$, if the distance between $u$ and $r$ is smaller than that between $v$ and $r$, $u$ will be visited before $v$. Here, we assume the graph is unweighted (i.e., the edge weight is 1) and distance between two ...

1

The result of createSchedule is a list of rounds. Each round is described by nodes receiving message from their parent that round. Each parent can only send one message per round. public class Scheduler { @Override public List<Collection<Node>> createSchedule(Node root) { List<Collection<Node>> result = new ArrayList<>(); ...

1

If you already know that the Catalan number $C_n$ is the number of valid parenthesis strings with $n$ pairs of parentheses, you can prove that the number of strict binary trees with $n$ internal nodes is $C_n$ by demonstrating that there is a bijection between the two sets. There is a bijection that is fairly easy to describe, and I’ll sketch the argument ...

1

An edge is a bridge if and only if it is not contained in any cycle. A tree has no simple cycles and has $(n − 1)$ edges. The graphs with exactly $(n-1)$ bridges are exactly the trees. A graph with n nodes can contain at most $(n-1)$ bridges, since adding additional edges must create a cycle. @Wiki

1

If you are allowed to have an unbalanced binary tree, the problem is as simple as comparing diameters on each level of the tree. Level 1 (root): diameter(coin) >= diameter(dollar) ? yes -> the coin is a dollar no -> go to level 2 Level 2: diameter(coin) >= diameter(half-dollar) ? yes -> the coin ...

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

Hint (same proof as for the finite case)

1

Let $E_n$ be the event that the student took the Level $n$ exam.   You know how many students took each so assuming there is no bias in selecting the student from among the examinees... $$~\mathsf P(E_{\rm I})~=\\ \mathsf P(E_{\rm II})~=\\ \mathsf P(E_{\rm III})~=$$ Let $S$ be the event that the student passed the exam.   You've been given the ...

1

Some problems in your writeup: If $l$ is the number of leaves of $T$, you cannot conclude that $l \leq \frac{n}{2}$, but only $l \leq \frac{n+1}{2}$ (in case $n$ is odd). And so, the number of internal vertices is $n - l \geq \frac{n-1}{2}$ (not $\frac{n}{2} - 1$). A priori, I see no reason why the number of internal vertices can't be equal to the number of ...

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