-1
$\begingroup$

Let $G=(V,E)$ be a connected simple undirected graph and let $k>0$ be an integer such that

  1. $\delta(G) \geq k$ (that is every vertex has at least $k$ neighbours), and
  2. $K_{k+1}$ is not a minor of $G$.

Question: In terms of $k$, how many vertices does a graph satisfying 1. and 2. above to contain at least? In other words, I am looking for an interesting lower bound for $|V|$.

(Remark: a trivial lower bound for $|V|$ is $|V|\geq k+2$ as for $|V|=k+1$ we would get $G\cong K_{k+1}$ by point 1 above, violating point 2.)

Improve this question
$\endgroup$
4
  • $\begingroup$ Such a graph can be arbitrarily large, even for $k=4$. For example, there are arbitrarily large planar graphs with minimum degree $4$. $\endgroup$
    – Tony Huynh
    Commented Aug 4, 2016 at 9:08
  • $\begingroup$ Maybe there is a misunderstanding. I am keen to know how many verices at least a graph satisfying 1. and 2. needs. Will edit question accordingly. $\endgroup$
    – Dominic van der Zypen
    Commented Aug 4, 2016 at 10:00
  • $\begingroup$ Well, in that case, $k+2$ is achievable. For example, if $n \geq 6$ is even, then $K_n$ minus a perfect matching does not have a $K_{n-1}$-minor. $\endgroup$
    – Tony Huynh
    Commented Aug 4, 2016 at 13:26
  • $\begingroup$ Oh - thanks! Do you want to put this in an answer so I can accept&close this, or should I better delete the question? $\endgroup$
    – Dominic van der Zypen
    Commented Aug 4, 2016 at 13:51

1 Answer 1

Reset to default
1
$\begingroup$

There is such a graph with $k+2$ vertices for all $k \geq 4$. To see this, first assume that $k$ is even. Let $G$ be $K_{k+2}$ minus the edges of a perfect matching. Note that every vertex of $G$ has degree $k$, but $G$ does not contain a $K_{k+1}$-minor. For $k$ odd, just take the even example and add an apex vertex.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I had a similar problem posted somewhere before. Instead of $K_{k+1}$ as minor what if we seek number of vertices needed such that there is no genus $g$ graph minor? $\endgroup$
    – Turbo
    Commented Aug 5, 2016 at 7:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .