Relation between independence number and maximum order of induced tree?

Question

For a graph $G$, let $t(G)$ be the maximum order of a vertex-subset that induces a tree in $G$, and $\alpha(G)$ be the independence number of $G$ (maximum size of independent set in $G$).

I find a relation states without proof that $$t(G)\le 2\alpha(G)$$ and want to know why.

My feeling is that take a maximum independent set $I$, and a neighbor of each of them (if any), then their union has size less than $2\alpha(G)$. But why the induced graph on them must contain a cycle or a forest with two components?

Answer 1

Given any subtree $T$ of $G$, I will show how to construct an independent set $I$ from $T$ with the property that $|T|\leq 2|I|$.

The construction is iterative. Start by letting $I_0$ be the leaf (i.e. degree $1$) vertices of $T$, and for all $k\geq 0$ let $I_{k+1}$ be the leaf vertices of $T\setminus I_k$. Let $J_k=I_{2k}$ except when $I_{2k}$ is an edge, in which case we let $J_k$ be one of the two vertices of $I_{2k}$ chosen arbitrarily. This is done to ensure that $J_k$ is an independent set, since the only way for a connected graph to have adjacent leaf vertices is if the graph is an edge.

Set $I=\cup_{k\geq 0}J_k$. We use the following two properties to finish the proof:

1. $I$ is an independent set
2. $|J_k|\geq |I_{2k+1}|$ for all $k\geq 0$

Property (1) can be seen using a simple proof by contradiction - adjacent vertices of $I$ would have to belong to distinct $J_i,J_j$ but this is impossible by construction. Property (2) follows from the existence of the surjection from $I_{2k}$ to $I_{2k+1}$ given by sending each vertex in $I_{2k}$ to its unique neighbor in $I_{2k+1}$, together with the observation that if $J_k\not=I_{2k}$ then $I_{2k+1}$ is empty. Thus, $$ |I|=\sum_{k\geq 0}|J_{k}|\geq \sum_{k\geq 0}|I_{2k+1}|=|T\setminus I|, $$ showing that $2|I|\geq |T|$ and thus we have found the desired independent set.

Finally, apply this construction to any tree with $|T|=t(G)$ to obtain an independent set $I$ satisfying $$ t(G)\leq 2I\leq 2\alpha(G), $$ with the latter inequality coming from the definition of $\alpha(G)$.

Answer 2

Let $T$ be an induced tree in $G$ of maximum number of vertices (so $v_T=t(G)$), and we are going to construct an independent set $I$ in $T$ so that $|I|\ge v_T/2$, which implies $\alpha(G)\ge t(G)/2$.

Algorithm of finding such an independent set

Set $T_0:=T$. Set $U_0:=V(T_0)$, $L_0=\emptyset$, $I_0=\emptyset$ as "unlabeled", "labeled", and independent vertex-sets, respectively. We will always keep $T_i$ an induced subtree of $T$ and the union of disjoint sets $U_i$, $L_i$, and $I_i$ equal to $V(T)$ during the algorithm.

At step $i\ge 0$, picking a unlabeled leaf $v$, if any, of the tree $T_i$ (recall a tree contains at least 1 leaf, i.e., a degree 1 vertex), set $$I_{i+1}:=I_i\cup\{v\},$$ $$T_{i+1}:=T_i\setminus \{v\},$$ and $$U_{i+1}:=U_i\setminus\{u,v\},$$ $$L_{i+1}:=L_{i}\cup\{u\},$$ where $u$ is the unique vertex in $T_i$ adjacent to $v$ if any, otherwise $U_{i+1}:=U_i\setminus\{v\}$ and $L_{i+1}:=L_i$.

If there is no such unlabeled leaves, we set $$I_{i+1}:=I_i,$$ $$U_{i+1}:=U_i,$$ $$L_{i+1}:=L_{i},$$ $$T_{i+1}:=T_i\setminus \{\text{labeled leaves in $T_i$}\}.$$

Then we go to next step. And the algorithm terminates if $U_k$ becomes empty.

It is easy to check $T_i,U_i,L_i,I_i$ satisfy the mentioned properties.

As all vertex of $T$ fall in the final independent set or labeled set, and at each step, the number of vertex included in $L_i$ is no more than that in $I_i$ (with the notations in the algorithm, note that the vertex $u$ can already be in the labeled set, or in the final step, the tree is an isolated vertex.). Therefore $$|I_m|\ge |L_m|\ge v_T/2$$ after final step $m$.

Answer 3

More strongly, if $b(G)$ is the maximum order of any induced bipartite subgraph in $G$, then $b(G) \le 2\alpha(G)$.

(If $H$ is an induced bipartite subgraph of order $b(G)$, and $A \cup B$ is the bipartition of $V(H)$, then either $|A| \ge \frac12 b(G)$ or $|B| \ge \frac12 b(G)$, and both $A$ and $B$ are independent sets in $G$. Therefore $\alpha(G) \ge \frac12 b(G)$.)

Since a tree is just one specific kind of bipartite graph, $t(G) \le b(G) \le 2\alpha(G)$, as desired.