Hot answers tagged

2

There is $1$ node in row $0$, $3$ nodes in row $1$, $9$ nodes in row $2$ etc. The total number of nodes up-to-and-including row $k$ is $\dfrac{3^{k+1}-1}{2}$, the partial sum of the geometric series. This gives $$\begin{array}{c|c|c|c|c|c|c}k&0&1&2&3\\\hline\dfrac{3^{k+1}-1}{2}&1&4&13&40\end{array}~~~\text{ etc.}$$ So for a ...


1

The proof is pretty easy: In any tree $T$ we have $$ |V(T)|= |E(T)|-1$$ where |E(T)| is the number of edges in $T$ Note that $$|E(T)|=\frac{1}{2}\sum_{v\in T} d(v) $$ Then we have two case 1- $ \frac{1}{2}\sum_{v\in T} d(v) $ is odd and thus $ |V(T)|$ is even 2- $ \frac{1}{2}\sum_{v\in T} d(v) $ is even and thus $ |V(T)|$ is also even (Since $d(v)$ is ...


1

First, note that if you add an edge to a tree, you obtain a cycle. You should already know that, but if you don't, see this question for a proof. So you cannot add edges $(a,b)$ if $a$ and $b$ lie in the same connected component. There is only one other possibility, that you add edges connecting different components. So any edge you add will reduce by $1$ ...


1

You need to add a lot more detail and clean up some inaccuracies. First, the negation of the conclusion isn’t that $G$ is not connected by a unique simple path: it’s that there are two vertices, $u$ and $v$, of $G$ that are not connected by a unique simple path. We’re assuming that $G$ is connected, so $u$ and $v$ are connected by at least one simple path; ...


1

I think that it can be embedded. Consider a 2-complex obtained by adding the edge in the middle and then the obvious 2-faces. Concretely, it means adding 3 triangles and $3\cdot3$ + $2\cdot6$ quadrilaterals. It is not acyclic yet, but after removing one quadrilateral from each cube, you get an acyclic one. Now you may subdivide the remaining quadrilaterals ...


1

You've misunderstood the notation. Refer to Definition 1: $\text{Aut}(TREE)$ is being used by the authors to denote the set of isomorphism classes of automorphism groups of (presumably finite) trees. So the notation $\Psi \in \text{Aut}(TREE)$ means that $\Psi$ is the full automorphism group of a particular tree. In fact Theorem 2 is just a restatement of ...


1

You want to write a program finding all the shortest paths between any two vertices in your graph. At the step $n$, the program will have saved in $d[i,j,n]$ the shortest path of length at most $n$. You do it as follows: Initialise $d[i,j,1] = w(i,j)$, that is the length of the edge from $i$ to $j$, if there is any. Proceed recursively: assuming you have ...


1

$1$ is impossible because if the stack consists of $(a,b,e,f)$ (with $f$ at the top), then the next node traversed must be $c$ or $g$, since those are adjacent to $f$ and have not been traversed yet. $2$ is possible; if the stack consists of $(a,b,e,f,c)$ then we must pop $c$ and then $f$, and can then push $g$ and $d$. $3$ is possible, as it is a path in ...



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