Independence number of a subdivision of a graph Is it true in general that the independence number of a subdivision of a graph $G$ that has size $m$ and order $n$ is equal to $m$ ? Except for a known class of graphs ,that's , trees.
 A: It's true for non-tree connected graphs, at least. So in general, the independence number of the subdivision $S(G)$ will be $m+k$, where $k$ is the number of tree components of $G$.
It's useful to know that in a tree $T$, we can pick an arbitrary vertex $r$ to be the root, and then match each edge of $T$ with one of its endpoints so that every vertex except $r$ is covered. To do this, just match each vertex $v$ with the first edge on the unique path from $v$ to $r$. In the subdivision $S(T)$, this gives us a vertex matching of size $m$ with only $r$ left unmatched; since the independent set can use at most one vertex from each matching, the independence number of $T$ is at most $m+1$, which we can achieve by choosing all of the vertices corresponding to vertices of $T$.
In a component $C$ with cycles, we can do a similar thing. Pick an edge $vw$ whose removal leaves $C$ connected, and let $T$ be a spanning tree of $C - vw$. We can find an edge-to-endpoint matching in $T$ that leaves out $v$, which gives us a matching of size $n-1$ in $S(C)$; by matching $v$ with $vw$, this increases to a matching of size $n$ that covers all the vertices of $C$, and $n$ of the vertices corresponding to edges of $C$. (Leaving $m-n$ vertices of $S(C)$ unmatched.)
Now it's easy to see that $S(C)$ has independence number at most $m$. From this matching, we can pick at most $n$ independent vertices, and at best we can pick all $m-n$ of the remaining vertices of $S(C)$.
A: Let $G$ be a connected graph that is not a tree (that is, $|E(G)| \geq |V(G)|$), and let $G^*$ be the graph obtained by subdividing every edge of $G$. Let $I$ be an independent set of $G^*$ of order $\alpha(G^*)$ with the least number of vertices of $V(G)$. 
If $I$ has no vertices in $V(G)$, then $|I| = \alpha(G^*) = |E(G)|$. If $I$ has no vertices in $V(G^*) \backslash V(G)$, then $I = V(G)$, but $V(G^*) \backslash V(G)$ is an independent set of order $|E(G)| \geq |V(G)|$, since $G$ is not a tree, and thus $|I| = \alpha(G^*) = |V(G)| = |E(G)|$.
Now we may assume $I$ has at least one vertex $u \in V(G)$ and at least one vertex $v \in V(G^*) \backslash V(G)$. Let $P$ be a path from $u$ to $v$ in $G^*$. The vertices of $P$ (or any path in $G^*$) alternate between vertices of $V(G)$ and vertices of $V(G^*) \backslash V(G)$. Let $x$ be the vertex in $I \cap V(G)$ nearest to $v$ on the path. Then the neighbor of $x$ nearer to $v$ on the path, call it $y$, is a vertex of $V(G^*) \backslash V(G)$, and $I-x+y$ is an independent set of the same order as $I$ with fewer vertices in $V(G)$, a contradiction to the definition of $I$. 
So for a connected graph $G$ that is not a tree, $\alpha(G^*)=|E(G)|$.
