Tag Info

Hot answers tagged

3

Let G be a graph. The symbol $\chi(G)$ usually denotes the chromatic number of G, that is, the minimum number of colors required to color the vertices of G in such a way that no two adjacent vertices share the same color. It's easy to see that, if G is a tree, then it can be colored with at most two colors, therefore $\chi(\text{Tree}) \le 2$.


3

27 = 3*3*3, so maybe we have to work with triangles. A triangle has three spanning trees. Let's take three triangles and try to connect them in such a way that we get 27 spanning trees and 8 edges. Call them triangle A, B, C. Connect triangle A and B together so that they share a vertex. Now we have 8 vertices. Connect a vertex from triangle C to the ...


2

I am sending some preliminary, as yet not fine-tuned and optimized obervations to generate activity on this question. I am sure these admit improvements (the time and space complexity of the algorithm is poor). If I have decoded the problem statement correctly we are enumerating labeled endofunctions with no fixed points as appeared at this ...


2

HINT: Let $v$ be a vertex of degree $k$, and take $v$ as the root. Let $v_1,\ldots,v_k$ be the daughters of $v$. Show that the subtree rooted at $v_i$ must have at least one leaf for each $i\in\{1,\ldots,k\}$, and that these $k$ leaves must all be distinct.


2

It’s easier to understand if you word backwards. Suppose that such a tree has depth $d$; what are the maximum and minimum possible numbers of nodes? A perfect binary tree of depth $d$ has $$1+2+\ldots+2^d=2^{d+1}-1$$ nodes; that’s clearly the maximum. You can remove at most $2^{d-1}$ of the nodes in the last level and still have a quasi-complete binary ...


2

I tried to find a counter example and I came up with this one: Edit: As was pointed out in the comments, my original example lacked the root condition. Let $ V = \{ v_0, v_1, v_2 \} $ be the nodes and $ E = \{ (v_0,v_2), (v_2, v_1) \} $. I think the resulting matrix should be: $$ \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 ...


2

If the question is: "For an arbitrary labeling of the nodes, so long as the root is the first, is the resulting matrix triangular?" The answer is no. For instance, a simple counterexample is a graph with edges $\{(v_1, v_3), (v_3, v_2)\}$. Then the adjacency matrix (as defined in the question) is $\left[\begin{smallmatrix} 0 & 0 & 0\\ 0 & 0 ...


2

If the vertex $v$ has degree $1$, then $v$ is incident to only one edge, namely $e$. This means that $v$ is connected to the rest of $G$ by way of only one edge, and $v$ will only have one other vertex connected to it. So removing $v$ and its only incident edge $e$ from connected graph $G$ means what?


2

I start in Washington DC and I want to travel to Roanoke. What is the shortest way to get there? This is a case where you would want to use Dijkstra's Algorithm. I live in Roanoke. We got a large snowstorm and have to plow the roads. What roads do we plow to enable everyone to travel to any location in the city? Here, we aren't concerned with a single ...


1

Prim and Kruskal are for spanning trees, and they are most commonly used when the problem is to connect all vertices, in the cheapest way possible. For Example, designing routes between cities. Dijkstra, is for finding the cheapest route between two vertices. For Example, GPS navigation.


1

You should take a look at the diagrams on Wikipedia which show you how the heights of the subtrees involved change, which will then tell you why you need to use the rotations for the RL case. If you use only one rotation, that middle subtree will stay at the same height and it will remain unbalanced. Don't simply memorize which case it is supposed to be ...


1

If I interpret the lemma and the definitions correctly, it seems that there are two definitions at work here: The code of an ordered rooted tree works through the branches "from left to right", i.e., following the order. The minimum code of an ordered rooted tree works through the branches on a "smallest binary number first" basis. While the code ...


1

No, this is wrong. Your tree is not in sorted order. Notice that you have 15 to the left of 12.


1

Think about the problem a little. What does a vertex of degree $1$ look like? What does a cut-edge look like?


1

HINT: Use the definition to prove by induction that every tree is connected, and no tree contains a cycle. Then prove the contrapositive of the desired statement. Assume that a graph $G$ is not a tree; either it contains a cycle, or it’s not connected. If you know that it contains no cycle, then it must not be connected. Now show that there must be a pair of ...


1

See this question for a proof that a connected graph is a tree defined in this manner if and only if it has no cycles. Thus the only way $G$ can fail to be a tree is for it to be disconnected. If $G$ is disconnected into two nonempty components $G_1$ and $G_2$ with no edges between them, then adding any edge from a vertex in $G_1$ to a vertex in $G_2$ will ...


1

Clearly a tree with 1 vertex has no cycles. For a connected tree with $k$ vertices, pick a vertex that was most recently added in some sequence constructing the tree. If we remove the vertex, there are no cycles by induction. If we had a cycle when we attached the new vertex, then the cycle would have to contain the new vertex, which means the new vertex ...


1

We observe that all fractions in $E(n)$ have the same denominator, so let's directly calculate the total numerator $S(n)$; for instance $S(5) = 3 \cdot 80 + 5 \cdot 944$. Let $T(n)$ be the number of pseudoforests with exactly one connected component, or the number of "good graphs" in the notation of this question. Let $\pi(n)$ be the set of the integer ...


1

I implemented @Jacopo Notarstefano's method, which is a good answer and has better space complexity than my initial draft. Time complexity is middling. It can compute the distribution for $n=60$ in $291$ seconds or about five minutes according to my tests. Here are some of the coefficients for $n=60$: $$2: ...


1

Yes -- the search tree condition will be satisfied at each node, because by definition of inorder every value in its left subtree will be visited before (and thus be smaller) than the value at the node, and similarly for the right subtree.



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