a question on graph theory

199 Views Asked by At

This is Exercise 13 on page 189 of Reinhard Diestel of Graph Theory

Given a tree $T$, find an upper bound for $ex(n,T)$ that is linear in $n$ and independent of the structure of $T$, i.e., depends only on $|T|$.

The hint refers to Proposition 1.2.2 and Corollary 1.5.4.

Proposition 1.2.2 Every graph $G$ with at least one edge has a subgraph $H$ with $\delta(H) > \varepsilon(H) \geq \varepsilon(G)$,

where $\delta$ and $\varepsilon$ denote the minimum degree and half of the average degree respectively.

Corollary 1.5.4 If $T$ is a tree and $G$ is any graph with $\delta(G) \geq |T|-1$, then $T \subseteq G$, i.e. $G$ has a subgraph isomorphic to $T$.

But I don't know how to connect 1.2.2 to this question.

I need some help on this question. Thanks for any help.

1

There are 1 best solutions below

1
On BEST ANSWER

Hint: By Proposition 1.2.2., if $G$ is a graph with $\varepsilon(G) = |T| - 1$, then $G$ has a subgraph $H$ with $\delta(H) \geq |T| - 1$. Now what does Corollary 1.5.4 imply about $H$? You can then use $\varepsilon(G) = |T| - 1$ to get an upper bound for $\text{ex}(n,T)$.