<p>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|$.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-06-10T02:33:54.493Z
2011-06-10T02:33:54.493Z
Perce
<p>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. </p>

<p>It is well-known that the $K_4$-minor-free graphs are exactly the graphs of treewidth at most two, see <a href="http://en.wikipedia.org/wiki/Forbidden_graph_characterization" rel="nofollow">http://en.wikipedia.org/wiki/Forbidden_graph_characterization</a> . Standard theory on treewidth tells us that a graph of treewidth at most 2 is 2-degenerate (see <a href="http://en.wikipedia.org/wiki/Degeneracy_%28graph_theory%29" rel="nofollow">http://en.wikipedia.org/wiki/Degeneracy_%28graph_theory%29</a> ), 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$. </p>

<p>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.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/K-tree" rel="nofollow">http://en.wikipedia.org/wiki/K-tree</a> ) and will therefore be $K_4$-minor-free, and the number of edges you build in this way is $2n-3$.</p>

CC BY-SA 3.0
2011-06-08T15:37:17.833Z
They are also known as the [series-parallel graphs](http://en.wikipedia.org/wiki/Series-parallel_graph).
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-06-08T11:51:33.370Z
2011-06-08T13:31:39.647Z
2011-06-08T13:31:39.647Z
Bart Jansen
<p>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.</p>

CC BY-SA 3.0
2011-06-08T11:41:53.030Z
Have a look at http://www.graphclasses.org/classes/gc_309.html A minimal superclass is a partial 3-tree; with this you should be able to find some bound.
Marcus Ritt
<graph-theory><co.combinatorics><upper-bounds>
Number of edges in $K_4$-free graphs
singhsumit
# Number of edges in $K_4$-free graphs

(Asked by: username_0 on 2011-06-08)

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.

**Tags:** graph-theory, co.combinatorics, upper-bounds
> **Comments:**
> **username_1**: Have a look at http://www.graphclasses.org/classes/gc_309.html A minimal superclass is a partial 3-tree; with this you should be able to find some bound.  

---

## 2 answers

### Answer by username_3 on 2011-06-08. Score: 18 | Accepted answer

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$.

> **Comments:**
> **username_4**: They are also known as the [series-parallel graphs](http://en.wikipedia.org/wiki/Series-parallel_graph).  

---

### Answer by username_2 on 2011-06-10. Score: 3

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.


---

