5
$\begingroup$

What can be the upper bound on the number of edges in a graph of $n$ vertices such that the graph does not have $K_4$ as a minor? Is there some relevant paper/book that I can look into it or it would be kind if some one can give intuition or some proof of some kind along with the bound.

$\endgroup$
18
$\begingroup$

I think $K_4$-minor-free graphs have at most $2n - 3$ edges for $n \geq 2$, and this is tight. Here's one way of looking at it.

It is well-known that the $K_4$-minor-free graphs are exactly the graphs of treewidth at most two, see http://en.wikipedia.org/wiki/Forbidden_graph_characterization . Standard theory on treewidth tells us that a graph of treewidth at most 2 is 2-degenerate (see http://en.wikipedia.org/wiki/Degeneracy_%28graph_theory%29 ), which means that all induced subgraphs have a vertex of degree at most two. So to count the number of edges in a $K_4$-minor-free graph, we can do the following: we find a vertex of degree at most two, and delete it. We remove one vertex, and at most two edges. What we're left with is still $K_4$-minor-free (since minor-freeness is preserved when deleting vertices), so if the graph is not yet empty then we know it is 2-degenerate, and has another vertex of degree at most two. If we keep removing vertices of degree at most two then we delete $n$ vertices until the graph is empty, and for each removed vertex we delete at most two edges. Hence the number of edges is at most $2n$.

Now observe that when removing the second-to-last vertex, there are only two vertices left so there can be only one edge that is removed in that step. Similarly, when we've removed all but one of the vertices then there can be no edges left, so in the last step we don't remove any edges. This shows that the number of edges is at most $2n - 3$ because we save 1 in the second-to-last step, and 2 in the last step.

To see that this is tight, start with a graph on two vertices and one edge. Now repeatedly select two adjacent vertices, and add a new vertex with edges to the selected two. The constructed graph will have treewidth two (since it is a 2-tree, see http://en.wikipedia.org/wiki/K-tree ) and will therefore be $K_4$-minor-free, and the number of edges you build in this way is $2n-3$.

$\endgroup$
2
$\begingroup$

In general, the number of edges in a $K_m$-minor-free graph is bounded linearly in the number of vertices. The first non-trivial case is $m=3$, i.e. forests where $|E|\le|V|-1$. Here, I'll show that $|E|\leq(2^{m-2}-1)|V|$.

Let $G$ be a minimal counterexample. Select any vertex $v$. Let $H$ be the subgraph induced by the neighbours of $v$. The idea is to find a vertex $u$ in $H$ whose degree in $H$ is small, so that contracting the edge $uv$ destroys a small number of edges and gives a smaller counterexample.

Note that $H$ contains no $K_{m-1}$ minor and is not a counterexample, so we may select a vertex $u$ in $H$ with $deg_H(u)\le 2^{m-2}-2$. Contracting the edge $uv$ then decreases $|E|$ by at most $2^{m-2} - 1$ and decreases $|V|$ by one, so we have a smaller counterexample.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.