Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
Thank you very much, this was extremely helpful. –  user42693 Sep 26 '12 at 4:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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