# Tag Info

3

Some HINTS: In the first problem you can use induction on $n$. Let $d_1\le d_2\le\ldots\le d_n$ be a sequence of positive integers such that $$\sum_{i=1}^nd_i=2n-2\;.$$ First note that if $\sum_{i=1}^nd_i=2n-2$, then $d_1=1$, and $\sum_{i=2}^nd_i=2n-3$. And $2(n-1)>2n-3$, so we must also have $d_2=1$ and hence $\sum_{i=3}^nd_i=2n-4$. We now have $n-2$ ...

1

I’ll work an example with the expression a*b/c+d-e*f. Note that plus and minus signs separate terms, while multiplication and division signs separate primaries within terms. Also, expressions generate their component terms from right to left: the rightmost term is the first one to be split off, via the productions <expression> → <expression> ± ...

1

See http://en.wikipedia.org/wiki/Longest_path_problem for a discussion of the longest path problem. In general it is NP-hard unless your graph is directed acyclic. Thus there are probably no fast solutions. If you want a somewhat brute force solution, then for each starting node do a depth first search (look up on wikipedia if you're not familiar with it) ...

1

Let $w$ be the number of leaves. We know $\sum \deg(v)=34$ where the sum is taken over the $18$ vertices of the graph. Each leaf of the graph contributes a degree of $1$; and each non-leaf contributes a degree between $3$ and $6$ inclusive, with at least one vertex contributing a degree of $6$. So $6+w+3(17-w)\le \sum\deg(v) \le 6+w+6(17-w)$ Therefore ...

1

Suppose $v$ is not in any "furthest pair". Let $x,y$ be a furthest pair. For vertices $s,t$, we denote the $s$-$t$-path in the tree by $P_{[s,t]}$. Let $w$ be a vertex in $P_{[x,y]}$ with $d(u,w)$ minimum. By the symmetry of $x,y$, we can assume $P_{[w,v]}$ and $P_{[x,w]}$ have no common edge. By our assumption, $d(w,v)<d(w,y)$, otherwise $P_{[x,w]}$ ...

1

Hint: Use this definition, "If G is a tree, if and only if G is connected and has $n − 1$ edges." and (assuming G mentioned in question is connected) 1) Find number of vertices in G ($n$) 2) Find number of edges ($e$)(Hint: each edge contribute two degrees) Find if there are any K's such that $e=n-1$. Then it is possible to find a tree of such K. ...

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