\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P8}{20(4)}{2013}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
%\usepackage{graphicx}
\usepackage{graphicx,psfrag,pstricks,pst-plot}  % For figures

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins

% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% SET UP SECTION NUMBERING

\setcounter{secnumdepth}{3}
% Number up to sub-subsections

% CHANGE APPEARANCE OF ENUMERATED LISTS

\renewcommand{\labelenumi}{(\roman{enumi})} % Labels (i), (ii), etc.

% CHANGE QED-RELATED COMMANDS

\renewcommand{\qed}{}
\newcommand{\ggcqedsymbol}{$\square$}
\newcommand{\ggcqed}{\hbox{}\nobreak\hbox{\quad\ggcqedsymbol}}
\newcommand{\ggcendpf}{\ggcqed}
%% NOTE: In this paper, we do not put end marks after proclaims w/o proofs
\newcommand{\ggcnopf}{}
%\newcommand{\ggcnopf}{\ggcqed}
%\newcommand{\ggcendexample}{}
\newcommand{\ggcendexample}{\ggcqed}

% SET STYLE FOR DEFINED TERMS

\newcommand{\defterm}[1]{\emph{#1}} % Defined term
\newcommand{\abstdefterm}[1]{#1} % Defined term in abstract
\newcommand{\localdefterm}[1]{\emph{#1}} % Special defined term,
                                         %  used only nearby

% RUN-IN HEADINGS

\newcommand{\runinhead}[1]{\medskip\noindent\textbf{#1}} % Run-in heading
% This should be used at the start of a paragraph.
% If the heading text ends with "---", then there should be no space between
% the ending right brace and the first word of the paragraph:
% \runinhead{Numbers---}How about 1, 2, and 3?

% LOCAL DEFINITIONS

\newcommand{\enumromanparen}{\renewcommand{\labelenumi}{(\roman{enumi})}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Maximum Induced Forests in\\ Graphs of Bounded Treewidth}

\author{Glenn G.~Chappell\\
\small Department of Computer Science\\[-0.8ex]
\small University of Alaska\\[-0.8ex]
\small Fairbanks, AK 99775-6670, USA\\
\small\tt{chappellg@member.ams.org}\\
\and
Michael J.~Pelsmajer\\
\small Department of Applied Mathematics\\[-0.8ex]
\small Illinois Institute of Technology\\[-0.8ex]
\small Chicago, IL 60616, USA\\
\small\tt{pelsmajer@iit.edu}}

\date{\dateline{Mar 18, 2011}{Oct 19, 2013}{Oct 28, 2013}\\
\small 2010 Mathematics Subject Classifications: Primary 05C35, Secondary 05C05}

\begin{document}

\maketitle

\begin{abstract}
Given a nonnegative integer $d$ and a graph $G$,
let $f_d(G)$ be the maximum order
of an induced forest in $G$ having maximum degree at most $d$.
We seek lower bounds for $f_d(G)$ based on the order and treewidth of $G$.

We show that, for all $k,d\ge 2$ and $n\ge 1$,
if $G$ is a graph with order $n$ and treewidth at most $k$,
then $f_d(G)\ge\lceil{(2dn+2)/(kd+d+1)}\rceil$,
unless $G\in\{K_{1,1,3},K_{2,3}\}$ and $k=d=2$.
We give examples that show that this bound is tight
to within~$1$.

We conjecture a bound for $d=1$: $f_1(G) \ge \lceil{2n/(k+2)}\rceil$,
which would also be tight to within~$1$,
and we prove it for $k\le 3$.
For $k\ge 4$ the conjecture remains open, and we prove a weaker bound:
$f_1(G)\ge (2n+2)/(2k+3)$.
We also examine the cases $d=0$ and $k=0,1$.

Lastly, we consider open problems relating to $f_d$
for graphs on a given surface, rather than graphs of bounded treewidth.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} Treewidth; 
  chordal graph; induced forest
\end{abstract}


\section{Introduction} \label{S:intro}

We begin with an overview of the topics considered in this paper.
Our terminology and notation agree with West~\cite{Wes2001};
see Diestel~\cite{Die2000} for basic information about treewidth.


\subsection{Background} \label{Ss:back}

Consider the following extremal problem
for $\mathcal{G}$ a class of graphs.
Given nonnegative integers $n$, $d$,
find the greatest integer $t$ such that
every $n$-vertex graph $G\in \mathcal{G}$ contains
a $t$-vertex induced forest of maximum degree at most $d$.

When $d=0$, we seek a lower bound on
the size of a maximum independent set.
This has been studied intensely for various
graph classes~\cite{ABT1976, Faj1978, HT2006, Jon1990, LL1997, Sta1979},
and is the extremal version of
the optimization problem \textsc{Maximum Independent Set}.
When $d=n$,
the desired forest has unrestricted degree.
A vertex set $S$ in a graph $G$ is a minimum-size
\localdefterm{feedback vertex set}
%(or \localdefterm{decycling set})
if and only if the set $U=V(G)-S$ induces a forest of maximum order;
thus the $d=n$
case is essentially an extremal version of \textsc{Feedback Vertex Set}.
This topic has also received a great deal of
study~\cite{AlBe1979, AMT2001, AW1987, BaBe2002, CKK2002, Hos1990, Sal2006}.
There are straightforward
connections between these ideas and coloring and acyclic coloring
(the latter were explored by Fertin \emph{et al.}~\cite{FGR2002}),
which can be used to obtain results
for the $d=0$ and $d=n$ cases, respectively.

Most of
the graph classes considered in the above papers are defined by
planarity, degree restrictions, and girth restrictions.
%
For the classes of planar graphs and outerplanar graphs,
the first author considered the $d=2$ case,
conjecturing lower bounds and giving examples that would be best possible.
The second author proved the outerplanar graph
conjecture~\cite[Thm.~1]{Pel2004},
showing that each $n$-vertex outerplanar graph
contains an induced forest with at least $(4n+2)/7$ vertices
and maximum degree at most $2$;
this is best possible.

In the present paper, we extend this result,
considering the class of all graphs with treewidth at most some integer $k$.
This is a natural outgrowth of the previous work,
since outerplanar graphs have
treewidth at most $2$.
%% NOTE: No citation above; we're not being that formal, yet.
We generalize a technique of Pelsmajer~\cite{Pel2004},
to obtain nearly sharp results.

%One of the major
%questions motivating these investigations is a well known conjecture
%of Albertson and Berman~\cite{AlBe1979}, for the case $d=n$,
%$\mathcal{G} = \{\text{planar graphs}\}$.
%Namely, they conjecture that any $n$-vertex planar graph contains
%a vertex set of size at least $n/2$ that induces a forest; there are
%examples showing that this would be best possible. Hosono~\cite{Hos1990}
%proved the sharp result for $d=n$ and \emph{outerplanar graphs}, namely
%that any $n$-vertex outerplanar graph contains a vertex set of size at
%least $2n/3$ that induces a forest.  In an attempt to approach this...


\subsection{Basic Definitions} \label{Ss:defs}

All graphs in this paper are finite, simple, and undirected.

If $G$ is a graph, then $V(G)$ denotes the vertex set of $G$.
If $U\subseteq V(G)$,
then $G[U]$ is the subgraph induced by the vertex set $U$.
%
The set of all vertices adjacent to a vertex $v$ is the
\defterm{neighborhood of $v$}, denoted by $N(v)$.

A graph $G$ is \defterm{chordal} if
every cycle in $G$ of length at least $4$
has a \localdefterm{chord}
(an edge joining nonconsecutive vertices in the cycle).
A chordal graph with at least one vertex
must contain a vertex that is \defterm{simplicial},
that is, whose neighborhood induces
a complete subgraph.
%% NOTE: We have results for graphs with no vertices.
%% Thus, we need to be careful about the case n=0, for example,
%% in requiring a chordal graph to have a vertex (as above),
%% before concluding that is has a simplicial.
%
The \defterm{treewidth} of a graph $G$ is equal to
%$\min\{\omega(G)-1 : G\subseteq G', G'\ {\rm is\ chordal }\}$.
%% NOTE: The above def is certainly more concise.
%% However, it relies on \omega, which we have not defined
%% (and, sadly, I have found that things like that
%% are often not so standardized). It also uses \subseteq for
%% is-a-subgraph-of, which isn't quite right. Putting it all
%% together, I have to go with the old, wordy definition. -GGC-
one less than the
smallest possible clique number of a chordal graph of which $G$
is a subgraph.

A special kind of chordal graph is a \defterm{$k$-tree},
inductively defined as follows:
given a nonnegative integer $k$,
the complete graph $K_{k+1}$ is a $k$-tree.
If $G$ is a $k$-tree, then the graph obtained by adding a new vertex
and joining it to every vertex of some $k$-clique of $G$,
is also a $k$-tree.
%
Equivalently, a graph $G$ is a $k$-tree if $G$ has treewidth $k$
and is edge-maximal with respect to that property.
%
Two well known facts about $k$-trees that we will use
are that a $k$-tree cannot be disconnected by the
removal of fewer than $k$ vertices,
and that a $k$-tree cannot contain a subdivision of the complete graph
$K_{k+2}$.
%
(For more on $k$-trees and treewidth,
see Diestel~\cite{Die2000}
or other references~\cite{Bod1998, Ree1997}.)

Suppose we assign numerical weights to the vertices of a graph $G$.
The \defterm{weight} of $G$, denoted by $w(G)$,
is the sum of the weights of the vertices of $G$.
The weight of a set $U\subseteq V(G)$,
denoted by $w(U)$,
is the sum of the weights of the elements of $U$.

If $S$ is a set, then we abbreviate $S\cup \{x\}$ by $S+x$,
and we abbreviate $S-\{x\}$ by $S-x$.


\subsection{Discussion of Results} \label{Ss:results}

The results in this paper concern a graph parameter
that we denote by $f_d(G)$.
%% Used to say "... concern the following graph parameter."
%% Since r_{k,d} is defined in a math display below, this might
%% lead the reader to think we are talking about r_{k,d}. Above
%% change is to avoid this.
Given a graph $G$, for each nonnegative integer $d$
we define $f_d(G)$ to be the maximum order
of an induced forest in $G$ having maximum degree at most $d$.

For nonnegative integers $k$, $d$, we define a real number
\[
r_{k,d} := \frac{2d}{kd+d+1}.
\]
As we will see, for graphs with treewidth $k$ and order $n$,
the best lower bound for $f_d(G)$ is often something like
$r_{k,d}\cdot n$.

The primary goal of this paper is to prove the following result.

\begin{theorem} \label{Th:if-nice}
Let $k$, $d$ be integers, with $k\ge 2$ and $d\ge 2$.
If $G$ is a graph with order $n\ge 1$ and treewidth at most $k$,
then
\[
f_d(G) \ge \left\lceil \frac{2dn+2}{kd+d+1} \right\rceil
 = \left\lceil r_{k,d}\cdot n + \frac{r_{k,d}}{d} \right\rceil,
\]
unless $G \in \{K_{1,1,3},K_{2,3}\}$ and $k=d=2$.\ggcnopf\end{theorem}

The special case of Theorem~\ref{Th:if-nice}
when $G$ is outerplanar and $d=2$
was proven by Pelsmajer~\cite[Thm.~1]{Pel2004}.

If a chordal graph has clique number $\omega$,
then its treewidth is $\omega-1$.
Further, $K_{2,3}$ is not chordal,
and so Theorem~\ref{Th:if-nice} has the following corollary
(which easily implies Theorem~\ref{Th:if-nice}, as well).

\begin{corollary} \label{Co:if-chordal}
Let $d \ge 2$.
If $G$ is a chordal graph with order $n$
and clique number $\omega \ge 3$,
then
\[
f_d(G) \ge \left\lceil \frac{2dn+2}{\omega d+1} \right\rceil,
\]
unless $G \cong K_{1,1,3}$ and $d=2$.\ggcnopf\end{corollary}
%% NOTE: At first glance, some things are left out of the above
%% result. However, we do not need to say n\ge 1, since we have
%% omega\ge 3. And when G is K_{1,1,3}, we do not need to say
%% anything about treewidth or clique number, since omega = 3.

In Section~\ref{S:pf} we prove Theorem~\ref{Th:if-nice}.

In Section~\ref{S:sharp} we discuss the sharpness of Theorem~\ref{Th:if-nice}.
We construct
examples to show that, for each $k,d\ge 2$,
the bound of Theorem~\ref{Th:if-nice} is tight to within $1$
for all $n\ge 1$,
and exactly sharp for infinitely many values of $n$.
We conclude that the coefficient of $n$
in Theorem~\ref{Th:if-nice} (i.e., $r_{k,d}$)
cannot be improved.

In Section~\ref{S:otherkd} we discuss
similar questions for $k<2$ and for $d<2$.
We observe that the bound of Theorem~\ref{Th:if-nice}
does not hold when $d=1$.
We conjecture that in this case a slightly weaker bound holds,
with no ``$+2$'' in the numerator.

\begin{conjecture} \label{J:d=1_a}
Let $k\ge 0$.
If $G$ is a graph with order $n$ and treewidth at most $k$,
then
\[
f_1(G) \ge \left\lceil \frac{2n}{k+2} \right\rceil
 = \left\lceil r_{k,1}\cdot n \right\rceil.\ggcnopf
\]
\end{conjecture}

We show that, as with Theorem~\ref{Th:if-nice},
the above bound is tight to within $1$, if it holds.

The question of whether we can place ``$+2$''
in the numerator may seem minor.
However, it has a significant impact on how we handle questions
about sharpness.
If there is no extra constant in the numerator,
then our bound is simply a fraction of $n$,
as in Conjecture~\ref{J:d=1_a},
and we can reasonably expect to prove sharpness
using a single graph as an example;
larger examples can be constructed using disjoint unions of copies
of this graph.
However, if there is a constant in the numerator,
as in Theorem~\ref{Th:if-nice},
then we will need to construct an infinite family of graphs
in order to prove sharpness.

We prove Conjecture~\ref{J:d=1_a} for $k\le 3$.
For $k\ge 4$, we prove a weaker bound:
$f_1(G) \ge (2n+2)/(2k+3)$.
We also cover the cases $d=0$ and $k=0,1$,
and we discuss sharpness.

In Section~\ref{S:surf}, we discuss related
conjectures and results for planar graphs and
graphs on other surfaces, including the following conjecture.

\begin{conjecture} \label{J:planar-alld_a}
Let $d\ge 2$ be an integer.
If $G$ is a planar graph with order $n\ge 1$,
then
\[
f_d(G) > \frac{2dn}{4d+1} = r_{3,d}\cdot n.\ggcnopf
\]
\end{conjecture}


\subsection{Related Work}

We conclude Section~1 with a discussion of a related paper.

Bose, Dujmovi\'c, and Wood~\cite{BDW2006} considered
a problem similar to ours.
They examine a graph parameter that we will denote by $\hat{f}_d(G)$:
the maximum order of an induced forest in $G$ whose vertices all
have degree at most $d$ \emph{in the original graph}.
Equivalently, they first discard all vertices of $G$
with degree greater than $d$, and
then find the maximum order of an induced forest in the graph that remains.
Like us, they focus on graphs with given order,
whose treewidth is at most some integer $k$.
For each triple $k,d,n$ with $k\ge 1$, $d\ge 2k-1$, and $n\ge 2k+1$,
they prove the following bound:
%% NOTE: We used to say this is "tight". Bose et al use this same
%% word, but to them it means best possible, except for o(n) terms.
%% However, they give lower-order terms below. So I am not sure
%% in exactly what sense this bound is "tight". Perhaps the word
%% is best left out. -GGC-
\[
\hat{f}_d(G) \ge
  \left(\frac{d-2k+1}{d-\frac{3}{2}k+1+\frac{1}{k+1}}\right)
  \left(\frac{2}{k+1}\right)n
  + \frac{2k}{d-\frac{3}{2}k+1+\frac{1}{k+1}},
\]
%% NOTE: Here is the actual lower bound from the Bose et al. paper.
%%
%% For $k\ge t\ge 0$, $d\ge\max\{2k-1,1\}$, and $n\ge 2k+1$,
%%\[
%%\left(\frac{d-2k+1}{d-\frac{3}{2}k+1+\frac{t(t+1)}{2(k+1)}}\right)
%%\left(\frac{t+1}{k+1}\right)n
%%+ \frac{k(t+1)}{d-\frac{3}{2}k+1+\frac{t(t+1)}{2(k+1)}}.
%%\]
%%
%% The first bound above is this with t set to 1.
%% Both formulas above (uncommented & commented)
%% checked by GGC 21 & 27 Aug 2009
for $G$ a graph with order $n$ and treewidth at most $k$.

Clearly, $\hat{f}_d(G) \le f_d(G)$.
Further, if $k$ and $n$ are fixed and $d$ increases without bound,
then the best lower bounds for $f_d$ and $\hat{f}_d$
both approach $2n/(k+1)$.
On the other hand, for fixed $k$, $d$ with $d\le 2k-1$,
the best lower bound for $\hat{f}_d$ is given
by a constant~\cite[notes after Thm.~5.1]{BDW2006},
while $f_d$ grows with $n$ for all values of $k$, $d$.
It is thus unsurprising that proving our results
requires rather different methods.

The main result of Bose \textit{et al.}~\cite[Thm.~5.1]{BDW2006}
is actually more general:
they seek large induced subgraphs
of treewidth at most some given $t$.
Above we compared our result with the special case of theirs
when $t=1$.
We ask whether our result can be similarly extended
to subgraphs of given treewidth.

\begin{problem}
Generalize Theorem~\ref{Th:if-nice}
to include lower bounds for the order
of induced subgraphs of given treewidth.\ggcnopf\end{problem}


\section{Proof of Theorem~\ref{Th:if-nice}} \label{S:pf}

Rather than prove Theorem~\ref{Th:if-nice} directly,
we use a loaded induction involving \emph{partial vertices}
(introduced by Pelsmajer~\cite{Pel2004}).
Partial vertices are vertices of degree at most $1$
that are required to be in the induced forest.
When determining whether the induced forest is large enough,
partial vertices in the forest count for less than other vertices.
We denote the set of partial vertices by $P$.

The actual result we will prove is the following;
Theorem~\ref{Th:if-nice} follows by setting $P=\varnothing$.

\begin{lemma} \label{L:if-full}
Let $k$, $d$ be integers, with $k\ge 2$ and $d\ge 2$.
Let $G$ be a graph with order $n\ge 1$ and treewidth at most $k$,
and let $P\subseteq V(G)$ be an independent set,
so that each vertex in $P$ has degree at most $1$ in $G$.
Let each vertex of $P$ have weight
\[
p:=\frac{2}{kd-d+1},
\]
and let each other vertex of $G$ have weight $1$.
Then there exists a set $U$, with $P\subseteq U\subseteq V(G)$,
such that $G[U]$ is a forest with maximum degree at most $d$,
and
\[
w(U) \ge \frac{2d\cdot w(G)+2}{kd+d+1}
 = r_{k,d}\cdot w(G) + \frac{r_{k,d}}{d},
\]
unless $G \in \{K_{1,1,3},K_{2,3}\}$,
$P=\varnothing$, and $k=d=2$.\end{lemma}

Note that $K_{1,1,3}$ and $K_{2,3}$ contain independent sets of
size~$3$, as well as other sets of $3$ vertices that
induce forests of maximum degree at most~$2$.  If
$G\in\{K_{1,1,3},K_{2,3}\}$ and $k=d=2$, then $3 = \frac{2d\cdot
w(G)+1}{kd+d+1}$.

\begin{proof}[Proof of Lemma~\ref{L:if-full}]
% Need "Proof of ..." as long as there is text between
% the statement of the result and its proof.
Let $k$, $d$, $G$, $n$, $P$, $p$, and the vertex weights
be as in the statement of the lemma.
A vertex of weight $p$ is a \localdefterm{partial vertex};
other vertices are \localdefterm{full}.
%
We proceed by induction on $w(G)$;
this is valid because $w(G)$ can always be written as
a rational number with denominator $kd-d+1$.

\medskip

We may assume that $V(G-P)$ is nonempty, since otherwise $U=P=V(G)$ suffices,
with $w(U)$ being exactly the required minimum when $|P|=1$,
and strictly greater otherwise.
%details are obvious:
%Since V(G)=P, G[U] is a forest of maximum degree 1.
%And $d\ge 1$, so that's good.
%Also w(U)=w(G), which suffices since r_{k,d}\le 1,
%which itself is easily observed:
%\frac{2d}{kd+d+1} \le {kd}{kd+d+1} < {kd+d+1}{kd+d+1} = 1

We may also assume that $G-P$ is either a $k$-tree
or a complete graph with order at most $k+1$.
%
If it is not, then we can add edges to $G-P$,
without increasing its treewidth beyond $k$,
until it lies in one of these categories.
A set $U$ that meets the requirements for this modified graph
will meet the requirements for the original graph, unless
$k=d=2$,
the modified graph lies in $\{K_{1,1,3},K_{2,3}\}$,
and the original graph does not.
%
However, if the original graph is a $5$-vertex graph
of treewidth at most $2$,
other than $K_{1,1,3}$ or $K_{2,3}$,
then there is always a way to add edges
so that the modified graph is a $2$-tree
other than $K_{1,1,3}$ (or $K_{2,3}$, which is not a $2$-tree).

We may further assume that each partial vertex has degree equal to $1$;
otherwise,
modify $G$ by adding an edge from each isolated partial vertex
to an arbitrary vertex of $G-P$.
Any solution for the modified graph will suffice for the original graph.

Since $G-P$ is connected, each partial vertex has a neighbor,
and the partial vertices form an independent set,
it follows that $G$ is connected.

\runinhead{How Our Argument Works---}We
will break the argument into cases.
In all cases of the proof except the ``Base Cases'',
we define a graph $G'$ based on $G$.
We do this by removing vertices from $G$ and/or
making full vertices partial;
sometimes we also add new partial vertices.
This $G'$ will always have order at least~$1$,
treewidth at most $k$,
and weight strictly less than $w(G)$.
Where possible,
we apply the induction hypothesis to $G'$ to find a vertex set $U'$
that is a solution for $G'$.
We then use this $U'$ to construct the required vertex set $U$.

We cannot apply the induction hypothesis to $G$ if
%it is possible that
$k=d=2$ and $G' \in \{K_{1,1,3},K_{2,3}\}$.
If we know that $G'$ contains at least one partial vertex,
then this is not a problem;
however, in some cases, there is the possibility
of $G'$ having no partial vertices.\footnote{There are six cases
later in the proof in which it is possible
both that $G'$ contains no partial vertices
and that $k=d=2$:
those labeled Reductions A \& B, C2, C8, C12, and C14.}
When $G'\in\{K_{1,1,3},K_{2,3}\}$ we may simply specify $U$ directly.
Another option is to set $U'$ to be a $3$-vertex set in $G'$,
and then construct $U$ based on $U'$, as before.
We will discuss this option further shortly.

Having constructed $U$, we need to show that it induces a forest
in $G$ meeting the degree requirement (maximum degree at most $d$)
and the weight requirement ($w(U)$ at least the required minimum).
% NOTE: We use the terms "degree requirement" and "weight requirement"
% often in the proof. They need to be introduced, as above.
Usually, the former will follow clearly from the construction of $U$
based on $U'$
and the fact that $G'[U']$ is a forest of maximum degree at most $d$.
We consider the latter.

\runinhead{Showing That $U$ Satisfies the Weight Requirement---}In
most cases, we obtain $U'$ in $G'$ by applying the induction hypothesis,
and then we define $U$ based on $U'$.
To verify that $U$ has the required weight, note that
it suffices to show that
\[
\frac{w(U)-w(U')}{w(G)-w(G')} \ge r_{k,d}.
\]

%On the other hand, if
%$k=d=2$ and $G'$ may not contain any partial vertices\footnote{This
%can happen in six cases later in the proof:
%those labeled Reductions A \& B, C2, C8, C12, and C14.},
%then $G'\cong K_{1,1,3}$ is a possibility.
In a case where $G'\in\{K_{1,1,3},K_{2,3}\}$ is a possibility
and we define $U$ based on $U'$,
we can prove that $U$ satisfies the weight requirement
by verifying the following
\localdefterm{strict weight inequality}:
\[
\frac{w(U)-w(U')}{w(G)-w(G')} > r_{k,d}.
\]
To see that this suffices,
observe that $w(U') \ge (2d\cdot w(G')+1)/(kd+d+1)$
[note the ``$+1$'' in the numerator]
when $U'$ is obtained by applying the induction hypothesis
and also when $G'\in\{K_{1,1,3},K_{2,3}\}$ and $|U'|=3$.
Now rewrite the strict weight inequality:
\begin{align*}
w(U) &> w(U') + r_{k,d}\cdot \left[w(G)-w(G')\right]\\
  &\ge \frac{2d\cdot w(G')+1}{kd+d+1}
    + \frac{2d\cdot \left[w(G)-w(G')\right]}{kd+d+1}
    = \frac{2d\cdot w(G)+1}{kd+d+1}.
\end{align*}
Since the first inequality above is strict,
and all numerators and denominators are integers,
$w(U)$ must be at least
$(2d\cdot w(G)+2)/(kd+d+1)$ [``$+2$'' in the numerator], as desired.

\runinhead{Notes on $K_{1,1,3}$ and $K_{2,3}$---}In the subsequent argument,
whenever $k=d=2$ and $G'$ has $5$ vertices and no partial vertices,
$G'$ is always obtained by removing some vertices from $G$.
Since $G-P$ is a $k$-tree or a complete graph,
%and $G$ is connected,
% Above not necessary -GGC-
it follows that $G$ is chordal.
Since chordal graphs are closed under taking induced subgraphs,
$G'$ will be chordal as well.
The graph $K_{2,3}$ is not chordal, and so $G'\not\cong K_{2,3}$.
Thus, in the remainder of this proof,
the only special case for $G'$ is $K_{1,1,3}$;
we will never need to deal directly with $K_{2,3}$.

We will sometimes apply the following reasoning
when dealing with $G'\cong K_{1,1,3}$.

%% NOTE: The following is referenced later
%% in the document. If the text is changed, or the heading is eliminated,
%% then update the refs, too.
\begin{remark}\label{r:K113}{\rm
When $k=d=2$, $G'\cong K_{1,1,3}$,
and $G'$ is created by removing a connected subgraph $B$ from $G$,
it may be helpful to let $U'$ be a $3$-vertex set in $G'$
that contains no vertices adjacent to vertices in $B$.

To see that we can always do this,
let $N(B)$ be the vertices of $G'$ that are adjacent to vertices in $B$.
If $N(B)$ contains $2$ nonadjacent vertices or $N(B)$ contains a triangle,
then, since $B$ is connected and $G'\cong K_{1,1,3}$, there is a
subdivision of $K_4$ in $G$.
But this is impossible,
since a graph of treewidth at most~$2$ cannot contain a subdivision of $K_4$.
Therefore,
$N(B)$ contains either exactly one vertex or two adjacent vertices of $G'$.
Considering all the possibilities, we can see that
there is always a $3$-vertex set $U'$ in $G'-N(B)$
that does not form a triangle, or,
equivalently, induces a forest of maximum degree at most~$2$.
}\end{remark}
%% NOTE: As of this writing, this reasoning is used in
%% Reduction A, and cases C2 and C14. In all three of these
%% applications, G' is obtained by removing a *connected*
%% subgraph from G.
%% NEW: We could actually use this reasoning in every case except Reduction B,
%% but I don't see the benefit...
%% CHANGED: Now, in Reduction A, we only use this reasoning,
%% and not the independent set.
%% Not sure if this is an improvement for Reduction A or not, actually.


\subsection{Simple Base Cases and Reductions}

\runinhead{Base Case 1---}Suppose that $G-P$ has exactly one vertex, $v$.

If $v$ has more than $d$ (partial) neighbors,
then let $U=V(G)-v$.  This $U$ is an independent set.
Since $w(G) = w(U)+1$, the desired bound becomes
\[
w(U)\ge \frac{2d[w(U)+1]+2}{kd+d+1},
\]
which simplifies to
\[
w(U)\ge \frac{2(d+1)}{kd-d+1} = (d+1)p.
\]
Because $U$ has at least this weight,
the weight requirement is satisfied.

Otherwise, $G$ is a tree with maximum degree at most $d$.
Let $U=V(G)$, so that $w(G) = w(U)$.
The desired bound becomes
\[
w(U) \ge \frac{2d\cdot w(U)+2}{kd+d+1},
\]
which simplifies to
\[
w(U)\ge \frac{2}{kd-d+1} = p,
\]
and again the weight requirement is satisfied.

\medskip

Henceforth, we assume that $G-P$ has at least two vertices.

\runinhead{Reduction A---}Suppose that
a full vertex $v$ of $G$ has $d$ or more partial neighbors.
(See the first graph in Figure~\ref{F:A,B,3a}.)

Remove $v$ and its partial neighbors, and let $G'$ be the graph that remains.

First suppose that $G'\not\cong K_{1,1,3}$ or $k>2$ or $d>2$.
There is at least one full vertex in $G'$
(otherwise $G$ is Base Case 1),
and so we find $U'$ in $G'$ by the induction hypothesis.
%% NOTE: The above is important. If there are no vertices left,
%% then we cannot apply the induction hypothesis. This is why we
%% handle both the no-fulls case and the one-full case in Base Case 1.
Let $U$ be $U'$ together with the removed partial vertices.
Then $G[U]$ is $G'[U']$ plus isolated vertices,
and so $G[U]$ is a forest satisfying the degree requirement.
We have
\begin{align*}
\frac{w(U)-w(U')}{w(G)-w(G')} &\ge \frac{dp}{1+dp}
  \quad&&\\
  &= \frac{2d}{kd+d+1}
    \quad&&\text{set $\textstyle p=\frac{2}{kd-d+1}$, simplify}\\
  &= r_{k,d},
\end{align*}
and so $G[U]$ also satisfies the weight requirement,
and we are done.

Now, suppose that $G'\cong K_{1,1,3}$
and $k=d=2$.
Let $s$ be the number of partial vertices adjacent to $v$.
Apply Remark~\ref{r:K113}
to obtain a $3$-vertex induced forest in $G'$
that contains no vertices adjacent to $v$ in $G$.

If $s\ge 3$, then let $U$ consist of this $3$-vertex set,
together with the $s$ partial vertices.
Since $k=d=2$, we have $p=2/3$.
Substituting $w(U) = 3+sp$, $w(G) = 6+sp$, $p=2/3$, and $k=d=2$ into
\[
w(U) \ge \frac{2d\cdot w(G) + 2}{kd+d+1}
\]
and simplifying, we obtain $s\ge 5/2$,
which holds when $s\ge 3$.

On the other hand, if $s=2$, then
let $U$ consist of the $3$-vertex set constructed above,
plus $v$ and the $2$ partial vertices.
Then $w(U) = 4+2p$, while $w(G) = 6+2p$.
Substituting and simplifying, as above,
we can see that $w(U)$ is again large enough.

\medskip

Henceforth, we assume that each full vertex of $G$
has fewer than $d$ partial neighbors.

\runinhead{Reduction B---}Suppose that a vertex $v$
that is simplicial in $G-P$ has one or more partial neighbors in $G$.
(See the second graph in Figure~\ref{F:A,B,3a}.)

Remove these partial neighbors,
and let $G'$ be the graph that remains.
If $G'\cong K_{1,1,3}$ and $k=d=2$,
then let $U'$ be a $3$-vertex independent set in $G'$;
otherwise, find $U'$ by the induction hypothesis.
Let $U$ be $U'$ together with the removed partial vertices.
Then
\[
\frac{w(U)-w(U')}{w(G)-w(G')}
=1 > r_{k,d},
\]
and so the strict weight inequality holds.

We consider the degree requirement.
If $v\in U'$, then, since $v$ is simplicial in $G-P$,
the degree of $v$ in the forest $G'[U']$ is at most $1$.
Therefore, since $v$ has fewer than $d$ partial neighbors in $G$,
the degree of $v$ in $G[U]$ is at most $d$.
Thus, the degree requirement is satisfied.

\medskip

Henceforth, we assume that each vertex that is simplicial in $G-P$
has no partial neighbors in $G$.

%\includegraphics{ReductionAB3a.eps}}
\begin{figure}[ht]
\begin{center}
\begin{tabular}{ccccc}
\begin{pspicture}(0.85,0.3)(4.15,3.76)
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
  \psarc[linestyle=dashed,dash=6pt 4pt](2.5,3.5){2.3}{220}{320}
%  \pspolygon[linewidth=0,fillstyle=solid,fillcolor=mygray](1.02,2.675)(3.98,2.675)(2.5,1.2)
%  \psellipse[fillstyle=solid,fillcolor=mygray](2.5,3)(1.65,0.76)
  \psdot[dotsize=4pt 2](2.5,1.2)\rput(2.3,1.4){$v$}
%  \psline(1.02,2.675)(2.5,1.2)(3.98,2.675) %y
%below y:
  \pscurve(2.5,1.2)(1.9,0.8)(1.6,0.3)
  \pscurve(2.5,1.2)(2.1,0.8)(1.9,0.3)
  \pscurve(2.5,1.2)(2.3,0.8)(2.2,0.3)
  \psline(2.5,1.2)(2.5,0.3)
  \pscurve(2.5,1.2)(2.7,0.8)(2.8,0.3)
  \pscurve(2.5,1.2)(2.9,0.8)(3.1,0.3)
  \pscurve(2.5,1.2)(3.1,0.8)(3.4,0.3)
  \psdots[dotstyle=Bo,dotsize=4pt 2](2.2,0.3)(2.5,0.3)(2.8,0.3)
  \psdots[dotstyle=Bo,dotsize=4pt 2](1.6,0.3)(1.9,0.3)(3.1,0.3)(3.4,0.3)
  \end{pspicture}
& \qquad &
\begin{pspicture}(0.85,0.3)(4.15,3.76)
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
  \pspolygon[linewidth=0,fillstyle=solid,fillcolor=mygray](1.02,2.675)(3.98,2.675)(2.5,1.2)
  \psellipse[fillstyle=solid,fillcolor=mygray](2.5,3)(1.65,0.76)
  \psdot[dotsize=4pt 2](2.5,1.2)\rput(2.2,1.2){$v$}
  \psline(1.02,2.675)(2.5,1.2)(3.98,2.675) %y
%below y:
  \pscurve(2.5,1.2)(2.3,0.8)(2.2,0.3)
  \psline(2.5,1.2)(2.5,0.3)
  \pscurve(2.5,1.2)(2.7,0.8)(2.8,0.3)
  \psdots[dotstyle=Bo,dotsize=4pt 2](2.2,0.3)(2.5,0.3)(2.8,0.3)
  \end{pspicture}
& \qquad &
\begin{pspicture}(0.85,0.3)(4.15,3.76)
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt \pspolygon[linewidth=0,fillstyle=solid,fillcolor=mygray](2.91,3.42)(4.6,3)(3.1,1.7)
\pspolygon[linewidth=0,fillstyle=solid,fillcolor=mygray](2.91,1.58)(4.6,2)(3.1,3.3) \psellipse[fillstyle=solid,fillcolor=mygray](2.5,2.5)(1,1)
  \rput(2.5,2.8){$G^*$}
  \psdots[dotsize=4pt 2](4.6,2)(4.6,3)
  \psdots[dotsize=1pt 1](4.6,2.3)(4.6,2.5)(4.6,2.7)
  \rput(5.1,2.5){($h$)}
%  \psdot[dotsize=4pt 2](2.5,1.2)\rput(2.1,1.0){$y$}
  \psline(2.91,3.42)(4.6,3)(3.1,1.7)
  \psline(2.91,1.58)(4.6,2)(3.1,3.3)
%
  \psline(1.4,1.4)(1.9,2.1)(1.15,1.7)
  \psline(1.85,1.15)(2.3,1.8)(2.2,1.0)
  \psline(2.5,0.9)(2.7,1.8)(2.8,0.9)
  \psdots[dotsize=4pt 2](1.9,2.1)(2.3,1.8)(2.7,1.8)
  \psdots[dotstyle=Bo,dotsize=4pt 2](1.4,1.4)(1.15,1.7)
  \psdots[dotstyle=Bo,dotsize=4pt 2](1.85,1.15)(2.2,1.0)(2.5,0.9)(2.8,0.9)
  \rput(1.3,0.9){$P$}
\end{pspicture}
\end{tabular}
\caption{Reduction A, Reduction B, and Base Case 3.
Partial vertices are shown as hollow vertices, and ovals represent cliques.}
\label{F:A,B,3a}
\end{center}
\end{figure}

\runinhead{Base Case 2---}Suppose that $G-P$ is a complete graph.

Since every vertex of $G-P$ is simplicial,
by Reduction B there are no partial vertices.
Thus, $G = G-P$ is a complete graph with from $2$ to $k+1$ vertices.
%% NOTE: Using Base Case 1 here (so G is not K_1).
Let $U$ be any two vertices of $G$.
Then $w(U) = 2$, while $w(G)\le k+1$.
Thus,
\[
w(U)
%= 2
= \frac{2d(k+1)+2}{d(k+1)+1}
\ge \frac{2d\cdot w(G)+2}{kd+d+1},
\]
and so the weight requirement is satisfied.

\medskip

Henceforth we assume that $G-P$ is not a complete graph.

Let $G^*$ be the subgraph obtained from $G-P$
by removing every vertex that is simplicial in $G-P$.
%% NOTE: We want to avoid suggesting that we are talking about
%% a perfect elimination ordering above.
Because $G-P$ is connected, but not complete,
it contains a vertex that is not simplicial,
and so $V(G^*)\ne \varnothing$.
Since $G^*$ is chordal,
there must be a vertex that is simplicial in $G^*$.

\runinhead{Base Case 3---}Suppose that
every vertex that is simplicial in $G^*$ dominates $G-P$.
%% NOTE: The point of Base Case 3 is to get us a depth 2 lobe
%% if we are not in it.

A simplicial vertex of $G^*$ dominates $G^*$, and so
$G^*$ must be a complete graph.
Then every vertex of $G^*$ is simplicial in $G^*$,
and so each vertex of $G-P$
is adjacent to all of $V(G^*)$.
Since $G-P$ is a $k$-tree but not a complete graph,
its (two or more) simplicial vertices cannot be adjacent.
Therefore, for each simplicial vertex of $G-P$,
its $k$ neighbors in $G-P$ are precisely the set $V(G^*)$.

We conclude that $G-P$ is formed from $G^*\cong K_k$
and an independent set $V(G)-P-V(G^*)$ of at least $2$ vertices,
with every vertex of the former adjacent to every vertex of the latter.
Each vertex in $G^*$
has at most $d-1$ partial neighbors in $G$ (by Reduction A),
and each vertex in $V(G)-P-V(G^*)$ has no partial neighbors (by Reduction B).
Let $h=|V(G)-P-V(G^*)|$,
and let $t=|P|$.
(See the last graph in Figure~\ref{F:A,B,3a}.)
%% I think it's clear from context, after a slight rewrite.
%We have two subcases:
%Subcase 3a, in which some vertex of $G^*$
%has at most $d-h$ partial neighbors,
%and Subcase 3b, in which each vertex of $G^*$
%has at least $d-h+1$ partial neighbors.

\runinhead{Subcase 3a.}
Suppose that some vertex $v$ of $G^*$
has at most $d-h$ partial neighbors in $G$.

Let $U$ consist of $v$, the $h$ independent-set vertices,
and the $t$ partial vertices.
Since $v$ has at most $d$ neighbors in $U$,
the degree requirement is satisfied.
Observe that $w(U) = h+tp+1$ and $w(G) = h+tp+k$.
Substituting these into
\[
w(U) \ge \frac{2d\cdot w(G) + 2}{kd+d+1}
\]
and simplifying, we obtain $h+tp\ge 1$,
which holds,
and so the weight requirement is satisfied as well.

\runinhead{Subcase 3b.}
Suppose that each vertex of $G^*$
has at least $d-h+1$ partial neighbors in $G$.

Let $U=V(G)-V(G^*)$.
%This $U$ is an independent set;
%we consider its weight.
Observe that
$w(U)=h+tp$ and $w(G)=h+tp+k$.
Making these substitutions, and using $p=2/(kd-d+1)$,
we can show that the desired bound is equivalent to
\[
h+tp\ge 2+dp.
\]
Since $G^*\cong K_k$
and each vertex of $G^*$
has at least $d-h+1$ partial neighbors,
we have $t\ge k(d-h+1)$.
Thus, to verify the required bound
it suffices to show that $h+k(d-h+1)p\ge 2+dp$.
Substituting $p=2/(kd-d+1)$, we can show that this is equivalent to
\[
(d-3)h(k-1) + h(k-2)+2(k-1) \ge 0.
%% NOTE: The above inequality has the nice property that
%% every part of the left-hand side
%% is *obviously* nonnegative when d >= 3 and k >= 2.
%% This inequality is the simplest equivalent one
%% that I could come up with that has that property. -GGC-
\]
This holds when $d\ge 3$, since $h,k\ge 2$.

Thus, for the remainder of Subcase 3b, we may assume that $d=2$.
The inequality $h+tp\ge 2+dp$ becomes $h+tp\ge 2+2p$.
Since $h\ge 2$, this inequality holds if $t\ge 2$,
and so we may assume that $t$ is $0$ or $1$,
and thus some vertex of $G^*$ has no partial neighbors in $G$.
Since this subcase assumes that each vertex of $G^*$ has at least $d-h+1$
partial neighbors, we have $0\ge d-h+1$, and so $h\ge d+1=3$.

We consider the possible values of $k$, when $d=2$.
If $k\ge 3$, then $p\le 2/5$,
and so $h+tp \ge h\ge 3\ge 2+2p$, and we are done.
On the other hand, if $k=2$, then $p=2/3$,
and so $h+tp\ge 2+2p$ if $t=1$ or if $h\ge 4$.
The only remaining case for $d=2$ is
that in which $k=2$, $h=3$, and $t=0$,
in which case $G$ is $K_{1,1,3}$ and $P=\varnothing$.
Then the maximum induced forest has weight $3$,
which is less than our lower bound.
However, this is not a problem, since,
when $k=d=2$, the graph $K_{1,1,3}$
is an exception to our result.

\runinhead{Summary of Simple Cases---}For the remainder of this proof,
we assume that all of the following hold:
\begin{itemize}
\item $G$ is connected,
\item $G-P$ is a $k$-tree,
\item no vertex of $G$ is adjacent to more than $d-1$ partial vertices,
\item each simplicial vertex of $G-P$ has no partial neighbors in $G$,
and
\item there is a vertex that is simplicial in $G^*$
and that does not dominate $G-P$.
%% NOTE: Above lengthy wording is to avoid confusion;
%% we want to rule out the idea that
%% the vertex lies in G^*, but it is simplicial in G.
\end{itemize}
In the next portion of the proof,
we will choose such a simplicial vertex $y$
and use it to construct what we call a ``lobe of depth 2''.


\subsection{Depth 2 Techniques}

\runinhead{Lobes and Depth---}Suppose that $X\subseteq V(G-P)$
induces a $k$-clique.
If removing $X$ disconnects $G-P$,
then $X$ together with any component of $G-P-X$,
is an \localdefterm{$X$-lobe} of $G-P$.
If an induced subgraph is an $X$-lobe for some $X$,
then it is a \localdefterm{lobe};
the clique induced by $X$ is its \localdefterm{clique of attachment}.
%% I don't think we need to consider an arbitrary subgraph, a lobe $B$ is good.
Consider the following procedure, performed on a lobe $B$ of $G-P$:
remove all vertices of $B$ that are simplicial %in the subgraph
and that do not lie in $X$.
%Beginning with a lobe $B$ of $G-P$,
The number of times we must perform this procedure,
to leave only $X$ remaining,
is the \localdefterm{depth} of $B$.

An \localdefterm{$X$-lobe} $B$ of $G$ is an $X$-lobe $B'$ of $G-P$,
together with all partial vertices adjacent to $V(B')-X$
with their incident edges.
The \localdefterm{depth} of a lobe $B$ of $G$
is the depth of $B'=B-P$ as a lobe of $G-P$.

The main portion of our proof consists of a number of cases
in which we handle lobes of depth $2$.

\runinhead{A Lobe of Depth 2---}Again,
some vertex $y$ that is simplicial in $G^*$, does not dominate $G-P$.
Let $X$ be the neighborhood of $y$ in $G^*$.
Then $X$ induces a $k$-clique;
this is the clique of attachment of a depth $2$ lobe $B_2$ in $G$.
Since $y$ dominates $B_2$, but not $G-P$,
we see that $B_2-P$ is not all of $G-P$, as required.

\begin{figure}[hb]
\begin{center}
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
\begin{pspicture}(0,0.3)(5,3.76)
  \pspolygon[linewidth=0,fillstyle=solid,fillcolor=mygray](1.02,2.675)(3.98,2.675)(2.5,1.2)
  \pspolygon[linewidth=0,fillstyle=solid,fillcolor=mygray](1.05,3.15)(0,1.3)(2.92,2.575) %left of y
  \pspolygon[linewidth=0,fillstyle=solid,fillcolor=mygray](3.95,3.15)(5,1.3)(2.08,2.575) %right of y
  \pspolygon[linewidth=0,fillstyle=solid,fillcolor=mygray](3.995,2.97)(3.75,1.1)(1.95,2.65) %slight right of y
  \psellipse[fillstyle=solid,fillcolor=mygray](2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psellipse(2.15,3)(1.15,0.58)
  \psellipse(2.85,3)(1.15,0.58)
  \psdot[dotsize=4pt 2](1.25,3)
  \psdot[dotsize=4pt 2](3.75,3)
  \psdot[dotsize=4pt 2](2.5,1.2)\rput(2.2,1.0){$y$}
  \psdots[dotsize=4pt 2](0,1.3)(5,1.3) %left/right of y
  \psdot[dotsize=4pt 2](3.75,1.1) %slight right of y
  \psline(1.02,2.675)(2.5,1.2)(3.98,2.675) %y
  \psline(1.05,3.15)(0,1.3)(2.92,2.575) %left of y
  \psline(3.95,3.15)(5,1.3)(2.08,2.575) %right of y
  \psline(3.995,2.97)(3.75,1.1)(1.95,2.65) %slight right of y
  \pscurve(2.5,1.2)(1.1,1.38)(0,1.3) %y - left of y
  \pscurve(2.5,1.2)(3.9,1.38)(5,1.3) %y - right of y
  \pscurve(2.5,1.2)(3.1,1.2)(3.75,1.1) %y - slight right of y
%below y:
  \pscurve(2.5,1.2)(2.3,0.8)(2.2,0.3)
  \psline(2.5,1.2)(2.5,0.3)
  \pscurve(2.5,1.2)(2.7,0.8)(2.8,0.3)
  \psdots[dotstyle=Bo,dotsize=4pt 2](2.2,0.3)(2.5,0.3)(2.8,0.3)
\end{pspicture}
%
\caption{A lobe $B_2$ of depth~2, with $m=3$, $s=3$, and $q=2$.
Note that $B_2-X$ is a star centered at $y$.}
\label{F:depth 2 lobe}
\end{center}
\end{figure}

If we remove $X$ from the lobe $B_2$,
then the resulting graph is a star centered at $y$
(partial neighbors of vertices in $X$ are not part of $B_2$.)
Let $m$ be the number of full leaves of the star $B_2-X$.
Then $m\ge 1$, since otherwise $y$ is simplicial in $G-P$.
Each of these leaves is adjacent to $y$ and to exactly $k-1$ vertices in $X$.
Let $s$ be the number of partial leaves of $B_2-X$,
so that $0\le s\le d-1$, by Reduction A.

Label the elements of $X$ as $x_1, x_2, \dots, x_k$.
Let $q$ be the number of distinct sets of vertices in $B_2$
that are neighborhoods of full leaves of $B_2-X$.
(For example, all full leaves of $B_2-X$ have the same neighborhood
if and only if $q=1$.)
Since $X$ has $k$ distinct subsets of size $k-1$, we have $q\le k$.

See Figure~\ref{F:depth 2 lobe} for an illustration of a depth 2 lobe.

We note that every depth $2$ lobe of $G$
can be found in the above manner
(by choosing a simplicial vertex in $G^*$
that does not dominate $G-P$, and so on).

\runinhead{Cases Involving Depth 2 Lobes---}Having
found a lobe $B_2$ of depth $2$,
we handle it based on $k$ and $d$,
as well as the values of $m$, $s$, and $q$ (defined above)
for $B_2$.

We split this portion of the proof into 14 cases
that cover all possible values of
$k$, $d$, $m$, $s$, and $q$,
with $k,d\ge 2$,
$m\ge 1$,
$0\le s\le d-1$,
and $1\le q\le \min\{k,m\}$.
%
\renewcommand{\labelenumi}{(C\arabic{enumi})} % Labels (C1), (C2), etc.
\newcounter{saveenumi1}
\begin{enumerate}
\item $m=1$ and $s\le d-2$.
\item $m=1$ and $s=d-1$.
\item $m=2$ and $s\ge 1$.
\setcounter{saveenumi1}{\value{enumi}}
\end{enumerate}
%
%Next, we list cases in which $k$ is required to be at least $3$.
%
\begin{enumerate}
\setcounter{enumi}{\value{saveenumi1}}
\item $k\ge 3$, $m\ge 2$, and $m+s\le d$.
\item $k\ge 3$, $m\ge 3$, $m+s\ge d+1$,
and either $m\ge 4$ or $k\ge 4$.
\item $k=3$, $m=3$, and $q\le 2$.
\item $k=3$, $m=3$, and $q=3$.
\setcounter{saveenumi1}{\value{enumi}}
\end{enumerate}
%
%Lastly, we list cases in which $k=2$.
%
\begin{enumerate}
\setcounter{enumi}{\value{saveenumi1}}
\item $k=2$, $m=2$, $s=0$, and $d=2$.
\item $k=2$, $m=2$, $s=0$, $q=1$, and $d\ge 3$.
\item $k=2$, $m=2$, $s=0$, $q=2$, and $d\ge 3$.
\item $k=2$, $m\ge 3$, and $d\ge 3$.
\item $k=2$, $m=3$, $q=1$, and $d=2$.
\item $k=2$, $m=3$, $q=2$, and $d=2$.
\item $k=2$, $m\ge 4$, and $d=2$.
\end{enumerate}

All the possibilities with $m=1$ are covered by C1 and C2.
For $m=2$, if $s\ge 1$, then we are in Case C3;
otherwise, for $k=2$ we are in one of C8, C9, C10,
and for $k\ge 3$ we are in C4.  For $k\ge 3$ and $m\ge 3$,
Cases C4 and C5 cover all possibilities except for some with
$k=m=3$, which are covered by Cases C6 and C7.
For $k=2$ and $m\ge 3$, all possibilities are covered by Cases C11,
C12, C13, and C14.
(Some cases overlap.)
%% NOTE: For example, C3 & C4 overlap

Thus, the 14 cases cover every possible value of $k$, $d$, $m$, $s$, and $q$.

\runinhead{Handling the Depth 2 Cases---}We discuss
how to handle each of the above cases,
in the order listed.

We first give two facts, which can easily be verified.

\runinhead{Facts.}
For all $k\ge 2$ and $d\ge 2$,
both of the following hold.
\enumromanparen % Labels (i), (ii), etc.
\begin{enumerate}
\item $\displaystyle\frac{2-p}{k+1-p} = r_{k,d}$.
\item $\displaystyle\frac{2 + (d-1)p}{k + 2 + (d-1)p} = r_{k,d}$.
\end{enumerate}

We now cover the cases in the order listed above.

\runinhead{Case C1.}
Suppose that
$m=1$ and $s\le d-2$.

% Strategy N1S
Since $m=1$, there is one vertex in $X$ (say $x_1$)
that is not adjacent to the full leaf of the star $B_2-X$.
(See the first graph in Figure~\ref{F:C1C2C3}.)
Remove all vertices of the lobe $B_2$,
except for $x_1$ and $y$,
and make $y$ partial,
to obtain $G'$.
Find $U'$ by the induction hypothesis,
and let $U$ be $U'$ plus all (full and partial) leaves of $B_2-X$.
Note that $y\in U$.
Then $G[U]$ is a forest satisfying the degree requirement.
We check the weight requirement.

\begin{align*}
\frac{w(U)-w(U')}{w(G)-w(G')} &= \frac{sp+1+(1-p)}{sp+k+(1-p)} \quad&&\\
 &\ge \frac{2-p}{k+1-p} \quad&&\text{minimized when $s=0$}\\
 &= r_{k,d}. \quad&&\text{by Fact (i)}
\end{align*}

Since the construction of $G'$ involved
the creation of a new partial vertex,
we do not need to verify the strict weight inequality.
(We will generally not point this out in later cases.)

\runinhead{Case C2.}
Suppose that
$m=1$ and $s=d-1$.

% Strategy S
(See the first graph in Figure~\ref{F:C1C2C3}
for an illustration of this case.)
Remove the entire lobe $B_2$ to obtain $G'$.
If $G'\not\cong K_{1,1,3}$ or $k>2$ or $d>2$,
then find $U'$ by the induction hypothesis,
and let $U$ be $U'$ plus all vertices in $B_2-X$.
Then $G[U]$ is the disjoint union of $G'[U']$
with a star of maximum degree $d$, and the weights satisfy
\begin{align*}
\frac{w(U)-w(U')}{w(G)-w(G')} &= \frac{2+sp}{k+2+sp} \quad&&\\
% &= \frac{2 + (d-1)p}{k + 2 + (d-1)p} \quad&&\\
 &= r_{k,d}. \quad&&\text{by Fact (ii), since $s=d-1$}
\end{align*}

If $G'\cong K_{1,1,3}$ and $k=d=2$,
then we apply Remark~\ref{r:K113}
to obtain a $3$-vertex induced forest in $G'$
that contains no vertices adjacent to $X$ in $G$.
Let $U$ consist of these three vertices, $x_1$, $x_2$,
the full leaf of the star $B_2-X$, and the partial vertex
(there is only one, since $s = d-1 = 1$).
Then $w(U) = 6+p$, while $w(G) = 9+p$.
Further, $k = d = 2$, and so $p = 2/3$.
Substituting these into
\[
w(U) \ge \frac{2d\cdot w(G) + 2}{kd+d+1}
\]
and simplifying,
we see that $U$ satisfies the weight requirement.
(Note that here we constructed $U$ explicitly,
$U'$ was never defined, and
there is no need to verify the strict weight inequality.)

%\includegraphics{C1C2C3.eps}}
\begin{figure}[ht]
\begin{center}
\begin{tabular}{ccccc}
\begin{pspicture}(0.55,0.3)(5,3.76)
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
  \pspolygon[linewidth=0,fillstyle=solid,fillcolor=mygray](1.02,2.675)(3.98,2.675)(2.5,1.2)
  \pspolygon[linewidth=0,fillstyle=solid,fillcolor=mygray](3.95,3.15)(5,1.3)(2.08,2.575) %right of y
  \psellipse[fillstyle=solid,fillcolor=mygray](2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psellipse(2.85,3)(1.15,0.58)
  \psdot[dotsize=4pt 2](1.25,3)\rput(1.5,2.8){$x_1$}
  \psdot[dotsize=4pt 2](2.5,1.2)\rput(2.2,1.0){$y$}
  \psdots[dotsize=4pt 2](5,1.3) %right of y
  \psline(1.02,2.675)(2.5,1.2)(3.98,2.675) %y
  \psline(3.95,3.15)(5,1.3)(2.08,2.575) %right of y
  \pscurve(2.5,1.2)(3.9,1.38)(5,1.3) %y - right of y
%below y:
  \pscurve(2.5,1.2)(2.3,0.8)(2.2,0.3)
  \psline(2.5,1.2)(2.5,0.3)
  \pscurve(2.5,1.2)(2.7,0.8)(2.8,0.3)
  \psdots[dotstyle=Bo,dotsize=4pt 2](2.2,0.3)(2.5,0.3)(2.8,0.3)
\end{pspicture}
& \qquad &
\begin{pspicture}(0,0.3)(5,3.76)
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
  \pspolygon[linewidth=0,fillstyle=solid,fillcolor=mygray](1.02,2.675)(3.98,2.675)(2.5,1.2)
  \pspolygon[linewidth=0,fillstyle=solid,fillcolor=mygray](1.05,3.15)(0,1.3)(2.92,2.575) %left of y
  \pspolygon[linewidth=0,fillstyle=solid,fillcolor=mygray](3.95,3.15)(5,1.3)(2.08,2.575) %right of y
  \psellipse[fillstyle=solid,fillcolor=mygray](2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psellipse(2.15,3)(1.15,0.58)
  \psellipse(2.85,3)(1.15,0.58)
  \psdot[dotsize=4pt 2](1.25,3)\rput(1.5,2.8){$x_1$}
  \psdot[dotsize=4pt 2](3.75,3)\rput(3.5,2.8){$x_2$}
  \psdot[dotsize=4pt 2](2.5,1.2)\rput(2.2,1.0){$y$}
  \psdots[dotsize=4pt 2](0,1.3)(5,1.3) %left/right of y
  \psline(1.02,2.675)(2.5,1.2)(3.98,2.675) %y
  \psline(1.05,3.15)(0,1.3)(2.92,2.575) %left of y
  \psline(3.95,3.15)(5,1.3)(2.08,2.575) %right of y
  \pscurve(2.5,1.2)(1.1,1.38)(0,1.3) %y - left of y
  \pscurve(2.5,1.2)(3.9,1.38)(5,1.3) %y - right of y
%below y:
  \pscurve(2.5,1.2)(2.3,0.8)(2.2,0.3)
  \psline(2.5,1.2)(2.5,0.3)
  \pscurve(2.5,1.2)(2.7,0.8)(2.8,0.3)
  \psdots[dotstyle=Bo,dotsize=4pt 2](2.2,0.3)(2.5,0.3)(2.8,0.3)
\end{pspicture}
&  &
\begin{pspicture}(0.75,0.3)(5,3.76)
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
  \pspolygon[linewidth=0,fillstyle=solid,fillcolor=mygray](1.02,2.675)(3.98,2.675)(2.5,1.2)
  \pspolygon[linewidth=0,fillstyle=solid,fillcolor=mygray](3.95,3.15)(5,1.3)(2.08,2.575) %right of y
  \pspolygon[linewidth=0,fillstyle=solid,fillcolor=mygray](3.995,2.97)(3.75,1.1)(1.95,2.65) %slight right of y
  \psellipse[fillstyle=solid,fillcolor=mygray](2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psellipse(2.85,3)(1.15,0.58)
  \psdot[dotsize=4pt 2](1.25,3)\rput(1.5,2.8){$x_1$}
  \psdot[dotsize=4pt 2](3.75,3)\rput(3.5,2.8){$x_2$}
  \psdot[dotsize=4pt 2](2.5,1.2)\rput(2.2,1.0){$y$}
  \psdots[dotsize=4pt 2](5,1.3) %right of y
  \psdot[dotsize=4pt 2](3.75,1.1) %slight right of y
  \psline(1.02,2.675)(2.5,1.2)(3.98,2.675) %y
  \psline(3.95,3.15)(5,1.3)(2.08,2.575) %right of y
  \psline(3.995,2.97)(3.75,1.1)(1.95,2.65) %slight right of y
  \pscurve(2.5,1.2)(3.9,1.38)(5,1.3) %y - right of y
  \pscurve(2.5,1.2)(3.1,1.2)(3.75,1.1) %y - slight right of y
%below y:
  \pscurve(2.5,1.2)(2.3,0.8)(2.2,0.3)
  \psline(2.5,1.2)(2.5,0.3)
  \pscurve(2.5,1.2)(2.7,0.8)(2.8,0.3)
  \psdots[dotstyle=Bo,dotsize=4pt 2](2.2,0.3)(2.5,0.3)(2.8,0.3)
\end{pspicture}
\end{tabular}
\caption{Case C1/C2, Case C3 with $q=2$, and Case C3 with $q=1$.}
\label{F:C1C2C3}
\end{center}
\end{figure}

\runinhead{Case C3.}
Suppose that
$m=2$ and $s\ge 1$.

% Strategy N2
Since $m=2$ we must have $q\le 2$,
and so there exist two distinct vertices of $X$ (say $x_1$, $x_2$),
so that each full leaf of the star $B_2-X$ is adjacent to
only one of these vertices.
(See the second and third graphs in Figure~\ref{F:C1C2C3}.)
Remove $y$, all partial leaves of $B_2-X$,
and $X-\{x_1,x_2\}$, and
make the full leaves partial,
to obtain $G'$.
Find $U'$ by the induction hypothesis,
and let $U$ be $U'$ plus all partial leaves of $B_2-X$.
Note that both full leaves of $B_2-X$ also lie in $U$.
We check the weight requirement.
\begin{align*}
\frac{w(U)-w(U')}{w(G)-w(G')} &= \frac{sp+2(1-p)}{sp+2(1-p)+1+(k-2)} \quad&&\\
 &\ge \frac{p+2(1-p)}{p+2(1-p)+1+(k-2)} \quad&&\text{minimized when $s=1$}\\
 &= \frac{2-p}{k+1-p} \quad&&\\
 &= r_{k,d}. \quad&&\text{by Fact (i)}
\end{align*}

\runinhead{Case C4.}
Suppose that
$k\ge 3$, $m\ge 2$, and $m+s\le d$. %(See Figure~\ref{F:depth 2 lobe}.)

% Strategy S
Remove the entire lobe $B_2$ to obtain $G'$.
Find $U'$ by the induction hypothesis,
and let $U$ be $U'$ plus all vertices in $B_2-X$.
Then

\begin{align*}
\frac{w(U)-w(U')}{w(G)-w(G')} &= \frac{m+sp+1}{m+sp+k+1} \quad&&\\
 &\ge \frac{3}{k+3}. \quad&&\text{minimized when $m=2$ \& $s=0$}
\end{align*}
The inequality
\[
\frac{3}{k+3} \ge \frac{2d}{kd+d+1}
\]
simplifies to $k\ge 3-3/d$, which holds, since $k\ge 3$.

Note that, while it is possible that $G'$ contains no partial vertices,
we always have $k\ne 2$ in Case C4, and so
we do not need to treat $G'\cong K_{1,1,3}$ separately.
(We will generally not point this out in later cases.)

\runinhead{Case C5.}
Suppose that
$k\ge 3$, $m\ge 3$, $m+s\ge d+1$,
and either $m\ge 4$ or $k\ge 4$.

% Strategy L
Remove the entire lobe $B_2$ to obtain $G'$.
Find $U'$ by the induction hypothesis,
and let $U$ be $U'$ plus all leaves of the star $B_2-X$.
Then

\[
\frac{w(U)-w(U')}{w(G)-w(G')} = \frac{m+sp}{m+sp+k+1}.
\]
The inequality
\[
\frac{(m+sp)}{(m+sp)+k+1} \ge \frac{2d}{kd+d+1}
%% NOTE: Parens around (m+sp) above are to emphasize that this is
%% handled as an atomic quantity when we simplify
\]
simplifies to
\[
m+sp \ge \frac{2(k+1)d}{kd-d+1}.
\]
We consider this inequality when $m\ge 4$,
and then when $k\ge 4$.

Suppose that $m\ge 4$.
It suffices to verify the inequality obtained by replacing
$m+sp$ by $4$ above.
This simplifies to $kd\ge 3d-2$,
which holds, since $k\ge 3$.

Now suppose that $k\ge 4$.
The quantity $m+sp$ is minimized when $m=3$ and $m+s = d+1$,
that is, $s=d-2$.
Thus, we replace $m+sp$ by $3+(d-2)p$ above,
substitute $p=2/(kd-d+1)$,
and simplify to $(k-3)d\ge 1$,
which holds, since $k\ge 4$ and $d\ge 2$.

%\includegraphics{C6-alt.eps}}
\begin{figure}[hbt]
\begin{center}
\begin{tabular}{ccc}
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
\begin{pspicture}(0.7,0.5)(4.3,3.76)
  \psellipse(2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psdot[dotsize=4pt 2](1.7,3.2)\rput(1.8,3.4){$x_1$}
  \psdot[dotsize=4pt 2](3.3,3.2)\rput(3.4,3.4){$x_2$}
  \psdot[dotsize=4pt 2](2.5,2.6)\rput(2.5,2.9){$x_3$}
  \psdot[dotsize=4pt 2](2.5,1.5)\rput(2.2,1.3){$y$}
  \psline(1.7,3.2)(3.3,3.2)(2.5,2.6)(1.7,3.2)(2.5,1.5)(3.3,3.2)
  \psline(2.5,2.6)(2.5,1.5)
  \psdot[dotsize=4pt 2](0.7,1.7) %left of y
  \psdots[dotsize=4pt 2](3.75,1.1)(4.3,1.7)%(4.85,2.3) %right of y
  \pscurve(2.5,1.5)(1.7,1.73)(0.7,1.7) %y - left of y
  \psline(1.7,3.2)(0.7,1.7)(2.5,2.6)
  \pscurve(2.5,1.5)(3.1,1.43)(3.75,1.1) %y - slight right of y
  \psline(3.3,3.2)(3.75,1.1)(2.5,2.6)
  \pscurve(2.5,1.5)(3.3,1.73)(4.3,1.7) %y - med right of y
  \psline(3.3,3.2)(4.3,1.7)(2.5,2.6)
%  \pscurve(2.5,1.5)(3.5,2.05)(4.85,2.3) %y - far right of y
%  \psline(3.3,3.2)(4.85,2.3)(2.5,2.6)
%below y:
  \pscurve(2.5,1.5)(2.3,1.1)(2.2,0.5)
  \psline(2.5,1.5)(2.5,0.5)
  \pscurve(2.5,1.5)(2.7,1.1)(2.8,0.5)
  \psdots[dotstyle=Bo,dotsize=4pt 2](2.2,0.5)(2.5,0.5)(2.8,0.5)
\end{pspicture}
& \qquad\qquad &
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
\begin{pspicture}(0.7,0.5)(4.85,3.76)
  \psellipse(2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psdot[dotsize=4pt 2](1.7,3.2)\rput(1.8,3.4){$x_1$}
  \psdot[dotsize=4pt 2](3.3,3.2)\rput(3.4,3.4){$x_2$}
  \psdot[dotsize=4pt 2](2.5,2.6)\rput(2.5,2.9){$x_3$}
  \psdot[dotsize=4pt 2](2.5,1.5)\rput(2.2,1.3){$y$}
  \psline(1.7,3.2)(3.3,3.2)(2.5,2.6)(1.7,3.2)(2.5,1.5)(3.3,3.2)
  \psline(2.5,2.6)(2.5,1.5)
%  \psdot[dotsize=4pt 2](0.7,1.7) %left of y
  \psdots[dotsize=4pt 2](3.75,1.1)(4.3,1.7)(4.85,2.3) %right of y
%  \pscurve(2.5,1.5)(1.7,1.73)(0.7,1.7) %y - left of y
%  \psline(1.7,3.2)(0.7,1.7)(2.5,2.6)
  \pscurve(2.5,1.5)(3.1,1.43)(3.75,1.1) %y - slight right of y
  \psline(3.3,3.2)(3.75,1.1)(2.5,2.6)
  \pscurve(2.5,1.5)(3.3,1.73)(4.3,1.7) %y - med right of y
  \psline(3.3,3.2)(4.3,1.7)(2.5,2.6)
  \pscurve(2.5,1.5)(3.5,2.05)(4.85,2.3) %y - far right of y
  \psline(3.3,3.2)(4.85,2.3)(2.5,2.6)
%below y:
  \pscurve(2.5,1.5)(2.3,1.1)(2.2,0.5)
  \psline(2.5,1.5)(2.5,0.5)
  \pscurve(2.5,1.5)(2.7,1.1)(2.8,0.5)
  \psdots[dotstyle=Bo,dotsize=4pt 2](2.2,0.5)(2.5,0.5)(2.8,0.5)
\end{pspicture}
\\ \hskip 1pt \\
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
\begin{pspicture}(0.7,1.1)(4.3,3.76)
  \psellipse(2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psdot[dotsize=4pt 2](1.7,3.2)\rput(1.8,3.4){$x_1$}
  \psdot[dotsize=4pt 2](3.3,3.2)\rput(3.4,3.4){$x_2$}
%  \psdot[dotsize=4pt 2](2.5,2.6)\rput(2.5,2.9){$x_3$}
%  \psdot[dotsize=4pt 2](2.5,1.5)\rput(2.1,1.3){$y$}
  \psline(1.7,3.2)(3.3,3.2)%(2.5,2.6)(1.7,3.2)(2.5,1.5)(3.3,3.2)
%  \psline(2.5,2.6)(2.5,1.5)
%  \pscurve(2.5,1.5)(1.7,1.73)(0.7,1.7) %y - left of y
  \psline(1.7,3.2)(0.7,1.7)%(2.5,2.6)
%  \pscurve(2.5,1.5)(3.1,1.43)(3.75,1.1) %y - slight right of y
  \psline(3.3,3.2)(3.75,1.1)%(2.5,2.6)
%  \pscurve(2.5,1.5)(3.3,1.73)(4.3,1.7) %y - med right of y
  \psline(3.3,3.2)(4.3,1.7)%(2.5,2.6)
%  \pscurve(2.5,1.5)(3.5,2.05)(4.85,2.3) %y - far right of y
%  \psline(3.3,3.2)(4.85,2.3)(2.5,2.6)
  \psdot[dotstyle=Bo,dotsize=4pt 2](0.7,1.7) %left of y
  \psdots[dotstyle=Bo,dotsize=4pt 2](3.75,1.1)(4.3,1.7)%(4.85,2.3) %right of y
%below y:
%  \pscurve(2.5,1.5)(2.3,1.1)(2.2,0.5)
%  \psline(2.5,1.5)(2.5,0.5)
%  \pscurve(2.5,1.5)(2.7,1.1)(2.8,0.5)
%  \psdots[dotstyle=Bo,dotsize=4pt 2](2.2,0.5)(2.5,0.5)(2.8,0.5)
\end{pspicture}
& \qquad\qquad &
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
\begin{pspicture}(0.7,1.1)(4.85,3.76)
  \psellipse(2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psdot[dotsize=4pt 2](1.7,3.2)\rput(1.8,3.4){$x_1$}
  \psdot[dotsize=4pt 2](3.3,3.2)\rput(3.4,3.4){$x_2$}
%  \psdot[dotsize=4pt 2](2.5,2.6)\rput(2.5,2.9){$x_3$}
%  \psdot[dotsize=4pt 2](2.5,1.5)\rput(2.1,1.3){$y$}
  \psline(1.7,3.2)(3.3,3.2)%(2.5,2.6)(1.7,3.2)(2.5,1.5)(3.3,3.2)
%  \psline(2.5,2.6)(2.5,1.5)
%  \pscurve(2.5,1.5)(1.7,1.73)(0.7,1.7) %y - left of y
%  \psline(1.7,3.2)(0.7,1.7)(2.5,2.6)
%  \pscurve(2.5,1.5)(3.1,1.43)(3.75,1.1) %y - slight right of y
  \psline(3.3,3.2)(3.75,1.1)%(2.5,2.6)
%  \pscurve(2.5,1.5)(3.3,1.73)(4.3,1.7) %y - med right of y
  \psline(3.3,3.2)(4.3,1.7)%(2.5,2.6)
%  \pscurve(2.5,1.5)(3.5,2.05)(4.85,2.3) %y - far right of y
  \psline(3.3,3.2)(4.85,2.3)%(2.5,2.6)
%  \psdot[dotsize=4pt 2](0.7,1.7) %left of y
  \psdots[dotstyle=Bo,dotsize=4pt 2](3.75,1.1)(4.3,1.7)(4.85,2.3) %right of y
%below y:
%  \pscurve(2.5,1.5)(2.3,1.1)(2.2,0.5)
%  \psline(2.5,1.5)(2.5,0.5)
%  \pscurve(2.5,1.5)(2.7,1.1)(2.8,0.5)
%  \psdots[dotstyle=Bo,dotsize=4pt 2](2.2,0.5)(2.5,0.5)(2.8,0.5)
\end{pspicture}
\end{tabular}
\caption{Case C6.
On the left, $q=2$ (before and after).
On the right, $q=1$ (before and after).}
\label{F:C6}
\end{center}
\end{figure}

\runinhead{Case C6.}
Suppose that
$k=3$, $m=3$, and $q\le 2$.

% Strategy N2   %MJP:rewritten for this specialized context

Since $q\le 2$, there is a vertex in $X$ (say $x_3$)
that is adjacent to every full leaf of $B_2-X$.
(See Figure~\ref{F:C6}.)
Then each full leaf is adjacent to exactly one vertex in $\{x_1,x_2\}$.
Remove $x_3$, $y$, and all partial leaves,
and make all the full leaves partial,
to obtain $G'$.
Find $U'$ by the induction hypothesis,
and let $U$ be $U'$ plus all partial leaves.
Note that all full leaves also lie in $U$.
Thus,
\begin{align*}
\frac{w(U)-w(U')}{w(G)-w(G')} &= \frac{3(1-p)+sp}{3(1-p)+sp+2} \quad&&\\
 &\ge \frac{3-3p}{5-3p}. \quad&&\text{minimized when $s=0$}
\end{align*}
Thus, it suffices to show that
\[
\frac{3-3p}{5-3p} \ge \frac{2d}{kd+d+1}.
\]
Substituting $p=2/(kd-d+1)$ and $k=3$,
this inequality simplifies to
$(2d-3)(2d+1)\ge 0$,
which holds, since $d\ge 2$.

\runinhead{Case C7.}
Suppose that
$k=3$, $m=3$, and $q=3$.

%\includegraphics{C7.eps}}
\begin{figure}[hb]
\begin{center}
\begin{tabular}{ccc}
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
\begin{pspicture}(0.7,0.5)(4.85,3.76)
  \psellipse(2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psdot[dotsize=4pt 2](1.7,3.2)\rput(1.8,3.4){$x_1$}
  \psdot[dotsize=4pt 2](3.3,3.2)\rput(3.4,3.4){$x_2$}
  \psdot[dotsize=4pt 2](2.5,2.6)\rput(2.5,2.9){$x_3$}
  \psdot[dotsize=4pt 2](2.5,1.5)\rput(2.2,1.3){$y$}
  \psline(1.7,3.2)(3.3,3.2)(2.5,2.6)(1.7,3.2)(2.5,1.5)(3.3,3.2)
  \psline(2.5,2.6)(2.5,1.5)
  \psdot[dotsize=4pt 2](0.7,1.7) %left of y
  \psdots[dotsize=4pt 2](3.70,0.9)(4.3,1.7) %right of y
  \pscurve(2.5,1.5)(1.7,1.73)(0.7,1.7) %y - left of y
  \psline(1.7,3.2)(0.7,1.7)(2.5,2.6)
%  \pscurve(2.5,1.5)(3.1,1.43)(3.25,1.1) %y - slight right of y
  \psline(3.70,0.9)(2.5,1.5)
  \pscurve(3.70,0.9)(2.6,1.8)(1.7,3.2)
%  \psline(3.70,0.9)(1.7,3.2)
%  \pscurve(3.3,3.2)(3.05,2)(3.1,0.9)
  \pscurve(3.3,3.2)(3.05,1.75)(3.70,0.9)
%  \pscurve(3.3,3.2)(3.3,1.4)(3.70,0.9)
  \pscurve(2.5,1.5)(3.3,1.73)(4.3,1.7) %y - med right of y
  \psline(3.3,3.2)(4.3,1.7)(2.5,2.6)
%  \pscurve(2.5,1.5)(3.5,2.05)(4.85,2.3) %y - far right of y
%  \psline(3.3,3.2)(4.85,2.3)(2.5,2.6)
%below y:
  \pscurve(2.5,1.5)(2.3,1.1)(2.2,0.5)
  \psline(2.5,1.5)(2.5,0.5)
  \pscurve(2.5,1.5)(2.7,1.1)(2.8,0.5)
  \psdots[dotstyle=Bo,dotsize=4pt 2](2.2,0.5)(2.5,0.5)(2.8,0.5)
\end{pspicture}
& \qquad\qquad &
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
\begin{pspicture}(0.7,0.5)(4.85,3.76)
  \psellipse(2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psdot[dotsize=4pt 2](1.7,3.2)\rput(1.8,3.4){$x_1$}
  \psdot[dotsize=4pt 2](3.3,3.2)\rput(3.4,3.4){$x_2$}
  \psdot[dotsize=4pt 2](2.5,2.6)\rput(2.5,2.9){$x_3$}
  \psdot[dotsize=4pt 2](2.5,1.5)\rput(2.2,1.3){$y$}
  \psline(1.7,3.2)(3.3,3.2)(2.5,2.6)(1.7,3.2)(2.5,1.5)(3.3,3.2)
  \psline(2.5,2.6)(2.5,1.5)
%  \pscurve(2.5,1.5)(1.7,1.73)(0.7,1.7) %y - left of y
  \psline(1.7,3.2)(0.7,1.7)
%  \pscurve(2.5,1.5)(3.1,1.43)(3.75,1.1) %y - slight right of y
  \psline(3.55,1.1)(2.5,2.6)
%  \pscurve(2.5,1.5)(3.3,1.73)(4.3,1.7) %y - med right of y
  \psline(3.3,3.2)(4.3,1.7)%(2.5,2.6)
%  \pscurve(2.5,1.5)(3.5,2.05)(4.85,2.3) %y - far right of y
%  \psline(3.3,3.2)(4.85,2.3)(2.5,2.6)
  \psdot[dotstyle=Bo,dotsize=4pt 2](0.7,1.7) %left of y
  \psdots[dotstyle=Bo,dotsize=4pt 2](3.55,1.1)(4.3,1.7) %right of y
  \rput(0.5,1.5){$c_1$}
  \rput(4.1,1.5){$c_2$}
  \rput(3.35,0.9){$c_3$}
%below y:
%  \pscurve(2.5,1.5)(2.3,1.1)(2.2,0.5)
%  \psline(2.5,1.5)(2.5,0.5)
%  \pscurve(2.5,1.5)(2.7,1.1)(2.8,0.5)
%  \psdots[dotstyle=Bo,dotsize=4pt 2](2.2,0.5)(2.5,0.5)(2.8,0.5)
\end{pspicture}
\end{tabular}
\caption{Case C7 (before and after).}
\label{F:C7}
\end{center}
\end{figure}

% Strategy N3X.
Remove all full and partial leaves of the star $B_2-X$,
and add new partial vertices $c_1$, $c_2$, $c_3$, so that
$c_i$ is adjacent only to $x_i$, for $i=1,2,3$.
Let $G'$ be the resulting graph.
(See Figure~\ref{F:C7}.)
Find $U'$ by the induction hypothesis.

We may assume that $y\in U'$.
If it is not,
then we can add $y$ to $U'$,
removing one element of $X$ from $U'$ if $U'$ meets $X$,
to obtain a new $U'$ that contains $y$.
Note that now $U'$ contains at most $1$ vertex of $X$.

Let $U$ be $U'-\{c_1,c_2,c_3,y\}$ plus all leaves of $B_2-X$.
If $x_i\in U'$ then its degree is the same in
$G[U]$ as in $G[U']$;
hence, $G[U]$ is a forest of maximum degree at most $d$.

For the weight requirement, we have
\begin{align*}
\frac{w(U)-w(U')}{w(G)-w(G')} &= \frac{3+sp-3p-1}{3+sp-3p} \quad&&\\
 &\ge \frac{2-3p}{3-3p}. \quad&&\text{minimized when $s=0$}
\end{align*}
Thus, it suffices to show that
\[
\frac{2-3p}{3-3p} \ge \frac{2d}{kd+d+1}.
\]
Substituting $p=2/(kd-d+1)$ and $k=3$,
this inequality simplifies to
$(2d+1)(d-2)\ge 0$,
which holds, since $d\ge 2$.

\runinhead{Case C8.}
Suppose that
$k=2$, $m=2$, $s=0$, and $d=2$.

% Strategy S
Remove the entire lobe $B_2$ to obtain $G'$.
If $G'\cong K_{1,1,3}$,
then let $U'$ be a $3$-vertex independent set in $G'$;
otherwise, find $U'$ by the induction hypothesis.
Let $U$ be $U'$ plus all vertices in $B_2-X$.
Then
\begin{align*}
\frac{w(U)-w(U')}{w(G)-w(G')} &= \frac{3}{5} \quad&&\\
 &> \frac{4}{7} = r_{k,d}, \quad&&\text{$k=2$ \& $d=2$}
\end{align*}
and so the strict weight inequality holds.

\runinhead{Case C9.}
Suppose that
$k=2$, $m=2$, $s=0$, $q=1$, and $d\ge 3$.
%(See Figure~\ref{F:C9}

% Strategy N1S
Since $q=1$,
there is one vertex in $X$ (say $x_1$)
that is not adjacent to either leaf of the star $B_2-X$.
(See the first graph in Figure~\ref{F:C9C12C13}.)
Remove $x_2$ and the two leaves of $B_2-X$, and make $y$ partial,
to obtain $G'$.
Find $U'$ by the induction hypothesis,
and let $U$ be $U'$ plus all leaves of $B_2-X$.
Note that $y\in U$.
Since $d\ge3$, the degree requirement is satisfied.
We have

\begin{align*}
\frac{w(U)-w(U')}{w(G)-w(G')} &= \frac{2+(1-p)}{3+(1-p)} \quad&&\\
 &> \frac{2-p}{3-p} \quad&&\\
% &= \frac{2-p}{k+1-p} \quad&&\text{$k=2$}\\
 &= r_{k,d}. \quad&&\text{by Fact (i), since $k=2$}
\end{align*}

\runinhead{Case C10.}
Suppose that
$k=2$, $m=2$, $s=0$, $q=2$, and $d\ge 3$.  (See Figure~\ref{F:C10}.)

To deal with this case
we will use techniques involving lobes of depth $3$.
We discuss these later, in Subsection~\ref{Ss:depth3}.

\runinhead{Case C11.}
Suppose that
$k=2$, $m\ge 3$, and $d\ge 3$.

% Strategy N2
Remove $y$ and all partial leaves of the star $B_2-X$,
and make all the full leaves partial,
to obtain $G'$.
Find $U'$ by the induction hypothesis,
and let $U$ be $U'$ plus all partial leaves of $B_2-X$.
Note that all full leaves of $B_2-X$ also lie in $U$.
Thus,
\begin{align*}
\frac{w(U)-w(U')}{w(G)-w(G')} &= \frac{sp+m(1-p)}{sp+m(1-p)+1} \quad&&\\
 &\ge \frac{3-3p}{4-3p}. \quad&&\text{minimized when $m=3$ \& $s=0$}
\end{align*}
Thus, it suffices to show that
\[
\frac{3-3p}{4-3p} \ge \frac{2d}{kd+d+1}.
\]
Substituting $p=2/(kd-d+1)$ and $k=2$,
this inequality simplifies to
$(d-3)(d+1)\ge 0$,
which holds, since $d\ge 3$.

\runinhead{Case C12.}
Suppose that
$k=2$, $m=3$, $q=1$, and $d=2$.

%\includegraphics{C12C13-alt.eps}}
\begin{figure}[thb]
\begin{center}
\begin{tabular}{ccccccc}
\begin{pspicture}(1.1,0.3)(3.7,3.08)
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
  \psellipse(2.5,2.5)(1.15,0.58)
  \rput(1.1,2.7){$X$}
  \psdot[dotsize=4pt 2](2,2.5)\rput(2.1,2.7){$x_1$}
  \psdot[dotsize=4pt 2](3,2.5)\rput(3.1,2.7){$x_2$}
  \psdot[dotsize=4pt 2](2.5,1.2)\rput(2.2,1.0){$y$}
  \psline(2,2.5)(3,2.5)(2.5,1.2)(2,2.5)
%  \psdot[dotsize=4pt 2](1.5,1.7) %left of y
%  \rput(1.1,1.56){$y'$}
%  \psline(2,2.5)(1.5,1.7)(2.5,1.2)
%  \psdots[dotsize=4pt 2](0.6,2)(1,1.2)%next level left of y
%  \rput(0.3,1.9){$z_1$}
%  \rput(0.7,1.1){$z_2$}
%  \psline(2,2.5)(0.6,2)(1.5,1.7)(1,1.2)(2.5,1.2)
  \psdots[dotsize=4pt 2](3.3,1.2)(3.5,1.6) %right of y
  \psline(2.5,1.2)(3.3,1.2)(3,2.5)
  \psline(2.5,1.2)(3.5,1.6)(3,2.5)
%below y:
\end{pspicture}
& \qquad\qquad &
\begin{pspicture}(1.1,0.3)(3.7,3.08)
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
  \psellipse(2.5,2.5)(1.15,0.58)
  \rput(1.1,2.7){$X$}
  \psdot[dotsize=4pt 2](2,2.5)\rput(2.1,2.7){$x_1$}
  \psdot[dotsize=4pt 2](3,2.5)\rput(3.1,2.7){$x_2$}
  \psdot[dotsize=4pt 2](2.5,1.2)\rput(2.2,1.0){$y$}
  \psline(2,2.5)(3,2.5)(2.5,1.2)(2,2.5)
%  \psdot[dotsize=4pt 2](1.5,1.7) %left of y
%  \rput(1.1,1.56){$y'$}
%  \psline(2,2.5)(1.5,1.7)(2.5,1.2)
%  \psdots[dotsize=4pt 2](0.6,2)(1,1.2)%next level left of y
%  \rput(0.3,1.9){$z_1$}
%  \rput(0.7,1.1){$z_2$}
%  \psline(2,2.5)(0.6,2)(1.5,1.7)(1,1.2)(2.5,1.2)
  \psdots[dotsize=4pt 2](3.3,1.2)(3.5,1.6)(3.7,2) %right of y
  \psline(2.5,1.2)(3.3,1.2)(3,2.5)
  \psline(2.5,1.2)(3.5,1.6)(3,2.5)
  \psline(2.5,1.2)(3.7,2)(3,2.5)
%below y:
  \pscurve(2.5,1.2)(2.3,0.8)(2.2,0.3)
  \psline(2.5,1.2)(2.5,0.3)
  \pscurve(2.5,1.2)(2.7,0.8)(2.8,0.3)
  \psdots[dotstyle=Bo,dotsize=4pt 2](2.2,0.3)(2.5,0.3)(2.8,0.3)
\end{pspicture}
& \qquad\qquad\qquad &
\begin{pspicture}(1.1,0.3)(3.7,3.08)
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
  \psellipse(2.5,2.5)(1.15,0.58)
  \rput(1.1,2.7){$X$}
  \psdot[dotsize=4pt 2](2,2.5)\rput(2.1,2.7){$x_1$}
  \psdot[dotsize=4pt 2](3,2.5)\rput(3.1,2.7){$x_2$}
  \psdot[dotsize=4pt 2](2.5,1.2)\rput(2.2,1.0){$y$}
  \psline(2,2.5)(3,2.5)(2.5,1.2)(2,2.5)
  \psdots[dotsize=4pt 2](1.5,1.7)(1.7,1.2) %left of y
  \rput(1.2,1.56){$z_2$}
  \rput(1.4,1.1){$z_1$}
  \psline(2,2.5)(1.5,1.7)(2.5,1.2)(1.7,1.2)(2,2.5)
%  \psdots[dotsize=4pt 2](0.6,2)(1,1.2)%next level left of y
%  \rput(0.3,1.9){$z_1$}
%  \rput(0.7,1.1){$z_2$}
%  \psline(2,2.5)(0.6,2)(1.5,1.7)(1,1.2)(2.5,1.2)
  \psdot[dotsize=4pt 2](3.5,1.6)%right of y
  \rput(3.8,1.5){$z_3$}
  \psline(2.5,1.2)(3.5,1.6)(3,2.5)
%  \psline(1.02,2.675)(2.5,1.2)(3.98,2.675) %y
%  \psline(1.05,3.15)(0,1.3)(2.92,2.575) %left of y
%  \psline(3.95,3.15)(5,1.3)(2.08,2.575) %right of y
%  \psline(3.995,2.97)(3.75,1.1)(1.95,2.65) %slight right of y
%  \pscurve(2.5,1.2)(1.1,1.38)(0,1.3) %y - left of y
%  \pscurve(2.5,1.2)(3.9,1.38)(5,1.3) %y - right of y
%  \pscurve(2.5,1.2)(3.1,1.2)(3.75,1.1) %y - slight right of y
%below y:
  \pscurve(2.5,1.2)(2.3,0.8)(2.2,0.3)
  \psline(2.5,1.2)(2.5,0.3)
  \pscurve(2.5,1.2)(2.7,0.8)(2.8,0.3)
  \psdots[dotstyle=Bo,dotsize=4pt 2](2.2,0.3)(2.5,0.3)(2.8,0.3)
\end{pspicture}
& \, &
\begin{pspicture}(1.1,0.3)(3.7,3.08)
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
  \psellipse(2.5,2.5)(1.15,0.58)
  \rput(1.1,2.7){$X$}
  \psdot[dotsize=4pt 2](2,2.5)\rput(2.1,2.7){$x_1$}
  \psdot[dotsize=4pt 2](3,2.5)\rput(3.1,2.7){$x_2$}
  \psdot[dotsize=4pt 2](2.5,1.2)\rput(2.2,1.0){$y$}
  \psline(2,2.5)(3,2.5)(2.5,1.2)(2,2.5)
  \rput(1.2,1.56){$c_1$}
  \psline(2,2.5)(1.5,1.7)
  \psdot[dotstyle=Bo,dotsize=4pt 2](1.5,1.7) %left of y
%below y:
%  \pscurve(2.5,1.2)(2.3,0.8)(2.2,0.3)
%  \psline(2.5,1.2)(2.5,0.3)
%  \pscurve(2.5,1.2)(2.7,0.8)(2.8,0.3)
%  \psdots[dotstyle=Bo,dotsize=4pt 2](2.2,0.3)(2.5,0.3)(2.8,0.3)
\end{pspicture}
\end{tabular}
\caption{Case C9, Case C12, and Case C13 (before and after).}
\label{F:C9C12C13}
\end{center}
\end{figure}

% Strategy N1L
Since $q=1$,
there is one vertex in $X$ (say $x_1$)
that is not adjacent to any full leaf of the star $B_2-X$.
(See the second graph in Figure~\ref{F:C9C12C13}.)
Remove all vertices of $B_2$,
except for $x_1$,
to obtain $G'$.
If $G'\cong K_{1,1,3}$,
then let $U'$ be a $3$-vertex independent set in $G'$;
otherwise, find $U'$ by the induction hypothesis.
Let $U$ be $U'$ plus all leaves of $B_2-X$.
Then
\begin{align*}
\frac{w(U)-w(U')}{w(G)-w(G')} &= \frac{3+sp}{5+sp} \quad&&\\
 &\ge \frac{3}{5} \quad&&\text{minimized when $s=0$}\\
 &> \frac{4}{7} = r_{k,d}, \quad&&\text{$k=2$ \& $d=2$}
\end{align*}
and so the strict weight inequality holds.

\runinhead{Case C13.}
Suppose that
$k=2$, $m=3$, $q=2$, and $d=2$.

% Strategy N2X.
Let $z_1$, $z_2$, $z_3$ be the full leaves of the star $B_2-X$.
Without loss of generality,
we may assume that $N(z_1) = N(z_2) = \{x_1,y\}$,
while $N(z_3) = \{x_2,y\}$.
Remove all full and partial leaves of $B_2-X$,
and add a partial vertex $c_1$ adjacent to $x_1$.
Let $G'$ be the resulting graph.
(See the last two graphs in Figure~\ref{F:C9C12C13}.)
Find $U'$ by the induction hypothesis.

We may assume that $y\in U'$.
If it is not,
then we can add $y$ to $U'$,
removing one element of $X$ from $U'$ if $U'$ meets $X$,
to obtain a new $U'$ that contains $y$.
Note that now $U'$ contains at most $1$ vertex of $X$.

Let $U$ be $U'-\{c_1,y\}$ plus all leaves of the star $B_2-X$.
If $x_i\in U'$ then its degree is the same in
$G[U]$ as in $G[U']$;
hence, $G[U]$ is a forest of maximum degree at most $d$.
Then
\begin{align*}
\frac{w(U)-w(U')}{w(G)-w(G')} &= \frac{3+sp-p-1}{3+sp-p} \quad&&\\
 &\ge \frac{2-p}{3-p} \quad&&\text{minimized when $s=0$}\\
% &= \frac{2-p}{k+1-p} \quad&&\text{$k=2$}\\
 &= r_{k,d}. \quad&&\text{by Fact (i), since $k=2$}
\end{align*}

\runinhead{Case C14.}
Suppose that
$k=2$, $m\ge 4$, and $d=2$.

% Strategy L.
Remove the entire lobe $B_2$, to obtain $G'$.
First, suppose that $G'\not\cong K_{1,1,3}$.
In this case,
find $U'$ by the induction hypothesis,
and let $U$ be $U'$ plus all leaves of $B_2-X$.
Then
\begin{align*}
\frac{w(U)-w(U')}{w(G)-w(G')} &= \frac{m+sp}{m+sp+3} \quad&&\\
 &\ge \frac{m}{m+3}. \quad&&\text{minimized when $s=0$}
\end{align*}
Since $m\ge 4$, this fraction is at least $4/7=r_{k,d}$.

Now suppose that $G'\cong K_{1,1,3}$.
Applying Remark~\ref{r:K113},
we let $U'$ be a $3$-vertex set inducing a forest in $G'$
that contains no vertices adjacent to $X$ in $G$.

If $m\ge 5$, then let $U$ be $U'$ plus all leaves of $B_2-X$.
Then $w(U) = 3+m+sp$, while $w(G) = 8+m+sp$.
Substituting these, along with $k = d = 2$, into
\[
w(U) \ge \frac{2d\cdot w(G) + 2}{kd+d+1}
\]
and simplifying, we obtain
$m+sp\ge 13/3$,
which holds, since $m\ge 5$.

Now suppose that $m=4$.
Since $k=2$ and $m=4$, some element of $X$ (say $x_1)$ is adjacent to
at most $2$ full leaves of $B_2-X$.
Let $U$ be $U'$ plus $x_1$ and all leaves of $B_2-X$.
Then $w(U) = 8+sp$, while $w(G) = 12+sp$.
Substituting and simplifying, as above,
we obtain $sp\ge -2$, which holds.

Thus, $U$ satisfies the weight requirement.

\runinhead{Cases Covered by the Depth 2 Techniques---}When
$k\ge 3$ or $d=2$, we have handled every lobe of depth $2$,
and so our proof of these cases is complete.

When $k=2$ and $d\ge 3$,
we have handled every lobe of depth $2$
except for that with
$m=2$, $s=0$, and $q=2$
(Case C10; see Figure~\ref{F:C10}).
Next we consider graphs in which every depth 2 lobe is of this type.
%We will deal with graphs containing this lobe
%using techniques involving lobes of depth $3$.

%\includegraphics{C10.eps}}
\begin{figure}[ht]
\begin{center}
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
\begin{pspicture}(1.1,1.2)(3.9,3.08)
  \psellipse(2.5,2.5)(1.15,0.58)
  \rput(1.1,2.7){$X$}
  \psdot[dotsize=4pt 2](2,2.5)\rput(2.1,2.7){$x_1$}
  \psdot[dotsize=4pt 2](3,2.5)\rput(3.1,2.7){$x_2$}
  \psdot[dotsize=4pt 2](2.5,1.2)\rput(2.2,1.0){$y$}
  \psline(2,2.5)(3,2.5)(2.5,1.2)(2,2.5)
  \psdot[dotsize=4pt 2](1.5,1.7) %left of y
  \psline(2,2.5)(1.5,1.7)(2.5,1.2)
  \psdots[dotsize=4pt 2](3.5,1.7) %right of y
  \psline(2.5,1.2)(3.5,1.7)(3,2.5)
\end{pspicture}
\caption{A depth 2 lobe of type C10.}
\label{F:C10}
\end{center}
\end{figure}


\subsection{Depth 3 Techniques} \label{Ss:depth3}

We have handled all depth 2 cases except for C10.
Henceforth, we assume
that \emph{every} lobe of depth $2$ in $G$ is in Case C10,
that is, that $k=2$, $d\ge 3$,
and each depth $2$ lobe contains
no partial vertices ($s = 0$) and
two simplicial vertices ($m=2$)
having distinct neighborhoods ($q = 2$).
(See Figure~\ref{F:C10}.)
%Note that, since $d\ge 3$,
%we no longer need special cases to handle $K_{1,1,3}$.

\runinhead{Base Case 4---}Suppose that $G$ has no lobe of depth $3$ or more.

We claim that $G$ must be isomorphic to the graph with vertex set
$\{a_1, a_2, a_3, b_1, b_2, b_3\}$,
in which the $a_i$ vertices form a triangle,
the $b_i$ vertices form an independent set,
and $a_i$ is adjacent to $b_j$ if and only if $i\ne j$.
(This graph is known as the \localdefterm{Haj\'os graph};
it is pictured in Figure~\ref{F:Hajos}.)

%\includegraphics{Hajos.eps}}
\begin{figure}[ht]
\begin{center}
\pslinewidth 0.5pt
\begin{pspicture}(1.1,1.5)(3.8,3.5)
  \psdot[dotsize=4pt 2](2,2.5)\rput(1.6,2.5){$a_1$}
  \psdot[dotsize=4pt 2](3,2.5)\rput(3.4,2.5){$a_2$}
  \psdot[dotsize=4pt 2](2.5,1.7)\rput(2.85,1.45){$a_3$}
  \psline(2,2.5)(3,2.5)(2.5,1.7)(2,2.5)
  \psdot[dotsize=4pt 2](1.5,1.7) %left of y
  \rput(1.2,1.5){$b_2$}
  \psline(2,2.5)(1.5,1.7)(2.5,1.7)
  \psdots[dotsize=4pt 2](3.5,1.7) %right of y
  \rput(3.85,1.5){$b_1$}
  \psline(2.5,1.7)(3.5,1.7)(3,2.5)
  \psdot[dotsize=4pt 2](2.5,3.3)\rput(2.85,3.3){$b_3$}
  \psline(3,2.5)(2.5,3.3)(2,2.5)
\end{pspicture}
\caption{Base Case 4, the Haj\'os graph.}
\label{F:Hajos}
\end{center}
\end{figure}

To see this, note that $G$ has a depth $2$ lobe $B$,
which must be in Case C10.
Let $X=\{x_1,x_2\}$ be the clique of attachment of $B$,
and let $y$ be the common neighbor of $x_1$, $x_2$ in $B$.
Since $B$ is not all of $G-P$,
there is another $X$-lobe $B'$.
If $B'$ has depth $2$ or more,
then there is an $\{x_1,y\}$-lobe of depth $3$ or more,
contradicting our assumption.
Thus, $B'$ has depth $1$.
If there is a third $X$-lobe, or if $x_2$ has any partial neighbors,
then we have an $\{x_1,y\}$-lobe of depth $2$ that is not in Case C10,
another contradiction.
Similarly, $x_1$ has no partial neighbors.
We conclude that $G$ is the union of $B$ (depth $2$, Case C10)
and $B'$ (depth 1),
and that $P=\varnothing$.
Hence, $G$ is the Haj\'os graph,
with $\{a_1,a_2,a_3\} = \{x_1,x_2,y\}$.

To deal with this case,
let $U=V(G)-\{a_1,a_2\}$.
Then $w(U) = 4$, while $w(G) = 6$.
Thus,
\[
w(U) = \frac{12d+4}{3d+1}
 > \frac{12d+2}{3d+1}
 = \frac{2d\cdot w(G)+2}{kd+d+1},
\]
and so the weight requirement is satisfied.

\medskip

Henceforth, we assume that $G$ has a lobe of depth $3$ or more.

\runinhead{A Lobe of Depth 3---}A lobe of depth more than $3$
must contain a lobe of depth $3$.
Thus, $G$ has a lobe $B_3$ of depth $3$.
Let $X=\{x_1,x_2\}$ be the clique of attachment of $B_3$.
Let $y$ be the common neighbor in $B_3$ of $x_1$, $x_2$.
Let $t$ be the number of partial vertices adjacent to $y$;
there can be no other partial vertices in $B_3$.

\runinhead{Reduction D---}Suppose that $B_3$
contains two or more lobes of depth at most $2$,
at least one of which has depth exactly $2$,
having the same clique of attachment $X'$.
%% NOTE: We could do Reduction D earlier,
%% but we must be careful to ensure that removal of the lobes
%% leaves at least 1 vertex;
%% otherwise we cannot apply the induction hypothesis.
%% Being inside B_3 ensures this.
%% Also, we only *use* Reduction D to reduce the number of depth 3 cases,
%% and so there is no reason to move it earlier.

Remove the above $X'$-lobes, to obtain $G'$.
This $G'$ will have at least $1$ full vertex,
since the two $X'$-lobes are contained in $B_3$
and, being a lobe, $B_3$ cannot contain $G-P$.
Thus, we can find $U'$ by the induction hypothesis,
and let $U$ be $U'$ plus all vertices of the removed lobes,
except for those in $X'$.
Then the degree requirement is satisfied.
Further, the fraction
\[
\frac{w(U)-w(U')}{w(G)-w(G')}
\]
is $6/8$ if both removed lobes have depth $2$,
and $4/6$ otherwise;
in either case,
it is at least $r_{k,d}$
(since, when $k=2$, we have $r_{k,d}=2d/(3d+1)<2/3$),
and so the weight requirement is also satisfied.

\medskip

Henceforth, we assume that, given a depth $2$ lobe contained in $B_3$,
there is no other lobe of depth at most $2$ having the same
clique of attachment.

\runinhead{Cases Involving Depth 3 Lobes---}Having found
a lobe $B_3$ of depth $3$,
we handle it based on the depth $1$ and depth $2$ lobes that it contains.

By Reduction D, no two depth $2$ lobes in $B_3$
can have the same clique of attachment.
Thus, $B_3$ must contain either $1$ or $2$ lobes of depth $2$;
if the latter, then one is attached at $\{x_1, y\}$,
and the other is attached at $\{x_2, y\}$.
Further, if a depth $2$ lobe is attached at a $2$-clique,
then no depth $1$ lobe is attached at this same clique.

We split this portion of the proof into 3 cases, listed below.
We observe that these cases cover all the possibilities.
%
\renewcommand{\labelenumi}{(E\arabic{enumi})} % Labels (E1), (E2), etc.
\begin{enumerate}
\item $B_3$ contains two lobes of depth $2$.
\item $B_3$ contains exactly one lobe of depth $2$,
and no full simplicial vertices other than those in the lobe of depth $2$.
\item $B_3$ contains exactly one lobe of depth $2$,
and at least one full simplicial vertex
other than those in the lobe of depth $2$.
\end{enumerate}

\runinhead{Handling the Depth 3 Cases---}We discuss
how to handle each of the above cases,
in the order listed.

\runinhead{Case E1.}
Suppose that $B_3$
contains two lobes of depth $2$.

Then $B_3$ has exactly $9$ full vertices.
By Reduction D, one of the depth $2$ lobes must be attached at $\{x_1,y\}$,
and the other at $\{x_2,y\}$,
(See the first graph in Figure~\ref{F:E1E2}.)

Delete $B_3$ to obtain $G'$.
Find $U'$ by the induction hypothesis,
and let $U$ be $U'$ plus all vertices of $B_3$
except for $x_1$, $x_2$, and $y$.
Recall that $t$ is the number of partial vertices adjacent to $y$.
Thus,
\[
\frac{w(U)-w(U')}{w(G)-w(G')} = \frac{6+tp}{9+tp}
 \ge \frac{6}{9} > r_{k,d},
\]
and so the weight requirement is satisfied.

\medskip

In the remaining cases (E2 and E3),
$B_3$ contains exactly one lobe of depth $2$.
We may assume, without loss of generality,
that its clique of attachment is $\{x_1,y\}$.
Label its full simplicials as $z_1$, $z_2$,
and its remaining vertex as $y'$,
so that $N(z_1)=\{x_1,y'\}$,
$N(z_2)=\{y',y\}$,
and $N(y')=\{x_1,y,z_1,z_2\}$.
(See the second graph in Figure~\ref{F:E1E2} and
the first graph in Figure~\ref{F:E3}.)

%\includegraphics{E1E2.eps}}
\begin{figure}[ht]
\begin{center}
\begin{tabular}{ccccc}
\begin{pspicture}(0.6,0.3)(4.4,3.08)
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
  \psellipse(2.5,2.5)(1.15,0.58)
  \rput(1.1,2.7){$X$}
  \psdot[dotsize=4pt 2](2,2.5)\rput(2.1,2.7){$x_1$}
  \psdot[dotsize=4pt 2](3,2.5)\rput(3.1,2.7){$x_2$}
  \psdot[dotsize=4pt 2](2.5,1.2)\rput(2.2,1.0){$y$}
  \psline(2,2.5)(3,2.5)(2.5,1.2)(2,2.5)
  \psdot[dotsize=4pt 2](1.5,1.7) %left of y
%  \rput(1.1,1.56){$y'$}
  \psline(2,2.5)(1.5,1.7)(2.5,1.2)
  \psdots[dotsize=4pt 2](0.6,2)(1,1.2)%next level left of y
  \psline(2,2.5)(0.6,2)(1.5,1.7)(1,1.2)(2.5,1.2)
%  \rput(0.3,1.9){$z_1$}
%  \rput(0.7,1.1){$z_2$}
  \psdot[dotsize=4pt 2](3.5,1.7) %right of y
%  \rput(1.1,1.56){$y'$}
  \psline(3,2.5)(3.5,1.7)(2.5,1.2)
  \psdots[dotsize=4pt 2](4.4,2)(4,1.2)%next level right of y
  \psline(3,2.5)(4.4,2)(3.5,1.7)(4,1.2)(2.5,1.2)
%below y:
  \pscurve(2.5,1.2)(2.3,0.8)(2.2,0.3)
  \psline(2.5,1.2)(2.5,0.3)
  \pscurve(2.5,1.2)(2.7,0.8)(2.8,0.3)
  \psdots[dotstyle=Bo,dotsize=4pt 2](2.2,0.3)(2.5,0.3)(2.8,0.3)
\end{pspicture}
& \qquad\qquad\qquad &
\begin{pspicture}(0.6,0.3)(3.65,3.08)
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
  \psellipse(2.5,2.5)(1.15,0.58)
  \rput(1.1,2.7){$X$}
  \psdot[dotsize=4pt 2](2,2.5)\rput(2.1,2.7){$x_1$}
  \psdot[dotsize=4pt 2](3,2.5)\rput(3.1,2.7){$x_2$}
  \psdot[dotsize=4pt 2](2.5,1.2)\rput(2.2,1.0){$y$}
  \psline(2,2.5)(3,2.5)(2.5,1.2)(2,2.5)
  \psdot[dotsize=4pt 2](1.5,1.7) %left of y
  \rput(1.8,1.8){$y'$}
  \psline(2,2.5)(1.5,1.7)(2.5,1.2)
  \psdots[dotsize=4pt 2](0.6,2)(1,1.2)%next level left of y
  \rput(0.3,1.9){$z_1$}
  \rput(0.7,1.1){$z_2$}
  \psline(2,2.5)(0.6,2)(1.5,1.7)(1,1.2)(2.5,1.2)
%  \psdots[dotsize=4pt 2](3.3,1.2)(3.5,1.6)(3.7,2) %right of y
%  \psline(2.5,1.2)(3.3,1.2)(3,2.5)
%  \psline(2.5,1.2)(3.5,1.6)(3,2.5)
%  \psline(2.5,1.2)(3.7,2)(3,2.5)
%  \psline(1.02,2.675)(2.5,1.2)(3.98,2.675) %y
%  \psline(1.05,3.15)(0,1.3)(2.92,2.575) %left of y
%  \psline(3.95,3.15)(5,1.3)(2.08,2.575) %right of y
%  \psline(3.995,2.97)(3.75,1.1)(1.95,2.65) %slight right of y
%  \pscurve(2.5,1.2)(1.1,1.38)(0,1.3) %y - left of y
%  \pscurve(2.5,1.2)(3.9,1.38)(5,1.3) %y - right of y
%  \pscurve(2.5,1.2)(3.1,1.2)(3.75,1.1) %y - slight right of y
%below y:
  \pscurve(2.5,1.2)(2.3,0.8)(2.2,0.3)
  \psline(2.5,1.2)(2.5,0.3)
  \pscurve(2.5,1.2)(2.7,0.8)(2.8,0.3)
  \psdots[dotstyle=Bo,dotsize=4pt 2](2.2,0.3)(2.5,0.3)(2.8,0.3)
\end{pspicture}
& \, &
\begin{pspicture}(0.6,0.3)(3.65,3.08)
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
  \psellipse(2.5,2.5)(1.15,0.58)
  \rput(1.1,2.7){$X$}
  \psdot[dotsize=4pt 2](2,2.5)\rput(2.1,2.7){$x_1$}
  \psdot[dotsize=4pt 2](3,2.5)\rput(3.1,2.7){$x_2$}
  \psdot[dotsize=4pt 2](2.5,1.2)\rput(2.2,1.0){$y$}
  \psline(2,2.5)(3,2.5)(2.5,1.2)(2,2.5)
%  \psdot[dotsize=4pt 2](1.5,1.7) %left of y
%  \rput(1.1,1.56){$y'$}
%  \psline(2,2.5)(1.5,1.7)(2.5,1.2)
  \psline(2,2.5)(0.6,2)%(1.5,1.7)(1,1.2)(2.5,1.2)
  \psdots[dotstyle=Bo,dotsize=4pt 2](0.6,2)%(1,1.2)%next level left of y
  \rput(0.3,1.9){$z_1$}
%  \rput(0.7,1.1){$z_2$}
%  \psdots[dotsize=4pt 2](3.3,1.2)(3.5,1.6)(3.7,2) %right of y
%  \psline(2.5,1.2)(3.3,1.2)(3,2.5)
%  \psline(2.5,1.2)(3.5,1.6)(3,2.5)
%  \psline(2.5,1.2)(3.7,2)(3,2.5)
\end{pspicture}
\end{tabular}
\caption{Case E1 and Case E2 (before and, for Subcase E2a, after).}
\label{F:E1E2}
\end{center}
\end{figure}

\runinhead{Case E2.}
Suppose that $B_3$ contains exactly one lobe of depth $2$,
and no full simplicial vertices other than those in the lobe of depth $2$.

Then $B_3$ has exactly $6$ full vertices.
(See the second graph in Figure~\ref{F:E1E2}.)
By Reduction A, $t\le d-1$.
We have two subcases:
Subcase E2a, in which $t\le d-2$,
and Subcase E2b, in which $t=d-1$.

\runinhead{Subcase E2a.}
Suppose that $t\le d-2$.

Delete the $t$ partial vertices, $z_2$, and $y'$,
and make $z_1$ partial.
Let $G'$ be the resulting graph.
(See the last graph in Figure~\ref{F:E1E2}.)
Find $U'$ by the induction hypothesis,
and let $U$ be $U'$ plus the $t$ partial vertices and $z_2$.
Note that $z_1\in U$.
If $y\in U'$, then the degree of $y$ in $G'[U']$ is at most one,
and so the degree of $y$ in $G[U]$ is at most $t+2\le d$.
It follows that $G[U]$ is a forest that satisfies the degree requirement;
we verify the weight requirement.
\begin{align*}
\frac{w(U)-w(U')}{w(G)-w(G')} &= \frac{1+tp+(1-p)}{2+tp+(1-p)} \quad&&\\
 &\ge \frac{2-p}{3-p} \quad&&\text{minimized when $t=0$}\\
% &= \frac{2d}{3d+1} \quad&&\text{$k=2$}\\
 &= r_{k,d}. \quad&&\text{by Fact (i), since $k=2$}
\end{align*}

\runinhead{Subcase E2b.}
Suppose that $t=d-1$.

Delete every vertex of $B_3$, except for $x_2$,
to obtain $G'$.
Find $U'$ by the induction hypothesis,
and let $U$ be $U'$ plus $y'$, $z_1$, $z_2$,
and the $d-1$ partial vertices.
Then
\begin{align*}
\frac{w(U)-w(U')}{w(G)-w(G')} &= \frac{3+(d-1)p}{5+(d-1)p} \quad&&\\
 &> \frac{2+(d-1)p}{4+(d-1)p} \quad&&\\
 &= r_{k,d}. \quad&&\text{by Fact (ii), since $k=2$}
\end{align*}

%\includegraphics{E3.eps}}
\begin{figure}[ht]
\begin{center}
\begin{tabular}{ccccc}
\begin{pspicture}(0.6,0.3)(3.7,3.08)
\pslinewidth 0.5pt
  \psellipse(2.5,2.5)(1.15,0.58)
  \rput(1.1,2.7){$X$}
  \psdot[dotsize=4pt 2](2,2.5)\rput(2.1,2.7){$x_1$}
  \psdot[dotsize=4pt 2](3,2.5)\rput(3.1,2.7){$x_2$}
  \psdot[dotsize=4pt 2](2.5,1.2)\rput(2.2,1.0){$y$}
  \psline(2,2.5)(3,2.5)(2.5,1.2)(2,2.5)
  \psdot[dotsize=4pt 2](1.5,1.7) %left of y
  \rput(1.8,1.8){$y'$}
  \psline(2,2.5)(1.5,1.7)(2.5,1.2)
  \psdots[dotsize=4pt 2](0.6,2)(1,1.2)%next level left of y
  \rput(0.3,1.9){$z_1$}
  \rput(0.7,1.1){$z_2$}
  \psline(2,2.5)(0.6,2)(1.5,1.7)(1,1.2)(2.5,1.2)
  \psdots[dotsize=4pt 2](3.3,1.2)(3.7,2) %right of y
  \psline(2.5,1.2)(3.3,1.2)(3,2.5)
  \psdots[dotsize=1pt 1](3.42,1.44)(3.5,1.6)(3.58,1.76)
  \psline(2.5,1.2)(3.7,2)(3,2.5)
%below y:
  \pscurve(2.5,1.2)(2.3,0.8)(2.2,0.3)
  \psline(2.5,1.2)(2.5,0.3)
  \pscurve(2.5,1.2)(2.7,0.8)(2.8,0.3)
  \psdots[dotstyle=Bo,dotsize=4pt 2](2.2,0.3)(2.5,0.3)(2.8,0.3)
  \rput(3.9,1.5){($h$)}
\end{pspicture}
& \qquad \ &
\begin{pspicture}(0.6,0.3)(3.7,3.08)
\pslinewidth 0.5pt
  \psellipse(2.5,2.5)(1.15,0.58)
  \rput(1.1,2.7){$X$}
  \psdot[dotsize=4pt 2](2,2.5)\rput(2.1,2.7){$x_1$}
%  \psdot[dotsize=4pt 2](3,2.5)\rput(3.1,2.7){$x_2$}
  \psline(2.5,1.2)(2,2.5)
  \psdot[dotstyle=Bo,dotsize=4pt 2](2.5,1.2)\rput(2.2,1.0){$y$}
%  \psdot[dotsize=4pt 2](1.5,1.7) %left of y
%  \rput(1.1,1.56){$y'$}
%  \psline(2,2.5)(1.5,1.7)(2.5,1.2)
  \rput(0.3,1.9){$z_1$}
  \psline(2,2.5)(0.6,2)%(1.5,1.7)(1,1.2)(2.5,1.2)
  \psdots[dotstyle=Bo,dotsize=4pt 2](0.6,2)%next level left of y
%  \psdots[dotsize=4pt 2](3.3,1.2)(3.7,2) %right of y
%  \psline(2.5,1.2)(3.3,1.2)(3,2.5)
%  \psdots[dotsize=1pt 1](3.42,1.44)(3.5,1.6)(3.58,1.76)
%  \psline(2.5,1.2)(3.7,2)(3,2.5)
\end{pspicture}
& \qquad \ &
\begin{pspicture}(0.6,0.3)(3.7,3.08)
\pslinewidth 0.5pt
  \psellipse(2.5,2.5)(1.15,0.58)
  \rput(1.1,2.7){$X$}
  \psdot[dotsize=4pt 2](2,2.5)\rput(2.1,2.7){$x_1$}
  \psdot[dotsize=4pt 2](3,2.5)\rput(3.1,2.7){$x_2$}
%  \psdot[dotsize=4pt 2](2.5,1.2)\rput(2.1,1.0){$y$}
  \psline(2,2.5)(3,2.5)
  \psdot[dotsize=4pt 2](1.5,1.7) %left of y
  \rput(1.8,1.8){$y'$}
  \psline(2,2.5)(1.5,1.7)
%  \psdots[dotsize=4pt 2](0.6,2)(1,1.2)%next level left of y
  \rput(0.3,1.9){$z_1$}
  \rput(0.7,1.1){$z_2$}
  \psline(2,2.5)(0.6,2)(1.5,1.7)(1,1.2)%(2.5,1.2)
  \psline(3.3,1.2)(3,2.5)
  \psline(3.7,2)(3,2.5)
  \psdots[dotsize=4pt 2](0.6,2)%next level left of y
  \psdots[dotstyle=Bo,dotsize=4pt 2](1,1.2)%next level left of y
  \psdots[dotstyle=Bo,dotsize=4pt 2](3.3,1.2)(3.7,2) %right of y
  \psdots[dotsize=1pt 1](3.42,1.44)(3.5,1.6)(3.58,1.76)
  \rput(3.9,1.5){($h$)}
\end{pspicture}
\end{tabular}
\caption{Case E3 (left) and results of Subcases E3a (center) and E3b (right).}
\label{F:E3}
\end{center}
\end{figure}

\runinhead{Case E3.}
Suppose that $B_3$ contains exactly one lobe of depth $2$,
and at least one full simplicial vertex
other than those in the lobe of depth $2$.

Let $h$ be the number of full simplicials outside of the depth $2$ lobe;
each of these has
neighborhood $\{x_2, y\}$.
(See the first graph in Figure~\ref{F:E3}.)
Then $B_3$ has exactly $h+6$ full vertices.
%As in Case E2,
%let $z_1$ be the simplicial vertex in the depth $2$ lobe
%that is adjacent to $x_1$,
%let $z_2$ be the simplicial vertex in the depth $2$ lobe
%that is adjacent to $y$,
%let $y'$ be the star center of the depth $2$ lobe,
%and let $t$ be the number of partial vertices adjacent to $y$.
We have two subcases:
Subcase E3a, in which $h+t\le d-2$,
and Subcase E3b, in which $h+t\ge d-1$.

\runinhead{Subcase E3a.}
Suppose that $h+t\le d-2$.

Delete the $t$ partial vertices, $x_2$, $y'$, $z_2$,
and the $h$ full simplicials,
and make $y$ and $z_1$ partial.
Let $G'$ be the resulting graph.
(See the second graph in Figure~\ref{F:E3}.)
Find $U'$ by the induction hypothesis,
and let $U$ be $U'$ plus $z_2$, the $h$ full simplicials,
and the $t$ partial vertices.
Note that $y,z_1\in U$.
Thus,
\begin{align*}
\frac{w(U)-w(U')}{w(G)-w(G')} &= \frac{h+1+tp+2(1-p)}{h+3+tp+2(1-p)} \quad&&\\
 &\ge \frac{2+2(1-p)}{4+2(1-p)} \quad&&\text{minimized when $h=1$ \& $t=0$}\\
 &= \frac{2-p}{3-p} \quad&&\\
 &= r_{k,d}. \quad&&\text{by Fact (i), since $k=2$}
\end{align*}

\runinhead{Subcase E3b.}
Suppose that $h+t\ge d-1$.

Delete $y$ and the $t$ partial vertices,
and make the $h$ full simplicials and $z_2$ partial.
Let $G'$ be the resulting graph.
(See the last graph in Figure~\ref{F:E3}.)
Find $U'$ by the induction hypothesis,
and let $U$ be $U'$ plus the $t$ partial vertices.
Note that $U$ contains the $h$ full simplicials and $z_2$.
Then
\begin{align*}
\frac{w(U)-w(U')}{w(G)-w(G')} &= \frac{tp+(h+1)(1-p)}{tp+(h+1)(1-p)+1}.
  \quad&&\\
\intertext{We minimize the right-hand size above
by setting $t=d-2$ and $h=1$.
To see this, note that, when $d\ge 3$, we have $1-p\ge p$.
Thus, to minimize $tp+(h+1)(1-p)$, while maintaining $h+t\ge d-1$,
we set $h$ as small as possible ($h=1$)
and $t$ only as large as necessary ($t = d-1-h = d-2$).
Continuing:}
 &\ge \frac{(d-2)p+2(1-p)}{(d-2)p+2(1-p)+1}
   \quad&&\\
 &\ge \frac{p+2(1-p)}{p+2(1-p)+1}
   \quad&&\text{minimized when $d=3$}\\
 &= \frac{2-p}{3-p}
   \quad&&\\
 &= r_{k,d}.
   \quad&&\text{by Fact (i), since $k=2$}
\end{align*}
%% NOTE: The above rigamarole is really all about getting t to be nonzero.

This completes the proof of Lemma~\ref{L:if-full}.\ggcendpf\end{proof}

We have now proven Theorem~\ref{Th:if-nice}.
In the next section we consider sharpness of this result.
% Yes, I know the reader can just look down and see the next section
% title. However, when reading through all the details, it is easy
% to lose track of the big picture, which, at this point, is the following:
% We are in the middle of a huge discussion of Theorem 1.1; we just
% proved it; next comes sharpness. I think it is worthwhile to remind
% the reader of all this. (GGC)


\section{Sharpness of Theorem~\ref{Th:if-nice}} \label{S:sharp}

We construct
examples to show that, for each $k,d\ge 2$,
the bound of Theorem~\ref{Th:if-nice} is tight to within $1$
for all $n\ge 1$,
and exactly sharp for infinitely many values of $n$.

\begin{example} \label{Ex:sharp}
We construct a graph $G(k,d,n)$ for each $n\ge 1$ and $k,d\ge 2$.

If $n\le k+1$, then let $G(k,d,n)=K_n$.

For the case when $n\ge k+2$,
choose nonnegative integers $a$, $h$ with $h\le kd+d$.
Let $n=k+2+a(kd+d+1)+h$.
Note that each $n\ge k+2$ is obtained from a unique pair $a$, $h$.

Let $b=\lfloor{h/(k+1)}\rfloor$, and let $c=h-b(k+1)$,
so that $h = b(k+1)+c$, $0\le b\le d$, and $0\le c\le k$.

Now we construct $G(k,d,n)$.
%The structure of $G(k,d,n)$ is illustrated
%in Figure~\ref{F:general-sharp}.
Let $z_0,\ldots,z_a$ be distinct vertices.
For each pair $(i,j)$ with $1\le i\le a$ and $1\le j\le d$,
for each pair $(i,j)$ with $i=a+1$ and $1\le j\le b$, and for $(i,j)=(1,0)$,
let $S_{i,j}$ be a $k$-clique, with every vertex
adjacent to $z_{i-1}$ and to another vertex $x_{i,j}$.
If $c\ne 0$, then let $S'$ be a $c$-clique,
each of whose vertices is adjacent to $z_a$.
Note that we have specified $(a+1)+(ad+b+1)(k+1)+c=n$ vertices.
In each $S_{i,j}$, choose a vertex $y_{i,j}$.
For each $1\le i\le a$,
let $z_i$ be adjacent to every vertex in $S_{i,d}-y_{i,d}+x_{i,d}$.

This defines $G(k,d,n)$.
See Figures~\ref{F:general-sharp} and \ref{F:sharp-nonplanar}
for illustrations.\ggcendexample\end{example}

\begin{figure}[ht]
\begin{center}
\psfrag{S10}{$S_{1,0}$}
\psfrag{S11}{$S_{1,1}$}
\psfrag{S1d-1}{$S_{1,d-1}$}
\psfrag{S1d}{$S_{1,d}$}
\psfrag{S21}{$S_{2,1}$}
\psfrag{S2d-1}{$S_{2,d-1}$}
\psfrag{S2d}{$S_{2,d}$}
\psfrag{S31}{$S_{3,1}$}
\psfrag{S3d-1}{$S_{3,d-1}$}
\psfrag{S3d}{$S_{3,d}$}
\psfrag{S41}{$S_{4,1}$}
\psfrag{S4b}{$S_{4,b}$}
\psfrag{Ss}{$S'$}
\psfrag{x10}{$x_{1,0}$}
\psfrag{x11}{$x_{1,1}$}
\psfrag{x1d-1}{$x_{1,d-1}$}
\psfrag{x1d}{$x_{1,d}$}
\psfrag{x21}{$x_{2,1}$}
\psfrag{x2d-1}{$x_{2,d-1}$}
\psfrag{x2d}{$x_{2,d}$}
\psfrag{x31}{$x_{3,1}$}
\psfrag{x3d-1}{$x_{3,d-1}$}
\psfrag{x3d}{$x_{3,d}$}
\psfrag{x41}{$x_{4,1}$}
\psfrag{x4b}{$x_{4,b}$}
\psfrag{y1d}{$y_{1,d}$}
\psfrag{y2d}{$y_{2,d}$}
\psfrag{y3d}{$y_{3,d}$}
\psfrag{z0}{$z_0$}
\psfrag{z1}{$z_1$}
\psfrag{z2}{$z_2$}
\psfrag{z3}{$z_3$}
\includegraphics[scale=1.07]{general-sharp.eps}
\caption{The structure of $G(k,d,n)$ with $a=3$. %and $c\ne 0$ and $d,b\ge 2$.
Circles represent $k$-cliques.
Although every $k$-clique $S_{i,j}$ contains a vertex $y_{i,j}$, those vertices are only indicated in the figure when both $i\le a$ and $j=d$.}
\label{F:general-sharp}
\end{center}
\end{figure}

\begin{figure}[ht]
\begin{center}
%\begin{pspicture}(-1.1,0.2)(12.5,3.2)
\begin{pspicture}(-1.1,0.2)(11,3.2)
\pslinewidth 0.5pt
\psdot[dotsize=4pt 2](-1,0.5) %x_{1,0}
\rput(-1.1,0.80){$x_{1,0}$}
\psdots[dotsize=4pt 2](0,0.35)(0,1)(0.5,0)(0.5,0.65) %S_{1,0}
\rput(0.25,1.3){$S_{1,0}$}
\pslinewidth 1.2pt
\psline(0,0.35)(0,1)(0.5,0)(0.5,0.65)
\psline(0,1)(0.5,0.65)(0,0.35)(0.5,0)
\pslinewidth 0.5pt
\psline(2.5,0.5)(0,0.35)(-1,0.5)
\psline(2.5,0.5)(0,1)(-1,0.5)
\psline(2.5,0.5)(0.5,0)(-1,0.5)
\psline(2.5,0.5)(0.5,0.65)(-1,0.5)
\psdot[dotsize=4pt 2](2.5,0.5) % z_0
\rput(2.5,0.2){$z_0$}
\psdots[dotsize=4pt 2](1,2)(1.5,2.5)(1.5,2)(2,2.5) %S_{1,1}
\rput(0.6,2.25){$S_{1,1}$}
\pslinewidth 1.2pt
\psline(1,2)(1.5,2.5)(1.5,2)(2,2.5)
\psline(1.5,2.5)(2,2.5)(1,2)(1.5,2)
\pslinewidth 0.5pt
\psdot[dotsize=4pt 2](1,3) %x_{1,1}
\rput(1.2,3.2){$x_{1,1}$}
\psline(2.5,0.5)(1,2)(1,3)
\psline(2.5,0.5)(1.5,2.5)(1,3)
\psline(2.5,0.5)(1.5,2)(1,3)
\psline(2.5,0.5)(2,2.5)(1,3)
\psdots[dotsize=4pt 2](3,2.5)(3.5,2)(3.5,2.5)(4,2) %S_{1,2}
\rput(4.4,2.25){$S_{1,2}$}
\pslinewidth 1.2pt
\psline(3,2.5)(3.5,2)(3.5,2.5)(4,2)
\psline(3.5,2)(4,2)(3,2.5)(3.5,2.5)
\pslinewidth 0.5pt
\psdot[dotsize=4pt 2](4,3) %x_{1,2}
\rput(4.2,3.2){$x_{1,2}$}
\psline(2.5,0.5)(3,2.5)(4,3)
\psline(2.5,0.5)(3.5,2)(4,3)
\psline(2.5,0.5)(3.5,2.5)(4,3)
\psline(2.5,0.5)(4,2)(4,3)
\psdots[dotsize=4pt 2](4.5,0.50)(4.65,1.2)(5,0)(5.35,1.2)(5.5,0.50) %S_{1,d}
\rput(4.9,1.5){$S_{1,3}$}
\rput(5.9,0.65){$x_{1,3}$}
\rput(4.1,0.65){$y_{1,3}$}
\psline(4.5,0.50)(4.65,1.2)(5,0)(5.35,1.2)(5.5,0.50)(4.5,0.50)(5,0)(5.5,0.50)(4.65,1.2)(5.35,1.2)(4.5,0.50)
\pslinewidth 1.2pt
\psline(4.5,0.50)(4.65,1.2)(5,0)(5.35,1.2)
\psline(4.65,1.2)(5.35,1.2)(4.5,0.50)(5,0)
\pslinewidth 0.5pt
\psline(2.5,0.5)(4.5,0.50)
\psline(2.5,0.5)(4.65,1.2)(7.5,0.5)
\psline(2.5,0.5)(5,0)(7.5,0.5)
\psline(2.5,0.5)(5.35,1.2)(7.5,0.5)
\psline(2.5,0.5)(5.5,0.50)(7.5,0.5)
\psdot[dotsize=4pt 2](7.5,0.5) % z_1
%
\rput(7.5,0.2){$z_1$}
\psdots[dotsize=4pt 2](6,2)(6.5,2.5)(6.5,2)(7,2.5) %S_{2,1}
\rput(5.6,2.25){$S_{2,1}$}
\pslinewidth 1.2pt
\psline(6,2)(6.5,2.5)(6.5,2)(7,2.5)
\psline(6.5,2.5)(7,2.5)(6,2)(6.5,2)
\pslinewidth 0.5pt
\psdot[dotsize=4pt 2](6,3) %x_{2,1}
\rput(6.2,3.2){$x_{2,1}$}
\psline(7.5,0.5)(6,2)(6,3)
\psline(7.5,0.5)(6.5,2.5)(6,3)
\psline(7.5,0.5)(6.5,2)(6,3)
\psline(7.5,0.5)(7,2.5)(6,3)
\psdots[dotsize=4pt 2](8,2.5)(8.5,2)(8.5,2.5)(9,2) %S_{2,2}
\rput(9.4,2.25){$S_{2,2}$}
\pslinewidth 1.2pt
\psline(8,2.5)(8.5,2)(8.5,2.5)(9,2)
\psline(8.5,2)(9,2)(8,2.5)(8.5,2.5)
\pslinewidth 0.5pt
\psdot[dotsize=4pt 2](9,3) %x_{2,2}
\rput(9.2,3.2){$x_{2,2}$}
\psline(7.5,0.5)(8,2.5)(9,3)
\psline(7.5,0.5)(8.5,2)(9,3)
\psline(7.5,0.5)(8.5,2.5)(9,3)
\psline(7.5,0.5)(9,2)(9,3)
\psdots[dotsize=4pt 2](9.5,0.50)(9.65,1.2)(10,0)(10.35,1.2)(10.5,0.50) %S_{2,d}
\rput(9.9,1.5){$S_{2,3}$}
\rput(10.9,0.65){$x_{2,3}$}
\rput(9.1,0.65){$y_{2,3}$}
\psline(9.5,0.50)(9.65,1.2)(10,0)(10.35,1.2)(10.5,0.50)(9.5,0.50)(10,0)(10.5,0.50)(9.65,1.2)(10.35,1.2)(9.5,0.50)
\pslinewidth 1.2pt
\psline(9.5,0.50)(9.65,1.2)(10,0)(10.35,1.2)
\psline(9.65,1.2)(10.35,1.2)(9.5,0.50)(10,0)
\pslinewidth 0.5pt
\psline(7.5,0.5)(9.5,0.50)
\psline(7.5,0.5)(9.65,1.2)%(12.5,0.5)
\psline(7.5,0.5)(10,0)%(12.5,0.5)
\psline(7.5,0.5)(10.35,1.2)%(12.5,0.5)
\psline(7.5,0.5)(10.5,0.50)%(12.5,0.5)
%\psdot[dotsize=4pt 2](12.5,0.5) % z_2
%\rput(12.5,0.2){$z_2$}
\end{pspicture}
\caption{$G(k,d,n)$ with $n=37, k=4, d=3$;
thus $a=1$, $h=kd+d=15$, $b=d=3$, and $c=0$.
Edges within each $S_{i,j}$ are shown in bold.}
\label{F:sharp-nonplanar}
\end{center}
\end{figure}

Now we investigate $f_d\bigl(G(k,d,n)\bigr)$.

\begin{proposition} \label{P:examplemax}
Let $k,d\ge 2$.
Then the following both hold.
\enumromanparen % Labels (i), (ii), etc.
\begin{enumerate}
\item For each $n\ge 1$, the graph $G(k,d,n)$, from Example~\ref{Ex:sharp},
has order $n$ and treewidth at most $k$,
and
\[
f_d\bigl(G(k,d,n)\bigr) \le
1 + \left\lceil \frac{2dn+2}{kd+d+1} \right\rceil
  = 1 + \left\lceil r_{k,d}\cdot n + \frac{r_{k,d}}{d} \right\rceil.
\]
\item There exist infinitely many values of $n\ge 1$
for which
\[
f_d\bigl(G(k,d,n)\bigr) =
\left\lceil \frac{2dn+2}{kd+d+1} \right\rceil
  = \left\lceil r_{k,d}\cdot n + \frac{r_{k,d}}{d} \right\rceil.
\]
\end{enumerate}
\end{proposition}

\begin{proof}
Let $G = G(k,d,n)$.
It follows immediately from the construction
that the order of $G$ is $n$.
Since this graph is chordal,
its treewidth is $1$ less than its clique number.
If $n\le k+1$, then the graph is complete,
and its treewidth is $n-1 \le k$.
If $n\ge k+2$, then each $S_{i,j}+x_{i,j}$
induces a maximum clique of order $k+1$,
and the treewidth is $k$.

Suppose that $n\le k+1$.
The expression $\lceil(2dn+2)/(kd+d+1)\rceil$
has positive numerator and denominator,
and so its value is at least $1$.
Since $G\cong K_n$, an induced forest can have at most two vertices,
and so statement~(i) of the proposition holds for these values of $n$.

Now suppose that $n\ge k+2$.
Let $a$, $h$, $b$, and $c$ be as in Example~\ref{Ex:sharp}.
We will refer to an induced forest of maximum degree at most $d$
and maximum order,
as an \localdefterm{optimal forest}.

Note that if there are vertices $v,v'$ in $G$
with $N(v)-v'\subseteq N(v')-v$,
and if there is an optimal forest that contains $v'$ but not $v$,
then, by removing $v'$ and adding $v$, we obtain
another optimal forest that contains $v$ but not $v'$.
Thus, if $v_1,v_2,v_3$ are vertices of a triangle for which
$N(v_1)-v_3\subseteq N(v_3)-v_1$ and
$N(v_2)-v_3\subseteq N(v_3)-v_2$,
then we can find an optimal forest that does not contain $v_3$.

Applying these ideas to triples in
each $S_{i,j}+x_{i,j}$,
it follows that
there is an optimal forest $T$ that does not meet any $S_{i,j}-y_{i,j}$.
%It was confusing before.  Also, this more clearly defines $W$.
%(Unspecific choice of vertex/vertices in S' doesn't matter due to symmetry.)
If $|S'|\ge 2$, then by applying the ideas to triples in $S'+z_a$,
we may assume that $T$ does not contain $z_a$ and $T$ contains at most
$2$ vertices of $S'$.
%% NOTE: The basic idea above works for pairs. We use triples,
%% because a forest cannot meet a triangle in more than 2 vertices,
%% and so we automatically get that v that doesn't lie in the forest.

Removing from consideration those vertices that
have been excluded from $T$,
we are left with a set containing
$z_i$ for $i<a$,
all $x_{i,j}$ and $y_{i,j}$,
and $\min\{2,|S'+z_1|\}$ vertices of $S'+z_a$.
The number of $x_{i,j}$ vertices is $ad+b+1$;
the number of $y_{i,j}$ vertices is the same.
Let $W$ be this set of vertices, so that $V(T)\subseteq W$.
Then
\[
|W|
  \le a+2\left[ad+b+1\right]+2
  = a+2ad+2b+4.
\]

Each $z_i$ with $i<a$ has degree $d+1$
in $G[W]$.
Further, in $G[W]$,
the sets $N(z_i)+z_i$ for $0\le i<a$,
are pairwise disjoint;
$T$ thus misses at least one vertex
from each of these $a$ sets.
Subtracting $a$, we obtain an upper bound of $2ad+2b+4$
for the order of $T$.

If $c=0$, then we can do better, since $S'$ has no vertices,
and so $T$ has order at most $2ad+2b+3$.
If $h = kd+d$, then $c=0$ and $b=d$, and we can do better still.
Because $S'$ has no vertices,
we have $z_a\in W$.
Further, vertex $z_a$ has degree $d+1$ in $G[W]$,
and so reasoning as before,
$T$ misses at least one vertex
from the set $N(z_a)+z_a$.
We conclude that, if $h=kd+d$, then $T$ has order at most $2ad+2b+2$.

Substituting
$n = k+2+a(kd+d+1)+h$ and $h = b(k+1)+c$,
in the left-hand side below,
we obtain
\[
\left\lceil \frac{2dn+2}{kd+d+1} \right\rceil
 = 2ad+2b+2 +
  \left\lceil \frac{2(d-b) + 2dc}{kd+d+1} \right\rceil
 \ge 2ad+2b+2,
\]
with the inequality following from the fact that $b\le d$.

When $h = kd+d$, we showed that $T$ has order at most $2ad+2b+2$;
thus, in this case,
$|V(T)|\le \lceil (2dn+2)/(kd+d+1) \rceil$.
%\[
%|V(T)|\le \left\lceil \frac{2dn+2}{kd+d+1} \right\rceil.
%\]
That is, an optimal forest has at most this order
for the infinitely many $n\ge k+2$ with $n\equiv k+1 \pmod{kd+d+1}$.
Together with the lower bound in Theorem~\ref{Th:if-nice},
this shows that statement~(ii) of the proposition holds.

We also showed that, if $c=0$, then $T$ has order at most $2ad+b+3$.
This shows that statement~(i) holds when $c = 0$.
On the other hand, if $c\ne 0$, then $b < d$,
and so the right-hand side of the above inequality
can be increased to $2ad+2b+3$.
Since we showed that the order of $T$ is always at most $2ad+b+4$,
we conclude that
statement~(i) of the proposition holds for all $n$.\ggcendpf\end{proof}

By Proposition~\ref{P:examplemax}, we have the following.

\begin{corollary}
Let $k,d\ge 2$.
Then the bound of Theorem~\ref{Th:if-nice} is tight to within $1$
for all $n\ge 1$,
and exactly sharp
for infinitely many values of $n$.\ggcnopf\end{corollary}

In particular, the coefficient of $n$
in the bound of Theorem~\ref{Th:if-nice},
$r_{k,d}=2d/(kd+d+1)$, is best possible.


\section{Other Values of $k$ and $d$} \label{S:otherkd}

We have established
a lower bound on $f_d(G)$ when $k,d\ge 2$.
Now we look at other values of $k$, $d$.
We consider first $k<2$, and then $d<2$.


\subsection{Values of $k < 2$}

If we set $k = 0,1$, then the bound of Theorem~\ref{Th:if-nice}
may not hold.
In particular, for each $d\ge 2$ and $k=0,1$,
there exist graphs for which the bound does not hold.


\subsubsection{$k=0$} \label{Sss:k=0}

For $k=0$, this is obvious, since, when $d\ge 2$ and $k=0$,
we have $r_{k,d} = 2d/(d+1) > 1$.

The actual bound when $k=0$ is trivial.
The graphs of treewidth $0$ are precisely the graphs with no edges.
Thus, every induced subgraph of such a graph is a forest with
maximum degree $0$,
and so the correct bound, for $G$ a graph of order $n$, is given by
\[
f_d(G) = n.
\]


\subsubsection{$k=1$}

The case when $k=1$ is a bit more interesting.
The graphs of treewidth at most $1$ are precisely the forests.
We seek a lower bound on the maximum order of
an induced forest with bounded degree, in a forest.

First we show that, if we allow $k=1$,
then the bound of Theorem~\ref{Th:if-nice}
does not hold for $d\ge 2$.
When $k=1$, we have $r_{k,d} = 2d/(2d+1)$.
Let $G = K_{1,d+1}$;
this has order $n=d+2$.
Then $f_d(G) = d+1 =  n\cdot (d+1)/(d+2)$,
which is too small, since $(d+1)/(d+2) < 2d/(2d+1)$ when $d\ge 2$.

This fraction $(d+1)/(d+2)$ gives us the best lower bound.
The following result is due to
Chappell, Gimbel, and Hartman~\cite{CGHmanu};
it is restated using our notation.
For completeness, we provide the proof
(again, rewritten using our notation).

\begin{proposition}[Chappell, Gimbel, \& Hartman] \label{P:treeintree}
Let $d\ge 0$.
If $G$ is a graph with treewidth at most $1$,
(i.e., a forest)
and order $n$,
then
\[
f_d(G) \ge \left\lceil \frac{(d+1)n}{d+2} \right\rceil.
\]
\end{proposition}

\begin{proof}
We construct an induced forest $T$
of maximum degree at most $d$
and order at least $(d+1)n/(d+2)$.
We proceed by induction on $n$.
If $n\le d+1$,
then we may set $T = G$,
and the result holds.

Suppose that $n\ge d+2$.
If $G$ is not connected,
then apply the induction hypothesis to each component.

We may thus assume that $G$ is a tree.
Choose a vertex $x$ of $G$,
and call $x$ the \localdefterm{root} of $G$,
so that $G$ becomes a rooted tree,
and we can talk about \localdefterm{descendants} in $G$.
Consider the collection of all vertices of $G$ that have
more than $d$ descendants.
This collection is nonempty, since it contains the root.
Let $v$ be a vertex in this collection that is as far from the root
as possible.

Remove $v$ and all of its descendants from $G$, to obtain $G'$.
Apply the induction hypothesis to obtain a forest $T'$,
and let $T$ be the subgraph induced by the vertices in $T'$,
together with the descendants of $v$.
The descendants of $v$ induce a subgraph with maximum degree at most $d$.
Furthermore,
\[
\frac{|V(T)|-|V(T')|}{|V(G)|-|V(G')|} \ge \frac{d+1}{d+2},
\]
and so $T$ is the required forest.\ggcendpf\end{proof}

The example of $K_{1,d+1}$ shows that the fraction
$(d+1)/(d+2)$ in Proposition~\ref{P:treeintree} is best possible.
Letting $G$ be a disjoint union of copies of $K_{1,d+1}$,
plus one smaller star if $d+2$ does not divide $n$,
we can verify
that the bound of the proposition is sharp for all $n\ge 0$.
If connected examples are desired,
then add edges joining the various stars.


\subsection{Values of $d < 2$}


\subsubsection{$d=0$}

When $d=0$, we seek a lower bound
on the size of a maximum independent set in a graph $G$.
If we allow $d=0$,
then the bound of Theorem~\ref{Th:if-nice} is equal to~$2$,
since $r_{k,0} = 0$.
This bound holds trivially, as long as $G$ is not a complete graph.
However, we can find a better bound.

The best lower bound follows from
the fact that a graph with treewidth at most $k$
is $(k+1)$-colorable.
(To see this, find a chordal supergraph with clique number $k+1$,
remove a simplicial vertex, color the remainder of the graph by induction,
and then replace the simplicial, giving it a color not used on its
neighbors, of which there are at most $k$.)
Given such a coloring, we can take the largest color class.
Thus, we obtain the following well known result.
Note that $f_0(G)$ is the independence number of $G$.

\begin{proposition} \label{P:twindep}
Let $k\ge 0$.
If $G$ is a graph with order $n$ and treewidth at most $k$,
then
\[
f_0(G) \ge \left\lceil \frac{n}{k+1} \right\rceil.\ggcnopf
\]
\end{proposition}

Once again, the fraction $1/(k+1)$ in Proposition~\ref{P:twindep}
is best possible,
and the proposition is sharp for all $n\ge 0$.
To see this, let $G$ be a disjoint union of copies of $K_{k+1}$,
plus one smaller clique if $k+1$ does not divide $n$.
As before, we can add edges, if connected examples are desired.


\subsubsection{$d=1$}

The truly interesting case is that in which $d=1$.

If we allow $d=1$,
then the bound of Theorem~\ref{Th:if-nice} does not hold.
To see this, let $G = K_{k+2}-e$, that is,
a complete graph on $k+2$ vertices with one edge removed.
This $G$ has treewidth $k$,
but the greatest order of an induced forest
with maximum degree at most $1$, is $2$, which is too small.
Larger counterexamples can be constructed
using disjoint unions of copies of this graph;
these may be joined by edges if connected counterexamples are desired.

However, although allowing $d=1$
would make the bound of Theorem~\ref{Th:if-nice} false,
we suspect that it is ``nearly true''.
It appears that the coefficient of $n$ (i.e., $r_{k,1}$) is correct;
the only problem is the ``$+2$'' in the numerator.
Thus, we make the following conjecture.

\begin{conjecture} \label{J:d=1_b}
Let $k\ge 0$.
If $G$ is a graph with order $n$ and treewidth at most $k$,
then
\[
f_1(G) \ge \left\lceil \frac{2n}{k+2} \right\rceil
 = \left\lceil r_{k,1}\cdot n \right\rceil.\ggcnopf
\]
\end{conjecture}

If this conjecture holds,
then the fraction $2/(k+2)=r_{k,1}$ is best possible.
The bound would not be exactly sharp for all $n$;
for example, when $k\ge 2$ and $n=2$, the above bound is $1$,
while $f_1(G)=2$ for every $2$-vertex graph $G$.
However, like Theorem~\ref{Th:if-nice},
the bound would be tight to within $1$ for all $n$
and exactly sharp for infinitely many values of $n$.
We can show this by letting $G$ be
a disjoint union of copies of $K_{k+2}-e$,
plus one smaller clique if $k+2$ does not divide $n$.
And again, we can add edges, if connected examples are desired.

Later, we will prove Conjecture~\ref{J:d=1_b} for $k\le 3$.
However, although we cannot prove Conjecture~\ref{J:d=1_b}
for all values of $k$,
we can make use of Lemma~\ref{L:if-full} to prove
the following weaker result for all $k\ge 2$.

\begin{theorem}
Let $k\ge 2$.
If $G$ is a graph with order $n\ge 1$ and treewidth at most $k$,
then
\[
f_1(G) \ge \frac{2n+2}{2k+3}.
\]
\end{theorem}

\begin{proof}
Let $k$, $G$, and $n$ be as in the statement of the theorem.
Define $G'$ by attaching a partial vertex of weight
$p=2/(2k-1)$ to each vertex of $G$,
and let $P$ be the set of partial vertices.
Note that our $p$ has the same value as that used in Lemma~\ref{L:if-full}
when $d=2$ and $k$ is our given value.
Apply Lemma~\ref{L:if-full} to $G'$
with $k$ having the given value and $d=2$,
to obtain $U'$,
and let $U=U'-P$.
Then $U$ induces a forest of maximum degree at most~$1$ in $G$.
Also, $w(U')\ge r_{k,2}\cdot w(G')+r_{k,2}/2$, with $w(G')=n+np$,
and so
\begin{align*}
w(U) &= w(U')-np\\
  &\ge r_{k,2}\cdot w(G') + \frac{r_{k,2}}{2} -np\\
  &= r_{k,2}\cdot (n+np) + \frac{r_{k,2}}{2} -np\\
  &= \frac{4}{2k+3}\left({n+\frac{2n}{2k-1}}\right)
    +\frac{2}{2k+3}-\frac{2n}{2k-1}\\
  &= \frac{2n+2}{2k+3}.\ggcendpf
\end{align*}
\end{proof}

Again, we can prove the stronger bound of Conjecture~\ref{J:d=1_b}
for $k\le 3$.

\begin{theorem} \label{Th:d1-nice}
Let $k$ be an integer with $0\le k \le 3$.
If $G$ is a graph with order $n$ and treewidth at most $k$,
then
\[
f_1(G) \ge \left\lceil \frac{2n}{k+2} \right\rceil
 = \left\lceil r_{k,1}\cdot n \right\rceil.\ggcnopf
\]
\end{theorem}

The $k=0$ case of Theorem~\ref{Th:d1-nice}
follows from the discussion in Subsection~\ref{Sss:k=0}.
The $k=1$ case follows from Proposition~\ref{P:treeintree}.
The $k=2$ and $k=3$ cases follow from the next two lemmas,
respectively.

We prove the $k=2$ case using techniques similar to those
used in the proof of Lemma~\ref{L:if-full}.
However, the proof is much shorter,
and there is no need for partial vertices.

\begin{lemma} \label{L:d1k2}
If $G$ is a graph with order $n$ and treewidth at most $2$,
then $G$ contains an induced forest $T$,
so that $T$ has maximum degree at most $1$,
and
\[
|V(T)| \ge \frac{2n}{4}
 = r_{2,1}\cdot n.\ggcnopf
\]
\end{lemma}

\begin{proof}
Let $G$ and $n$ be as in the statement of the lemma.
We proceed by induction on $n$.
If $n=0$, then the result is trivially true;
assume, therefore, that $n\ge 1$.

We may also assume that $G$ is connected
and is either a $2$-tree or a complete graph with at most $3$ vertices.
If not, then we can add edges to $G$,
without increasing its treewidth beyond $2$,
until it lies in one of these categories.

Let $G^*$ be the graph obtained from $G$ by removing every vertex
that is simplicial in $G$.

If $V(G^*) = \varnothing$,
that is, if every vertex in $G$ is simplicial,
then $G$ is a complete graph with $1$, $2$, or $3$ vertices.
If $G$ is $K_1$ or $K_2$, then let $T = G$;
if $G$ is $K_3$,
then let $T$ be the subgraph induced by any $2$ vertices of $G$,
and we are done.

%Thus, we may assume that $G$ is a $2$-tree.
If there are two simplicial vertices $z$ and $z'$ in $G$
that have the same ($2$-vertex) neighborhood,
then delete this neighborhood, along with $z$ and $z'$,
to obtain $G'$.
Apply the induction hypothesis to obtain $T'$,
and let $T$ be $T'+z+z'$.
Then
\[
\frac{|V(T)|-|V(T')|}{|V(G)|-|V(G')|} = \frac{2}{4}.
\]

\medskip

Henceforth, we assume
that $V(G^*)\ne \varnothing$,
and
that no two simplicial vertices in $G$
have the same neighborhood.

%% NOTE: "depth" below is not quite used in a formal sense,
%% because we may not have a *lobe*; it might be the whole graph.
%% Thus, "depth" is not a formal statement, but just something intended
%% to help the reader understand what is going on.
\runinhead{Depth 2 Cases---}Let $y$ be a vertex
that is simplicial in $G^*$.
Let $X$ be the neighborhood of $y$ in $G^*$.
Let $z_1, \dots, z_m$ be the simplicial vertices in $G$
that are adjacent to $y$.
%% NOTE: Since the z_i's are simplicial in G, they are not in G^*.
%% In particular, { z_1, ..., z_m } and X are disjoint.

%I think it's true, and probably not too hard to show,
%that removing a set of simplicial vertices from a 2-tree will yield
%a 2-tree or $K_k$ with $k\le 2$.
%And I think it generalizes.  However, I doubt it's worth the trouble
%if it can be avoided, as I think it can...
%Proof(?), just in case:
%Delete simplicial vertices of the $k$-tree $G$ and let $G'$ be the result.
%Since tw(G^*)\le tw(G)\le k$, we can add edges $E$ to $G^*$
%to make it a $k$-tree or a complete graph.
%Then $(G^*\cup E)\cup (G-G^*)$ will be $k$-tree,
%because the simplicial vertices are still simplicial w.r.t. $G^*\cup E$.
%But since $G$ is already a $k$-tree, it is maximum w.r.t. adding edges
%and not increasing treewidth, and so $E=\varnothing$.

%PERHAPS:
%Suppose that $|X|\le 1$.
%If $m\ge2$, delete $X\cup y$, and induct...
%If $m=1$, delete $X$, induct...
%Thus we may assume that $|X|=2$.
%OR:
%If $|X|=1$, then $N(z_i)=\{x,y\}$ for $1\le i\le m$, and so $m=1$.
%Apply induction to $G-\{x,y,z\}$ to obtain $T'$, and let $T=T'+yz$.
%OR (and I don't like this):
%If $x\in X$ is a cut-vertex of $G^*$, then $x$ is a cut-vertex of $G$,
%which contradicts that $G$ is a $2$-tree.
%So $|X|=1$ implies that $V=\{x,y,z\}$.
We claim that $|X| = 2$.
If $|X| < 2$,
then the removal of $X$ cannot disconnect $G$,
because $G$ is a $2$-tree,
and so $X\cup\{y,z_1,\dots,z_m\}$ is the entire vertex set of $G$.
Further,
there is exactly one possible neighborhood for the $z_i$ vertices:
$X+y$,
and so all of them have the same neighborhood.
Thus, either there are $2$ simplicials with the same neighborhood,
or, if $m = 1$, $G$ is a complete graph.
Both of these cases have already been covered,
and so we must have $|X| = 2$.
Say $X = \{x_1, x_2\}$.

There are exactly two possible neighborhoods
for the simplicial vertices $z_1, \dots, z_m$:
$\{x_1,y\}$ and $\{x_2,y\}$.
Since no two simplicials can have the same neighborhood,
we must have $m = 1$ or $m = 2$.
(See Figure~\ref{F:new1}.)

\begin{figure}[ht]
\begin{center}
\begin{tabular}{ccc}
\begin{pspicture}(1.1,1.2)(3.9,3.08)
\pslinewidth 0.5pt
  \psellipse(2.5,2.5)(1.15,0.58)
  \rput(1.1,2.7){$X$}
  \psdot[dotsize=4pt 2](2,2.5)\rput(2.1,2.7){$x_1$}
  \psdot[dotsize=4pt 2](3,2.5)\rput(3.1,2.7){$x_2$}
  \psdot[dotsize=4pt 2](2.5,1.2)\rput(2.2,1.0){$y$}
  \psline(2,2.5)(3,2.5)(2.5,1.2)(2,2.5)
  \psdot[dotsize=4pt 2](1.5,1.7) %left of y
  \psline(2,2.5)(1.5,1.7)(2.5,1.2)
%  \psdots[dotsize=4pt 2](3.5,1.7) %right of y
%  \psline(2.5,1.2)(3.5,1.7)(3,2.5)
  \rput(1.2,1.56){$z_1$}
%  \rput(1.4,1.1){$z_1$}
%  \psline(2,2.5)(1.5,1.7)(2.5,1.2)(1.7,1.2)(2,2.5)
%  \psdots[dotsize=4pt 2](0.6,2)(1,1.2)%next level left of y
%  \rput(0.3,1.9){$z_1$}
%  \rput(0.7,1.1){$z_2$}
%  \psline(2,2.5)(0.6,2)(1.5,1.7)(1,1.2)(2.5,1.2)
%  \psdot[dotsize=4pt 2](3.5,1.6)%right of y
%  \rput(3.8,1.5){$z_2$}
\end{pspicture}
& \qquad\ &
\begin{pspicture}(1.1,1.2)(3.9,3.08)
\pslinewidth 0.5pt
  \psellipse(2.5,2.5)(1.15,0.58)
  \rput(1.1,2.7){$X$}
  \psdot[dotsize=4pt 2](2,2.5)\rput(2.1,2.7){$x_1$}
  \psdot[dotsize=4pt 2](3,2.5)\rput(3.1,2.7){$x_2$}
  \psdot[dotsize=4pt 2](2.5,1.2)\rput(2.2,1.0){$y$}
  \psline(2,2.5)(3,2.5)(2.5,1.2)(2,2.5)
  \psdot[dotsize=4pt 2](1.5,1.7) %left of y
  \psline(2,2.5)(1.5,1.7)(2.5,1.2)
  \psdots[dotsize=4pt 2](3.5,1.7) %right of y
  \psline(2.5,1.2)(3.5,1.7)(3,2.5)
  \rput(1.2,1.56){$z_1$}
%  \rput(1.4,1.1){$z_1$}
%  \psline(2,2.5)(1.5,1.7)(2.5,1.2)(1.7,1.2)(2,2.5)
%  \psdots[dotsize=4pt 2](0.6,2)(1,1.2)%next level left of y
%  \rput(0.3,1.9){$z_1$}
%  \rput(0.7,1.1){$z_2$}
%  \psline(2,2.5)(0.6,2)(1.5,1.7)(1,1.2)(2.5,1.2)
%  \psdot[dotsize=4pt 2](3.5,1.6)%right of y
  \rput(3.8,1.5){$z_2$}
\end{pspicture}
\end{tabular}
\caption{We must have $m=1$ or $m=2$
in the depth $2$ cases of the proof of Lemma~\ref{L:d1k2}.}
\label{F:new1}
\end{center}
\end{figure}


If $m = 1$, then delete $X$, $y$, and $z_1$, to obtain $G'$,
apply the induction hypothesis to obtain $T'$,
and let $T$ be $T'+y+z_1$.
We have
\[
\frac{|V(T)|-|V(T')|}{|V(G)|-|V(G')|} = \frac{2}{4}.
\]

If $m = 2$,
then assume, without loss of generality, that each $z_i$
is adjacent to the corresponding $x_i$;
that is, $N(z_1) = \{x_1,y\}$,
and $N(z_2) = \{x_2,y\}$.
Delete $z_1$ and $z_2$, to obtain $G'$,
and apply the induction hypothesis to obtain $T'$.

We may assume that $y\in T'$.
If it is not, then we can add $y$ to $T'$,
removing one element of $X$ from $T'$ if $T'$ meets $X$,
to obtain a new $T'$ that contains $y$.
Note that now $T'$ contains at most $1$ vertex of $X$.

Let $T = T' - y + z_1 + z_2$.
Then
\[
\frac{|V(T)|-|V(T')|}{|V(G)|-|V(G')|} = \frac{2-1}{2} = \frac{2}{4}.
\]

This completes the proof of Lemma~\ref{L:d1k2}.\ggcendpf\end{proof}

The remaining case of Theorem~\ref{Th:d1-nice}
is that in which $k=3$.
For this case, we make use of partial vertices,
as in Lemma~\ref{L:if-full},
along with a new kind of special vertex,
which we call a ``loner''.
A \localdefterm{loner vertex} is a simplicial vertex
with degree at most $2$ in $G$;
if a loner lies in our induced forest,
then no neighbor of this loner lies in the forest (thus the name).
We denote the set of loner vertices by $Q$.

The $k=3$ case of Theorem~\ref{Th:d1-nice}
follows from the lemma below,
by letting $P$ and $Q$ be empty.

\begin{lemma} \label{L:d1k3}
Let $G$ be a graph with order $n$
and treewidth at most $3$.
Let $P$, $Q$ be disjoint subsets of $V(G)$,
so that each vertex in $P$ has degree at most $1$ in $G$,
each vertex in $Q$ is simplicial and has degree at most $2$ in $G$,
and $P\cup Q$ is an independent set in $G$.
Let each vertex of $P$ have weight $1/3$,
and let each other vertex of $G$, including those in $Q$, have weight $1$.
Then there exists a set $U \subseteq V(G)$,
such that all of the following hold.
\enumromanparen % Labels (i), (ii), etc.
\begin{enumerate}
\item $G[U]$ is a forest of maximum degree at most $1$.
\item $P \subseteq U$.
\item Each vertex in $Q \cap U$ has no neighbors in $G[U]$.
\item $w(U) \ge \frac{2}{5}\,w(G) = r_{3,1}\cdot w(G)$.
\end{enumerate}
\end{lemma}

\begin{proof}
Let $G$, $n$, $P$, $Q$, and the vertex weights
be as in the statement of the lemma.
A vertex of weight $1/3$ is a \localdefterm{partial vertex}.
A vertex having the restriction that, if it lies in $U$,
then no neighbor lies in $U$, is a \localdefterm{loner vertex}.
Thus, sets $P$ and $Q$ contain the partial and loner vertices
of $G$, respectively.
Partial and loner vertices are \localdefterm{special};
other vertices are \localdefterm{full}.

We proceed by induction, first, on the weight of $G$,
and second---for graphs of equal weight---on the number of full vertices.

\runinhead{Simple Cases---}First, we deal with some simple base cases
and reductions.

If some loner $u$ in $G$ has degree at most $1$,
then remove $u$ and its neighbor, if any, from $G$,
to obtain $G'$.
Apply the induction hypothesis to obtain $U'$,
and let $U = U' + u$.
Then
\[
\frac{w(U)-w(U')}{w(G)-w(G')}
 \ge \frac{1}{2} > \frac{2}{5}.
\]

If $2$ special vertices have intersecting neighborhoods,
then delete these specials and their neighborhoods
(of $1$, $2$, or $3$ full vertices total), %not 0; G is connected
to obtain $G'$.  (See Figure~\ref{F:new2} for possibilities.)
Apply the induction hypothesis to obtain $U'$,
and let $U$ be $U'$ plus the $2$ deleted specials.
If both specials are partial, then
the fraction $[w(U)-w(U')]/[w(G)-w(G')]$
is $(2/3)/(1+2/3) = 2/5$.
If one is a partial vertex and one is a loner,
then the fraction is $(1/3 + 1)/(2 + 1/3 + 1) = 2/5$.
If both specials are loners,
then the fraction is $2/5$ if the neighborhoods have
exactly $1$ vertex in common,
and $2/4$ if they have $2$ vertices in common---at least $2/5$
in either case.


\begin{figure}[ht]
\begin{center}
\begin{tabular}{ccccccc}
\begin{pspicture}(1.4,1.2)(3.6,2.8)
\definecolor{lonergray}{gray}{0.75}
\pslinewidth 0.5pt
  \psline(2,1.2)(2.5,2.5)(3,1.2)
  \psdot[dotsize=4pt 2](2.5,2.5) %x2
  \psdot[dotstyle=Bo,dotsize=4pt 2](2,1.2) %y
  \psdot[dotstyle=Bo,dotsize=4pt 2](3,1.2) %y
  \psarc[linestyle=dashed,dash=6pt 4pt](2.5,4.5){2}{240}{270}
  \psarc[linestyle=dashed,dash=6pt 4pt](2.5,4.5){2}{270}{300}
\end{pspicture}
&\quad &
\begin{pspicture}(0.9,1.2)(4.1,2.8)
\definecolor{lonergray}{gray}{0.75}
\pslinewidth 0.5pt
  \psline(1.5,1.2)(2,2.5)(2.5,1.2)(3,2.5)(2,2.5)
  \psdot[dotsize=4pt 2](2,2.5) %x1
  \psdot[dotsize=4pt 2](3,2.5) %x2
  \psdot[dotstyle=Bsquare,fillcolor=lonergray,dotsize=4pt 2](2.5,1.2) %y
  \psdot[dotstyle=Bo,dotsize=4pt 2](1.5,1.2) %y
  \psarc[linestyle=dashed,dash=6pt 4pt](2,4.5){2}{240}{270}
  \psarc[linestyle=dashed,dash=6pt 4pt](3,4.5){2}{270}{300}
\end{pspicture}
&\quad &
\begin{pspicture}(0.4,1.2)(4.5,2.8)
\definecolor{lonergray}{gray}{0.75}
\pslinewidth 0.5pt
  \psline(1.5,2.5)(2,1.2)(2.5,2.5)(3,1.2)(3.5,2.5)(1.5,2.5)
  \psdot[dotsize=4pt 2](1.5,2.5) %x1
  \psdot[dotsize=4pt 2](2.5,2.5) %x2
  \psdot[dotsize=4pt 2](3.5,2.5) %x3
  \psdot[dotstyle=Bsquare,fillcolor=lonergray,dotsize=4pt 2](2,1.2) %y
  \psdot[dotstyle=Bsquare,fillcolor=lonergray,dotsize=4pt 2](3,1.2) %y
  \psarc[linestyle=dashed,dash=6pt 4pt](1.5,4.5){2}{240}{270}
  \psarc[linestyle=dashed,dash=6pt 4pt](3.5,4.5){2}{270}{300}
\end{pspicture}
&\quad &
\begin{pspicture}(0.9,1.2)(4.1,2.8)
\definecolor{lonergray}{gray}{0.75}
\pslinewidth 0.5pt
  \psline(3,2.5)(2,1.2)(2,2.5)(3,1.2)(3,2.5)(2,2.5)
  \psdot[dotsize=4pt 2](2,2.5) %x1
  \psdot[dotsize=4pt 2](3,2.5) %x2
  \psdot[dotstyle=Bsquare,fillcolor=lonergray,dotsize=4pt 2](2,1.2) %y
  \psdot[dotstyle=Bsquare,fillcolor=lonergray,dotsize=4pt 2](3,1.2) %y
  \psarc[linestyle=dashed,dash=6pt 4pt](2,4.5){2}{240}{270}
  \psarc[linestyle=dashed,dash=6pt 4pt](3,4.5){2}{270}{300}
\end{pspicture}
\end{tabular}
\caption{Special vertices with intersecting neighborhoods.
Loners are gray squares.}
\label{F:new2}
\end{center}
\end{figure}

\medskip

Henceforth, we assume
that each loner in $G$ has degree $2$,
and
that no full vertex is adjacent to more than $1$ special.

\medskip

Suppose that there are at most $3$ full vertices.
If there are no full vertices, then let $U = V(G)$.
If there are no special vertices, %and $n=3$,
then let $U$ contain $\min\{2,n\}$ vertices of $G$.
If there are partial vertices but no loners,
then let $U$ be all the partial vertices, together with $1$ full vertex.
Otherwise,
there is a loner, and so there are either $2$ or $3$ full vertices,
and possibly $1$ partial vertex if there are $3$ full vertices.
Let $U$ be the two neighbors of the loner, plus the partial vertex,
if there is one.
In each case, $U$ has the proper structure and at least the required weight.

\medskip

Henceforth, we assume that $G$ has at least $4$ full vertices.
Further, we may assume that $G$ is connected
and $G-P-Q$ is a $3$-tree;
otherwise, add edges until these are true.

\runinhead{A Simplicial Vertex---}Now consider a vertex $z$
that is simplicial in $G-P-Q$.
Let $X=\{x_1,x_2,x_3\}$ be the neighborhood of $z$ in $G-P-Q$.

Suppose that $z$ has a loner neighbor $u$.
Without loss of generality, say the other neighbor of $u$ is $x_1$.
Remove $z$ and $u$ and add a new partial vertex $c$ adjacent to $x_1$,
to obtain $G'$.
Apply the induction hypothesis to obtain $U'$.
If $x_1\not\in U'$, then we may let $U=U'-c+u$.
If $x_1\in U'$, then, noting that $c\in U'$,
we see that $x_2$ and $x_3$ cannot lie in $U'$;
let $U= U'-c+z$.
In either case,
\[
\frac{w(U)-w(U')}{w(G)-w(G')}
 = \frac{1-\frac{1}{3}}{2-\frac{1}{3}} = \frac{2}{5}.
\]

%Hence we may assume that $z$ is not adjacent to any loner.

Now suppose that $z$ is not adjacent to any special.
Remove $z$ and add three partial vertices,
one adjacent to each element of $X$,
to obtain $G'$.
(See Figure~\ref{F:new3}.)
This does not change the weight of
the graph, but it does reduce the number of full vertices.
Apply the induction hypothesis to obtain $U'$.
Note that $|X\cap U'|\le 1$.
Let $U$ be $U'+z$ minus the three added partial vertices.
Since $w(G) = w(G')$ and $w(U) = w(U')$,
the weight requirement is satisfied.

\begin{figure}[t]
\begin{center}
\begin{tabular}{ccc}
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
\begin{pspicture}(0.85,1.3)(4.15,3.76)
  \psellipse(2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psdot[dotsize=4pt 2](1.7,3.2)\rput(1.8,3.4){$x_1$}
  \psdot[dotsize=4pt 2](3.3,3.2)\rput(3.4,3.4){$x_2$}
  \psdot[dotsize=4pt 2](2.5,2.6)\rput(2.5,2.9){$x_3$}
  \psdot[dotsize=4pt 2](2.5,1.5)\rput(2.2,1.3){$z$}
  \psline(1.7,3.2)(3.3,3.2)(2.5,2.6)(1.7,3.2)(2.5,1.5)(3.3,3.2)
  \psline(2.5,2.6)(2.5,1.5)
\end{pspicture}
& \qquad\qquad &
\definecolor{mygray}{gray}{0.90}
\pslinewidth 0.5pt
\begin{pspicture}(0.7,1.3)(4.3,3.76)
  \psellipse(2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psdot[dotsize=4pt 2](1.7,3.2)\rput(1.8,3.4){$x_1$}
  \psdot[dotsize=4pt 2](3.3,3.2)\rput(3.4,3.4){$x_2$}
  \psdot[dotsize=4pt 2](2.5,2.6)\rput(2.5,2.9){$x_3$}
  \psline(2.5,2.6)(1.7,3.2)(3.3,3.2)(2.5,2.6)(2.5,1.5)
%  \pscurve(2.5,1.5)(1.7,1.73)(0.7,1.7) %y - left of y
  \psline(1.7,3.2)(0.7,1.7)
%  \pscurve(2.5,1.5)(3.3,1.73)(4.3,1.7) %y - med right of y
  \psline(3.3,3.2)(4.3,1.7)%(2.5,2.6)
  \psdot[dotstyle=Bo,dotsize=4pt 2](0.7,1.7) %left of y
  \psdot[dotstyle=Bo,dotsize=4pt 2](4.3,1.7) %right of y
  \psdot[dotstyle=Bo,dotsize=4pt 2](2.5,1.5)%\rput(2.1,1.3){$z$}
\end{pspicture}
\end{tabular}
\caption{When a simplicial vertex $z$ is not adjacent to any special
(before and after).}
\label{F:new3}
\end{center}
\end{figure}

\medskip

Henceforth, we assume that each vertex that is simplicial in $G-P-Q$
is adjacent to exactly one partial vertex and no loners.

\medskip

%This case could be extended to $X'$ such that $|X\cap X'|\ge 2$,
%but it doesn't help, I think.
If there is a vertex $z'\ne z$ that is simplicial in $G-P-Q$
and whose neighborhood in $G-P-Q$ is $X$
(the neighborhood of $z$),
then remove $X$, $z$, $z'$, and their $2$ partial neighbors,
to obtain $G'$.
Apply the induction hypothesis to obtain $U'$,
and let $U$ be $U'$ plus $z$, $z'$, and their $2$ partial neighbors.
Then
\[
\frac{w(U)-w(U')}{w(G)-w(G')}
 = \frac{2+\frac{2}{3}}{5+\frac{2}{3}} > \frac{2}{5}.
\]

\medskip

Henceforth, we assume that no two vertices that are simplicial in
$G-P-Q$ have the same neighborhood in $G-P-Q$.

\medskip

Suppose there is a loner $u$ adjacent to an element of $X$;
say $N(u)=\{x_1,v\}$,
where $v$ may or may not lie in $X$.
(See Figure~\ref{F:new4}.)
Remove $u$, $x_1$, $v$,
and the partial vertex adjacent to $z$,
and make $z$ into a loner, to obtain $G'$.
Apply the induction hypothesis to obtain $U'$,
and let $U$ be $U'$ plus $u$ and the partial vertex adjacent to $z$.
Then
\[
\frac{w(U)-w(U')}{w(G)-w(G')}
 = \frac{1+\frac{1}{3}}{3+\frac{1}{3}} = \frac{2}{5}.
\]

\begin{figure}[ht]
\begin{center}
\begin{tabular}{ccc}
\begin{pspicture}(0.4,0.5)(4.15,4.6)
\definecolor{lonergray}{gray}{0.75}
\pslinewidth 0.5pt
%  \psframe[framearc=0.3](1.5,2.4)(2.8,4.2)
%  \rput(2.1,4.5){$N(u)$}
  \psframe[framearc=0.3](1.5,3.0)(2.3,4.2)
  \rput(1.9,4.5){$N(u)$}
  \psellipse(2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psdot[dotsize=4pt 2](1.7,3.2)\rput(2,3.4){$x_1$}
  \psdot[dotsize=4pt 2](3.3,3.2)%\rput(3.4,3.4){$x_2$}
  \psdot[dotsize=4pt 2](2.5,2.6)%\rput(2.5,2.9){$x_3$}
  \psdot[dotsize=4pt 2](2.5,1.5)\rput(2.2,1.3){$z$}
  \psline(1.7,3.2)(3.3,3.2)(2.5,2.6)(1.7,3.2)(2.5,1.5)(3.3,3.2)
  \psline(2.5,2.6)(2.5,1.5)
  \psline(1.7,3.2)(0.7,1.7)
  \psline(1.7,3.2)(1.7,4)(0.7,1.7)
  \psdot[dotstyle=Bsquare,fillcolor=lonergray,dotsize=4pt 2](0.7,1.7)
  \rput(0.4,1.4){$u$}
  \psdot[dotsize=4pt 2](1.7,4)
  \rput(2,4){$v$}
%below y:
  \psline(2.5,1.5)(2.5,0.5)
  \psdots[dotstyle=Bo,dotsize=4pt 2](2.5,0.5)
\end{pspicture}
& \qquad\qquad &
\begin{pspicture}(0.4,0.5)(4.15,4.6)
\definecolor{lonergray}{gray}{0.75}
\pslinewidth 0.5pt
%  \psframe[framearc=0.3](1.5,2.4)(2.8,4.2)
%  \rput(2.1,4.5){$N(u)$}
%  \psframe[framearc=0.3](1.5,3.0)(2.3,4.2)
%  \rput(1.9,4.5){$N(u)$}
  \psframe[framearc=0.3](1.5,2.4)(2.8,3.8)
  \rput(2.1,4.1){$N(u)$}
  \psellipse(2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psdot[dotsize=4pt 2](1.7,3.2)\rput(2,3.4){$x_1$}
  \psdot[dotsize=4pt 2](3.3,3.2)%\rput(3.4,3.4){$x_2$}
  \psdot[dotsize=4pt 2](2.5,2.6)\rput(2.5,2.9){$v$}
  \psdot[dotsize=4pt 2](2.5,1.5)\rput(2.2,1.3){$z$}
  \psline(1.7,3.2)(3.3,3.2)(2.5,2.6)(1.7,3.2)(2.5,1.5)(3.3,3.2)
  \psline(2.5,2.6)(2.5,1.5)
  \psline(1.7,3.2)(0.7,1.7)(2.5,2.6)
  \psdot[dotstyle=Bsquare,fillcolor=lonergray,dotsize=4pt 2](0.7,1.7)
  \rput(0.4,1.4){$u$}
%below y:
  \psline(2.5,1.5)(2.5,0.5)
  \psdots[dotstyle=Bo,dotsize=4pt 2](2.5,0.5)
\end{pspicture}
\\ \ \\
\begin{pspicture}(0.4,1.3)(4.15,4.6)
\definecolor{lonergray}{gray}{0.75}
\pslinewidth 0.5pt
  \psframe[framearc=0.3](1.5,3.0)(2.3,4.2)
  \rput(1.9,4.5){$N(u)$}
  \psellipse(2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psdot[dotsize=4pt 2](3.3,3.2)%\rput(3.4,3.4){$x_2$}
  \psdot[dotsize=4pt 2](2.5,2.6)%\rput(2.5,2.9){$x_3$}
  \psline(3.3,3.2)(2.5,2.6)
  \psline(2.5,2.6)(2.5,1.5)(3.3,3.2)
  \psdot[dotstyle=Bsquare,fillcolor=lonergray,dotsize=4pt 2](2.5,1.5)\rput(2.2,1.3){$z$}
\end{pspicture}
& \qquad\qquad &
\begin{pspicture}(0.4,1.3)(4.15,4.6)
\definecolor{lonergray}{gray}{0.75}
\pslinewidth 0.5pt
  \psframe[framearc=0.3](1.5,2.4)(2.8,3.8)
  \rput(2.1,4.1){$N(u)$}
  \psellipse(2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psdot[dotsize=4pt 2](3.3,3.2)%\rput(3.4,3.4){$x_2$}
  \psline(2.5,1.5)(3.3,3.2)
  \psdot[dotstyle=Bsquare,fillcolor=lonergray,dotsize=4pt 2](2.5,1.5)\rput(2.2,1.3){$z$}
\end{pspicture}
\end{tabular}
\caption{When there is a loner adjacent to $X$
(both possibilities, before and after).}
\label{F:new4}
\end{center}
\end{figure}

\medskip

Henceforth, we assume that no loner is adjacent to any neighbor
of a vertex that is simplicial in $G-P-Q$.

\runinhead{The Subgraph $G^*$---}Let $G^*$
be the graph obtained from $G-P-Q$ by removing
each vertex that is simplicial in $G-P-Q$.

If $V(G^*) = \varnothing$,
that is, if every vertex of $G-P-Q$ is simplicial in $G-P-Q$,
then $G$ is a complete graph on $4$ full vertices
with a partial vertex joined to each full vertex.
Let $U$ be all the partial vertices, together with one full vertex.
Then
\[
\frac{w(U)}{w(G)} = \frac{1+\frac{4}{3}}{4+\frac{4}{3}} > \frac{2}{5}.
\]

\medskip

Henceforth, we assume that $V(G^*) \ne \varnothing$,
and thus that $G-P-Q$ is not a complete graph.
Since $G-P-Q$ is a $3$-tree,
it must contain two nonadjacent simplicial vertices.
Two simplicial vertices of $G-P-Q$ cannot have the same neighborhood,
and so $|V(G^*)|>3$.
Thus, $G^*$ is a $3$-tree.

\begin{figure}[hb]
\begin{center}
\begin{pspicture}(0.85,0.3)(4.15,3.76)
\definecolor{mygray}{gray}{0.90}
\definecolor{lonergray}{gray}{0.75}
\pslinewidth 0.5pt
  \pspolygon[linewidth=0,fillstyle=solid,fillcolor=mygray](1.02,2.675)(3.98,2.675)(2.5,1.2)
  \psellipse[fillstyle=solid,fillcolor=mygray](2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psdot[dotsize=4pt 2](2.5,1.2)\rput(2.2,1.1){$y$}
  \psline(1.02,2.675)(2.5,1.2)(3.98,2.675) %y
  \psline(3.75,2.9)(5,2.7)(3.9,3) % $z1$:
  \psline(2.5,1.2)(5,2.7)
%  \psline(1.7,3.2)(5,1.7)(3.3,3.2) % $z2$:
%  \psdots(3,2.7)(3.6,2.7)
  \psline(3,2.7)(5,1.7)(3.6,2.7)
  \psline(2.5,1.2)(5,1.7)
  \psdots[dotsize=4pt 2](5,2.7)\rput(5,3){$z_1$}
  \psdots[dotsize=4pt 2](5,1.7)\rput(5,1.4){$z_m$}
  \psdots[dotsize=1pt 1](5,2)(5,2.2)(5,2.4)
  \psline(5,1.7)(5.9,1.7)
  \psline(5,2.7)(5.9,2.7)
  \psdots[dotstyle=Bo,dotsize=4pt 2](5.9,1.7)(5.9,2.7)
%below y:
  \psline[linestyle=dashed](2.5,1.2)(2.5,0.3)
  \psdots[dotstyle=Bo,dotsize=4pt 2](2.5,0.3)
  \rput(2.15,0.35){?}
  \end{pspicture}
\caption{Depth 2 Cases.}
\label{F:new5}
\end{center}
\end{figure}


%% NOTE: "depth" below is not quite used in a formal sense,
%% because we may not have a *lobe*; it might be the whole graph.
%% Thus, "depth" is not a formal statement, but just something intended
%% to help the reader understand what is going on.
\runinhead{Depth 2 Cases---}Let $y$ be a vertex
that is simplicial in $G^*$.
Let $X$ be the neighborhood of $y$ in $G^*$.
Since $G^*$ is a $3$-tree, we must have $|X|=3$.
Let $z_1,\dots,z_m$ be the full simplicial vertices in $G$
that are adjacent to $y$.
%% NOTE: Since the z_i's are simplicial in G-P-Q, they are not in G^*.
%% In particular, { z_1, ..., z_m } and X are disjoint.
Then each $z_i$ is adjacent to exactly one partial vertex,
$y$ may or may not be adjacent to a single partial vertex,
and no loner is adjacent to $y$ or to any of the $z_i$ vertices.
(See Figure~\ref{F:new5}.)

If $m\ge 2$, then remove $X$, $y$ and the $z_i$ vertices,
and their adjacent partial vertices,
to obtain $G'$.
Apply the induction hypothesis to obtain $U'$,
and let $U$ be $U'$ plus the $z_i$ vertices
and their adjacent partial vertices,
along with the partial vertex adjacent to $y$, if there is one.
Then
\begin{align*}
\frac{w(U)-w(U')}{w(G)-w(G')}
  &\ge \frac{m+m\cdot\frac{1}{3}}{4+m+m\cdot\frac{1}{3}}
    \quad&&\text{minimized when $y$ has no adjacent partial vertex}\\
  &\ge \frac{2+\frac{2}{3}}{6+\frac{2}{3}} = \frac{2}{5}.
    \quad&&\text{minimized when $m=2$}
\end{align*}

\medskip

It remains to prove the result when $m=1$.
Let $x_1,x_2$ be the neighbors of $z_1$ in $X$.
%% NOTE: There may also be an x_3, but we don't use it
(See Figure~\ref{F:new6}.)

\begin{figure}[ht]
\begin{center}
\begin{tabular}{ccc}
\begin{pspicture}(0.6,0.5)(5,3.76)
\definecolor{mygray}{gray}{0.90}
\definecolor{lonergray}{gray}{0.75}
\pslinewidth 0.5pt
  \psellipse(2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psdot[dotsize=4pt 2](1.7,3.2)\rput(1.8,3.4){$x_1$}
  \psdot[dotsize=4pt 2](3.3,3.2)\rput(3.4,3.4){$x_2$}
  \psdot[dotsize=4pt 2](2.5,2.6) %x_3
  \psdot[dotsize=4pt 2](2.5,1.5)\rput(2.2,1.3){$y$}
  \psline(1.7,3.2)(3.3,3.2)(2.5,1.5)(1.7,3.2)
  \psline(3.3,3.2)(2.5,2.6)(1.7,3.2)
  \psline(2.5,2.6)(2.5,1.5)
  \psline(1.7,3.2)(5,2.7)(3.3,3.2) % $z$:
  \psline(2.5,1.5)(5,2.7)
  \psdots[dotsize=4pt 2](5,2.7)\rput(5,3){$z_1$}
  \psline(5,2.7)(5,1.7) % z's partial neighbor
  \psdots[dotstyle=Bo,dotsize=4pt 2](5,1.7)
%below y:
%  \psline(2.5,1.5)(2.5,0.5)
%  \psdots[dotstyle=Bo,dotsize=4pt 2](2.5,0.5)
\end{pspicture}
& \quad\ &
\begin{pspicture}(0.6,0.5)(5,3.76)
\definecolor{mygray}{gray}{0.90}
\definecolor{lonergray}{gray}{0.75}
\pslinewidth 0.5pt
  \psellipse(2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psdot[dotsize=4pt 2](1.7,3.2)\rput(1.8,3.4){$x_1$}
  \psdot[dotsize=4pt 2](3.3,3.2)\rput(3.4,3.4){$x_2$}
  \psdot[dotsize=4pt 2](2.5,2.6) %x_3
  \psdot[dotsize=4pt 2](2.5,1.5)\rput(2.2,1.3){$y$}
  \psline(1.7,3.2)(3.3,3.2)(2.5,1.5)(1.7,3.2)
  \psline(3.3,3.2)(2.5,2.6)(1.7,3.2)
  \psline(2.5,2.6)(2.5,1.5)
  \psline(1.7,3.2)(5,2.7)(3.3,3.2) % $z$:
  \psline(2.5,1.5)(5,2.7)
  \psdots[dotsize=4pt 2](5,2.7)\rput(5,3){$z_1$}
  \psline(5,2.7)(5,1.7) % z's partial neighbor
  \psdots[dotstyle=Bo,dotsize=4pt 2](5,1.7)
%below y:
  \psline(2.5,1.5)(2.5,0.5)
  \psdots[dotstyle=Bo,dotsize=4pt 2](2.5,0.5)
\end{pspicture}
\\ \ \\
\begin{pspicture}(0.6,1.5)(5,3.76)
\definecolor{mygray}{gray}{0.90}
\definecolor{lonergray}{gray}{0.75}
\pslinewidth 0.5pt
  \psellipse(2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psdot[dotsize=4pt 2](1.7,3.2)\rput(1.8,3.4){$x_1$}
  \psdot[dotsize=4pt 2](3.3,3.2)\rput(3.4,3.4){$x_2$}
  \psdot[dotsize=4pt 2](2.5,2.6) %x_3
  \psline(1.7,3.2)(3.3,3.2)
  \psline(3.3,3.2)(2.5,2.6)(1.7,3.2)
  \psline(1.7,3.2)(1.7,1.5)
  \psline(3.3,3.2)(3.3,1.5)
  \psdots[dotstyle=Bo,dotsize=4pt 2](1.7,1.5)(3.3,1.5)
%  \psline(1.7,3.2)(5,2.7)(3.3,3.2) % $z$:
%  \psline(2.5,1.5)(5,2.7)
%  \psdots[dotsize=4pt 2](5,2.7)\rput(5,3){$z_1$}
%  \psline(5,2.7)(5,1.7) % z's partial neighbor
%  \psdots[dotstyle=Bo,dotsize=4pt 2](5,1.7)
\end{pspicture}
& \quad\ &
\begin{pspicture}(0.6,1.5)(5,3.76)
\definecolor{mygray}{gray}{0.90}
\definecolor{lonergray}{gray}{0.75}
\pslinewidth 0.5pt
  \psellipse(2.5,3)(1.65,0.76)
  \rput(0.6,3.3){$X$}
  \psdot[dotsize=4pt 2](1.7,3.2)\rput(1.8,3.4){$x_1$}
  \psdot[dotsize=4pt 2](3.3,3.2)\rput(3.4,3.4){$x_2$}
  \psdot[dotsize=4pt 2](2.5,2.6) %x_3
  \psline(1.7,3.2)(3.3,3.2)
  \psline(3.3,3.2)(2.5,2.6)(1.7,3.2)
  \psline(1.7,3.2)(5,2.7)(3.3,3.2) % $z$:
  \psdots[dotstyle=Bsquare,fillcolor=lonergray,dotsize=4pt 2](5,2.7)\rput(5,3){$z_1$}
\end{pspicture}
\end{tabular}
\caption{When $m=1$ and $y$ is not (left) or is (right)
adjacent to a partial vertex (before and after).}
\label{F:new6}
\end{center}
\end{figure}


If $y$ is not adjacent to a partial vertex,
then remove $z_1$, its neighboring partial vertex, and $y$,
and then add two new partial vertices adjacent to $x_1$, $x_2$, respectively,
to obtain $G'$.
Apply the induction hypothesis to obtain $U'$.
At most one vertex of $X$ will lie in $U'$.
If $x_1$ or $x_2$ lies in $U'$,
then let $U$ be $U'$ minus the two added partial vertices,
plus $y$ and the removed partial vertex.
Otherwise,
let $U$ be $U'$ minus the two added partial vertices,
plus $z_1$ and the removed partial vertex.
In either case,
\[
\frac{w(U)-w(U')}{w(G)-w(G')}
 = \frac{-\frac{2}{3} + 1 + \frac{1}{3}}{-\frac{2}{3} + 2 + \frac{1}{3}}
 = \frac{2}{5}.
\]

If, on the other hand, $y$ is adjacent to a partial vertex,
then remove $y$ and the partial vertices adjacent to $y$ and $z_1$,
and make $z_1$ a loner,
to obtain $G'$.
Apply the induction hypothesis to obtain $U'$,
and let $U$ be $U'$ plus the removed partial vertices.
Then
\[
\frac{w(U)-w(U')}{w(G)-w(G')}
 = \frac{\frac{2}{3}}{1+\frac{2}{3}}
 = \frac{2}{5}.
\]

This completes the proof of Lemma~\ref{L:d1k3}.\ggcendpf\end{proof}

We have now proven Theorem~\ref{Th:d1-nice}.


\section{Graphs on Surfaces} \label{S:surf}

This research was initially motivated by two conjectures of the first author.
The first conjecture stated that, if $G$ is an outerplanar graph
of order $n$, then $f_2(G) > 4n/7$.
This conjecture was proven by the second author~\cite[Thm.~1]{Pel2004}.
Because outerplanar graphs have treewidth at most $2$,
and $r_{2,2} = 4/7$,
this result is implied by our more general Theorem~\ref{Th:if-nice}.

The second conjecture is a similar one involving planar graphs.
It remains open.

\begin{conjecture} \label{J:planar-lf}
Let $G$ be a planar graph of order $n\ge 1$.
Then $f_2(G) > 4n/9$.\ggcnopf\end{conjecture}

While we do not know whether the above conjecture holds,
we do know that, if it does,
then the fraction $4/9$ is best possible,
because of the following observation.

\begin{observation}
If $k=3$, then, for all $n\ge 1$ and $d\ge 2$,
the graph $G(k,d,n)$, from Example~\ref{Ex:sharp},
is planar.\ggcnopf\end{observation}

\begin{figure}[ht]
\begin{center}
\psfrag{x10}{$x_{1,0}$}
\psfrag{x11}{$x_{1,1}$}
\psfrag{x12}{$x_{1,2}$}
\psfrag{x13}{$x_{1,3}$}
\psfrag{x21}{$x_{2,1}$}
\psfrag{x22}{$x_{2,2}$}
\psfrag{x23}{$x_{2,3}$}
\psfrag{x31}{$x_{3,1}$}
\psfrag{y13}{$y_{1,3}$}
\psfrag{y23}{$y_{2,3}$}
\psfrag{z0}{$z_{0}$}
\psfrag{z1}{$z_{1}$}
\psfrag{z2}{$z_{2}$}
\includegraphics{sharp-planar.eps}
\caption{$G(k,d,n)$ with $n=37, k=3, d=3$
(thus $a=2, h=6, b=1$, and $c=2$),
drawn without crossing edges to illustrate the fact that it is planar.
Edges within each $S_{i,j}$ are shown in bold.}
\label{F:sharp-planar}
\end{center}
\end{figure}

(See Figure~\ref{F:sharp-planar} for an illustration.)
By this observation, we can use the graphs $G(3,d,n)$,
along with Proposition~\ref{P:examplemax},
to prove upper bounds for planar graphs.

A weaker version of Conjecture~\ref{J:planar-lf},
in which ``$f_2(G) > 4n/9$'' is replaced by ``$f_2(G)\ge n/3$'',
is known to hold.
This follows from
a result proved independently by Poh~\cite{Poh1990}
and by Goddard~\cite{God1991}:
that every planar graph has
a (not necessarily proper) vertex $3$-coloring,
so that each color class induces a forest of maximum degree at most $2$
(a \localdefterm{linear forest}).
%I believe that Goddard's proof has an unfixable error.
In such a coloring, the largest color class induces
a linear forest with at least $n/3$ vertices.

While planar graphs can have
arbitrarily high treewidth
(this is well known, but nontrivial to prove;
see, for example, Diestel~\cite{Die2000}),
in many ways they are similar to graphs with treewidth at most $3$.
For example, the maximum number of edges in an $n$-vertex planar graph
is $3n-6$;
the same holds for $n$-vertex graphs of treewidth at most $3$.
Both classes have a maximum clique number of $4$;
indeed, the maximum order of a clique minor is $4$.
Our investigations suggest that
planar graphs also behave much like graphs of treewidth at most $3$
for the purpose of finding large induced forests.
If $k=3$, then $r_{k,d} = 2d/(4d+1)$.
We conjecture that this same fraction gives a lower bound for planar graphs.

\begin{conjecture} \label{J:planar-alld_b}
Let $d\ge 2$ be an integer.
If $G$ is a planar graph with order $n\ge 1$,
then
\[
f_d(G) > \frac{2dn}{4d+1} = r_{3,d}\cdot n.\ggcnopf
\]
\end{conjecture}

Note that Conjecture~\ref{J:planar-alld_b} generalizes
Conjecture~\ref{J:planar-lf},
since $2d/(4d+1) = 4/9$ when $d = 2$; that is, $r_{3,2} = 4/9$.
And as before, if the above conjecture is true,
then the fraction $2d/(4d+1)$ is best possible,
as shown by the graphs $G(k,d,n)$ from Example~\ref{Ex:sharp},
with $k=3$.

Conjecture~\ref{J:planar-alld_b}
would become false if we allowed $d=1$,
as shown by setting $G=K_{2,2,2}$ (the octahedron).
The largest induced forest with maximum degree at most $1$ in this graph
has $2$ vertices, while, when $d=1$ and $n=6$,
we have $2dn/(4d+1) = 12/5 > 2$.

Letting $d$ increase without bound,
the value of
$r_{3,d}$ approaches $1/2$.
Thus, Conjecture~\ref{J:planar-alld_b}
implies the Induced Forest Conjecture
of Albertson and Berman~\cite{AlBe1979}:
that every $n$-vertex planar graph contains an induced forest
with at least $n/2$ vertices.

If ``$n/2$'' is replaced by ``$2n/5$'',
then the resulting statement is known to hold.
This follows from a result of Borodin~\cite{Bor1976,Bor1979}:
that every planar graph has a proper vertex $5$-coloring,
so that the union of each pair of color classes induces a forest.
In such a coloring, the union of the two largest color classes induces
a forest with at least $2n/5$ vertices.

Note that proving only Conjecture~\ref{J:planar-lf}
would not suffice to verify the Induced Forest Conjecture.
However this would still improve on the $2n/5$ in the previous paragraph,
since $4/9 > 2/5$.

Lastly, we consider induced forests in graphs on other surfaces.
We ask whether the ratio $2d/(4d+1)$ works for any surface,
once a correction term is subtracted.

\begin{question} \label{Q:surf-strong}
Does there exist a function $\varphi$ so that,
if $d\ge 2$ is an integer
and $G$ is a graph of order $n$ that is embeddable on a surface $S$,
then
\[
f_d(G) \ge \frac{2d}{4d+1}\cdot\left[n - \varphi(S)\right]?\ggcnopf
\]
\end{question}

In particular, when $S$ is the torus,
does $\varphi(S) = 3$ work?

This idea of being able to remove a fixed number of
vertices from a graph embeddable on some surface,
in order to obtain a graph that ``acts planar'',
is not a new one.
In particular, Albertson~\cite{Alb1981} conjectured
that for each surface $S$ there is a constant $q(S)$,
so that for each graph $G$ embeddable on $S$,
a set of at most $q(S)$ vertices can be removed from $G$,
to obtain a $4$-colorable graph.

%\bigskip

%\runinhead{Acknowledgements---}The authors would like to thank John Gimbel
%and Chris Hartman for allowing us to include their result.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
The authors would like to thank John Gimbel
and Chris Hartman for allowing us to include their result.

\begin{thebibliography}{10}

\bibitem{Alb1981}
M.~O.~Albertson.
\newblock Open problem 2.
\newblock In {\em The Theory and Applications of Graphs}
(G.~Chartrand et al., eds.),
page~609.
Wiley, 1981.

\bibitem{AlBe1979}
M.~O.~Albertson and D.~Berman.
\newblock A conjecture on planar graphs.
\newblock In {\em Graph Theory and Related Topics}
(J.~A.~Bondy and U.~S.~R.~Murty, eds.),
page~357.
Academic Press, 1979.

\bibitem{ABT1976}
M.~Albertson, B.~Bollob\'as, and S.~Tucker.
\newblock The independence ratio and maximum degree of a graph.
\newblock In {\em Proceedings of the Seventh Southeastern Conference
  on Combinatorics, Graph Theory and Computing
(Louisiana State Univ., Baton Rouge, La., 1976)},
volume XVII of {\em Congress. Numer.},
pages 43--50.
Utilitas Mathematica, Winnipeg, Man., 1976.

\bibitem{AMT2001}
N.~Alon, D.~Mubayi, and R.~Thomas.
\newblock Large induced forests in sparse graphs.
\newblock  {\em J. Graph Theory},
38(3):113--123, 2001.

\bibitem{AW1987}
J.~Akiyama and M.~Watanabe.
\newblock Maximum induced forests of planar graphs,
\newblock {\em Graphs Combin.},
3(1):201--202, 1987.

\bibitem{BaBe2002}
S.~Bau and L.~W.~Beineke.
\newblock The decycling number of graphs,
\newblock {\em Australas. J. Combin.},
25:285--298, 2002.

\bibitem{Bod1998}
H.~L.~Bodlaender.
\newblock A partial $k$-arboretum of graphs with bounded treewidth.
\newblock {\em Theoret. Comput. Sci.},
209(1-2):1--45, 1998.

\bibitem{Bor1976}
O.~V.~Borodin.
\newblock A proof of B.~Gr\"unbaum's conjecture on the acyclic $5$-colorability
 of planar graphs (Russian).
\newblock {\em Dokl. Akad. Nauk SSSR},
231(1):18--20, 1976.

\bibitem{Bor1979}
O.~V.~Borodin.
\newblock On acyclic colorings of planar graphs.
\newblock {\em Discrete Math.},
25(3):211--236, 1979.

\bibitem{BDW2006}
P.~Bose, V.~Dujmovi\'c, and D.~R.~Wood.
\newblock Induced subgraphs of bounded degree and bounded treewidth.
\newblock {\em Contrib. Discrete Math.},
1(1):88--105, 2006.

\bibitem{CKK2002}
I.~Caragiannis, C.~Kaklamanis, and P.~Kanellopoulos.
\newblock New bounds on the size of the minimum feedback vertex set
  in meshes and butterflies.
\newblock {\em Inform. Process. Lett.},
83(5):275--280, 2002.

\bibitem{CGHmanu}
G.~G.~Chappell, J.~Gimbel, and C.~Hartman.
\newblock Generalized independence in graphs.
\newblock Manuscript.

\bibitem{Die2000}
R.~Diestel.
\newblock {\em Graph theory, 2nd ed.}
\newblock Graduate Texts in Mathematics, 173.
Springer-Verlag, New York, 2000.

\bibitem{Faj1978}
S.~Fajtlowicz.
\newblock On the size of independent sets in graphs,
\newblock In {\em Proceedings of the Ninth Southeastern Conference
  on Combinatorics, Graph Theory, and Computing
(Florida Atlantic Univ., Boca Raton, Fla., 1978)},
volume XXI of {\em Congress. Numer.},
pages 269--274.
Utilitas Mathematica, Winnipeg, Man., 1978.

\bibitem{FGR2002}
G.~Fertin, E.~Godard, and A.~Raspaud.
\newblock Minimum feedback vertex set and acyclic coloring.
\newblock {\em Inform. Process. Lett.}
84(3):131--139, 2002.
% NOTE: "Godard" is the correct spelling, according to MathSciNet

\bibitem{God1991}
W.~Goddard.
\newblock Acyclic colorings of planar graphs.
\newblock {\em Discrete Math.},
91(1):91--94, 1991.

\bibitem{HT2006}
C.~C.~Heckman and R.~Thomas.
\newblock Independent sets in triangle-free cubic planar graphs.
\newblock {\em J. Comb. Theory Ser. B},
96(2):253--275, 2006.

\bibitem{Hos1990}
K.~Hosono.
\newblock Induced forests in trees and outerplanar graphs.
\newblock {\em Proc. Fac. Sci. Tokai Univ.},
25:27--29, 1990.

\bibitem{Jon1990}
K.~F.~Jones.
\newblock Size and independendence in triangle-free graphs with maximum degree three.
\newblock {\em J. Graph Theory},
14(5):525--535, 1990.

\bibitem{LL1997}
S.~C.~Locke and F.~Lou.
\newblock Finding independent sets in $K_4$-free $4$-regular connected graphs.
\newblock {\em J. Combin. Theory Ser. B},
71(1):85--110, 1997.

\bibitem{Pel2004}
M.~J.~Pelsmajer.
\newblock Maximum induced linear forests in outerplanar graphs.
\newblock {\em Graphs Combin.},
20(1):121--129, 2004.

\bibitem{Poh1990}
K.~S.~Poh.
\newblock On the linear vertex-arboricity of a planar graph.
\newblock {\em J. Graph Theory},
14(1):73--75, 1990.

\bibitem{Ree1997}
B.~A.~Reed.
\newblock Tree width and tangles: a new connectivity measure and some applications.
\newblock In {\em Surveys in combinatorics, 1997 (London)},
volume 241 of {\em London Math. Soc. Lecture Note Ser.},
pages 87--162.
Cambridge Univ. Press, Cambridge, 1997.

\bibitem{Sal2006}
M.~R.~Salavatipour.
\newblock Large induced forests in triangle-free planar graphs.
\newblock {\em Graphs Combin.},
22(1):113--126, 2006.

\bibitem{Sta1979}
W.~Staton.
\newblock Some Ramsey-type numbers and the independence ratio.
\newblock {\em Trans. Amer. Math. Soc.},
256:353--370, 1979.

\bibitem{Wes2001}
D.~B.~West.
\newblock {\em Introduction to Graph Theory, 2nd ed.}
\newblock Prentice-Hall, Upper Saddle River, NJ, 2001.

\end{thebibliography}

\end{document}

