Introduction to Graph Theory · Problem 7.1

Independent sets — Darij Grinberg

Mathematics — Graph Theory · independent-sets-probabilistic

Problem

Let

G = (V, E)

be a simple graph such that each vertex of

G

has degree

\geq 1

. Prove that there exists a subset

S

V

having size

\geq \sum_{v \in V} \dfrac{2}{1 + \deg v}

and with the property that the induced subgraph

G[S]

is a forest. [Hint: As the example of

\boxed{1} \!-\!\boxed{2}\!-\!\boxed{3}

shows, this claim is not true for loopless multigraphs (unlike the similar Theorem 7.1.4).]