Let $G=(V,E)$ be a finite, simple, undirected graph. Let $\Delta(G)$ be the maximal degree of $G$. Is there a finite graph $G'=(V', E')$ with the following properties?

  1. $V\subseteq V'$,
  2. $E \subseteq E'$, and
  3. $G'$ is $\Delta(G)$-regular.
  • $\begingroup$ In other words, if $\Delta\ge d_1\ge d_2\ge\dots d_n\ge 0$, then $\Delta,\dots \Delta, d_1\dots d_n$ is a graphic sequence for some number of repetitions of $\Delta$. Looks obvious, doesn't it? $\endgroup$ – fedja May 22 at 7:23
  • 2
    $\begingroup$ @fedja not quite just graphic sequence, we should save the existed edges $\endgroup$ – Fedor Petrov May 22 at 7:29
  • $\begingroup$ @FedorPetrov $d_j$ are $\Delta$ minus the existing degrees, i.e., I'm looking for the complement. I thought that was clear enough :-) $\endgroup$ – fedja May 22 at 7:31
  • 1
    $\begingroup$ @fedja well, but the complement should avoid existed edges, right? $\endgroup$ – Fedor Petrov May 22 at 7:36
  • 1
    $\begingroup$ @FedorPetrov Indeed, you are right. The correction is trivial (add some edges sticking out to saturate the existing vertices and consider the new graph), but then it basically becomes your construction. $\endgroup$ – fedja May 22 at 7:53

Yes. First of all, for any vertex $v\in V$ we draw the edges to $\Delta(G)-\deg(v)$ new vertices so that the degree of $v$ becomes equal to $\Delta(G)$. Now all degrees are equal either to $\Delta(G)$ or to 1. Without loss of generality, the number of vertices with degree 1 is even (else add the disjoint copy of the current graph). Partition them onto pairs, and for any pair $a,b$ take a graph $K_{d+1}\setminus \{ab\}$ on the vertex set $\{a,b, d-1\, \text{new vertices}\}$.

  • $\begingroup$ Very nice construction, thanks Fedor! $\endgroup$ – Dominic van der Zypen May 22 at 7:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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