2
$\begingroup$

Show that a graph with exactly one vertex of degree $i$ : $2\le i \le m$ and $k$ other vertices (which are monovalent) satisfies $\left\lfloor\frac{m+3}2\right\rfloor \le k\;.$

Here is my current approach. I want to a construct a graph of minimal $k$ - to do this I need to make sure that all the all the other vertices of degree $i$ connect to the vertex of degree $m$, and that the other vertices of degree $m-1$, $m-2$, ... share the largest number of vertices that won't result in a double. Here is my current construction.

Start with a vertex of degree $m$ $v_0$. choose some $v$ adjacent to that vertex, $v_1$. Connect it to $m-2$ of the other vertices giving it degree $m-1$ and creating $m-2$ vertices of degree $2$. At the next step, choose another of the vertices of degree $2$, call it $v_3$. connect it to $m-4$ vertices of degree $2$, leaving $1$ vertex of degree $2$, and creating $m-4$ vertices of degree $3$.

This produces a sequence of graphs $G_n$, where each graph contains exactly one vertex of degree $1,\dots ,n+1$ and degree $m,\dots ,(m-n)+1$.

Now at some point, we will reach an $i$ s.t $m-i = i+1$, at which point we will have two duplicate vertices. We then only have to move at most $i$ edges in order to get a graph with the "minimal number" of monovalent vertices satisfying this property.

Problem is I can't prove this graph is minimal, and I can't figure out how to get the bound to arise from this construction.

1 Answers 1

4

The idea of this problem is to look at how many vertices we need to add such that the resulting degree sequence is actually realizable as a simple graph. You can draw a few examples yourself and you will quickly realize that the vertices of degree $2\le i \le m$ alone is not realizable as a graph. To produce a graph, we must add a number of monovalent vertices. Let us take a look at how many monovalent vertices we must add to produce a proper graph then.

Suppose a graph with vertices of degree $i:\ 2\le i \le m$ along with $k$ monovalent vertices exist. Then the degree sequence of this graph $(m, m-2, \cdots, 2, \underbrace{1, \cdots, 1}_k)$ must satisfy the Erdős-Gallai Theorem, i.e. we must have $\sum^{i}_{j=1}d_j\leq i(i-1)+ \sum^n_{j=i+1} \min(d_j,i)$ for $1\le i \le n$ where $n$ is the number of vertices.

The idea is to examine the associated inequalities at their "weakest" point.

Consider the first $m-1$ vertices. Their associated numbering in the sequence is $\begin{matrix}d_i=&m & m-1 & \cdots & 3 & 2\\i= & 1 & 2 & \cdots & m-2 & m-1 \end{matrix}$ The point at which the latter sum begins to increase less rapidly is precisely when $i \ge d_{i+1}$ which first happens at $i=\lfloor\frac{m+1}{2}\rfloor$ and that is the point at which we want to take our inequality. To avoid tedious floor functions, I will work with even and odd cases separately (actually, I will do even and leave odd to you).

Let $m=2\ell$. Then the inequality can be written as $\sum_{j=1}^\ell d_j \le \ell(\ell-1) + \sum_{j=\ell+1}^{m-1}(d_j) + k$ Evaluating the sums gives $\sum_{j=1}^\ell d_j = m + \cdots + (m-\ell +1) = \frac{(2\ell)(2\ell+1)}{2} - \frac{(\ell + 1)(\ell)}{2}$ $\sum_{j=\ell+1}^{m-1}(d_j) = (m-\ell) + \cdots + 2 = \frac{(\ell + 1)(\ell)}{2} - 1$ and putting it all together $\frac{(2\ell)(2\ell+1)}{2} - \frac{(\ell + 1)(\ell)}{2} - \frac{(\ell + 1)(\ell)}{2} + 1 - \ell(\ell-1) \le k$ after simplification, you yield $\ell(2\ell + 1) - (\ell-1)\ell - (\ell + 1)\ell + 1 \le k$ $\ell + 1 = \frac{2\ell+2}{2} = \left\lfloor\frac{m + 3}{2}\right\rfloor\le k$ The case for odd $m$ follows similarly and I will leave that proof to you.

  • 0
    Thank you very much, this was extremely helpful.2012-09-26