4
$\begingroup$

Hi there I need to show that the sequence $s(n) = \{1,1,2,2,3,3,4,4,...,n,n\}$ can be the degrees of the vertices of a simple graph, $\forall n\geq 1$. So far I have tryied to prove this by induction using the Havel-Hakimi theorem.

$s(1) = {1,1}$ And by applying the HH algorithm we see that $s(1)$ hold. The same for $s(2)$ but I don't know how to do it for the $s(n)$ case. Another way I was thinkig of was by using the Erdös- Gallai theorem. It is simple to prove that the sum of $s(n)$ is even but I don't know how to prove the second condition: $\sum_{i=1}^{k}d_i \leq k(k-1)+\sum_{i=k+1}^{n}\min(d_i,k)$

$\endgroup$

2 Answers 2

2
$\begingroup$

Let the vertex set be $a_1,a_2,\ldots,a_{n},b_1,b_2,\ldots,b_{n}$ and $a_i$ is adjacent to $b_j$ iff $i \leq j$.

$\endgroup$
0
$\begingroup$

The way I would do this is :

  1. Split the sequence in two s(n) => [(1, n), (1, n)]
  2. Flip one of the sequences.
  3. Given the highest element of one sequence (say $s_i$ = m), connect to m elements of the other sequence
  4. Each such action saturates both equivalent members of each sequence

You end up with a bipartite connected graph.

$\endgroup$

You must log in to answer this question.

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