Rational Solver

0 votes

Best answer

**Recall:** We know that sum of all degree of vertices in a simple graph $G$ is twice its number of edge. Let $E(G)$ be the edge set of $G$ and $V(G)$ be the vertex set of $G$. Then

$$\sum_{v\in G} d(v) =2|E(G)|$$

Let $T$ be a tree on $n$ vertices with a maximum degree $k$. Then by the above result we know that

$$\sum_{v\in T} d(v)=2|E(T)|= 2(n-1)$$

Let there are $\ell$ many leaves in the tree $T$. We have to prove that $k\leq \ell$.

Note that there are $n-\ell$ vertices in $T$ with degree at least $2$. Amon all those $n-\ell$ vertices there will be at least one vertex with degree exactly $k$. That means, there are $n-\ell-1$ vertices with degree at least two and one vertex with degree exactly $k$. It follows that

$$\sum_{v\in T}d(v) \geq \ell + (n-\ell-1)\cdot 2+k = 2(n-1)+(k-\ell).$$

Therefore it follows that

$$2(n-1)=\sum_{v\in T}d(v) \geq 2(n-1)+(k-\ell) \implies k-\ell \leq 0$$

This completes the proof.

- All categories
- JAM 10
- WBJEEE 7
- Linear Algebra 8
- Calculus 3
- Discrete Mathematics 10
- Differential Equation 10
- Functional Analysis 1
- Abstract Algebra 3
- Topology 1
- Complex Analysis 5
- Probability 5
- Real Analysis 10
- Anonymous 0
- Chemistry 0
- Physics 0
- Spam 0

76 questions

33 answers

2 comments

1,801 users