Gráficos de gracia con Valence $k$

Question

Para un gráfico elegante ( código ), los vértices se etiquetan con valores de 0 a $e$ para que el $e$ las diferencias de borde son todos los valores de 1 a $e$ .
La siguiente es la secuencia de la OEIS A308722 .
$K_3$ es el gráfico mínimo de valencia 2 con $e=3$ .
$K_4$ es el gráfico mínimo de valencia 3 con $e=6$ .
$O$ es el gráfico mínimo de valencia 4 con $e=12$ .

El gráfico mínimo de gracia con valencia 5 tiene $e=20$ .

El gráfico mínimo de gracia con valencia 6 tiene $e=27$ .

El gráfico mínimo de gracia para la valencia 7 tiene $e=35$ . Es único.

¿Qué son los gráficos mínimos de gracia con valencia 8 y superior? Están muy relacionados con reglas escasas . Mi opinión sobre el comportamiento futuro es:
e=48 con 12 vértices de valencia 8. (verificado este)

e=63 con 14 vértices de valencia 9. Verificado. El complemento del grafo de la siguiente es grácil.

O en la forma más normal

e=75 con 15 vértices de valencia 10. Verificado. Hay 37 grafos de este tipo. El complemento del grafo siguiente es agraciado.

e=99 con 18 vértices de valencia 11. (e=88 resultó imposible). Verificado.

e=108 con 18 vértices de valencia 12. Verificado. El complemento del grafo siguiente es agraciado.

e=130 con 20 vértices de valencia 13. Verificado.
e=147 con 21 vértices de valencia 14.
e=180 con 24 vértices de valencia 15.
e=192 con 24 vértices de valencia 16.
e=221 con 26 vértices de valencia 17.
e=243 con 27 vértices de valencia 18.
e=285 con 30 vértices de valencia 19.
e=320 con 32 vértices de valencia 20.
e=336 con 32 vértices de valencia 21.

Muchos de estos gráficos de gracia se basan en datos obtenidos para la Conjetura de la regla dispersa . En esa página hay una lista de ejemplos de reglas dispersas hasta la longitud 600. Aquí están las longitudes 601 a 1100.

601 43 1 | 1×8 8×1 16×8 33×9 17×9 1×7
602 43 0 | 1×8 8×1 16×7 33×10 17×8 1×8
603 43 0 | 1×8 9×1 17×8 35×8 18×9 1×8
604 43 0 | 1×6 6×1 12×7 25×17 13×6 1×5
605 43 0 | 1×6 6×1 12×6 25×17 13×7 1×5
606 43 0 | 1×6 6×1 12×5 25×18 13×6 1×6
607 43 0 | 1×6 7×1 13×6 27×15 14×7 1×6 7×1
608 43 0 | 1×6 7×1 13×5 27×16 14×6 1×7 7×1
609 44 1 | 1×8 8×1 16×9 33×9 17×8 1×7 9×1
610 43 0 | 1×7 8×1 15×8 31×5 15×1 31×6 16×7 1×7
611 43 0 | 1×7 8×1 15×8 31×5 16×1 31×6 16×7 1×7
612 43 0 | 1×7 8×1 15×7 31×6 16×1 31×5 16×8 1×7
613 43 0 | 1×6 7×1 13×7 27×7 14×1 27×8 14×6 1×6
614 43 0 | 1×7 7×1 14×8 29×13 15×7 1×6
615 43 0 | 1×7 7×1 14×7 29×13 15×8 1×6
616 43 0 | 1×7 7×1 14×6 29×14 15×7 1×7
617 44 1 | 1×8 7×1 14×6 29×14 15×7 1×7
618 44 1 | 1×7 7×1 14×8 29×13 15×7 1×6 4×1
619 44 1 | 1×7 7×1 14×8 29×13 15×7 1×6 5×1
620 44 1 | 1×7 7×1 14×8 29×13 15×7 1×6 6×1
621 44 1 | 1×7 7×1 14×8 29×13 15×7 1×6 7×1
622 44 1 | 1×7 7×1 14×8 29×13 15×7 1×6 8×1
623 44 1 | 1×7 7×1 14×7 29×13 15×8 1×6 8×1
624 44 1 | 1×7 7×1 14×6 29×14 15×7 1×7 8×1
625 44 1 | 1×7 8×1 15×10 31×11 16×7 1×7
626 43 0 | 1×7 8×1 15×8 31×12 16×7 1×7
627 43 0 | 1×7 8×1 15×7 31×12 16×8 1×7
628 44 1 | 1×8 8×1 15×7 31×12 16×8 1×7
629 44 1 | 1×6 6×1 12×7 25×18 13×6 1×5
630 44 0 | 1×6 6×1 12×6 25×18 13×7 1×5
631 44 0 | 1×6 6×1 12×5 25×19 13×6 1×6
632 44 0 | 1×7 8×1 15×8 31×12 16×7 1×7 6×1
633 44 0 | 1×8 8×1 16×9 33×10 17×8 1×7
634 44 0 | 1×8 8×1 16×8 33×10 17×9 1×7
635 44 0 | 1×8 8×1 16×7 33×11 17×8 1×8
636 44 0 | 1×7 8×1 15×6 31×13 16×7 1×8 8×1
637 44 0 | 1×8 9×1 17×9 35×9 18×8 1×8
638 44 0 | 1×8 9×1 17×8 35×9 18×9 1×8
639 44 0 | 1×6 7×1 13×7 27×8 13×1 27×8 14×6 1×6
640 44 0 | 1×6 7×1 13×7 27×8 14×1 27×8 14×6 1×6
641 44 0 | 1×7 8×1 15×8 31×6 15×1 31×6 16×7 1×7
642 44 0 | 1×7 8×1 15×8 31×6 16×1 31×6 16×7 1×7
643 44 0 | 1×7 7×1 14×8 29×14 15×7 1×6
644 44 0 | 1×7 7×1 14×7 29×14 15×8 1×6
645 44 0 | 1×7 7×1 14×6 29×15 15×7 1×7
646 45 1 | 1×8 7×1 14×6 29×15 15×7 1×7
647 45 1 | 1×8 9×1 17×8 35×9 18×9 1×8 9×1
648 45 1 | 1×5 6×1 11×6 23×22 12×5 1×5
649 45 1 | 1×5 6×1 11×5 23×22 12×6 1×5
650 45 1 | 1×7 7×1 14×8 29×14 15×7 1×6 7×1
651 45 1 | 1×7 7×1 14×8 29×14 15×7 1×6 8×1
652 45 1 | 1×6 7×1 13×9 27×16 14×6 1×6
653 44 0 | 1×6 7×1 13×7 27×17 14×6 1×6
654 44 0 | 1×6 7×1 13×6 27×17 14×7 1×6
655 45 1 | 1×7 7×1 13×6 27×17 14×7 1×6
656 45 1 | 1×7 8×1 15×10 31×12 16×7 1×7
657 44 0 | 1×7 8×1 15×8 31×13 16×7 1×7
658 44 0 | 1×7 8×1 15×7 31×13 16×8 1×7
659 45 1 | 1×8 8×1 15×7 31×13 16×8 1×7
660 45 0 | 1×7 8×1 15×8 31×13 16×7 1×7 3×1
661 45 0 | 1×7 8×1 15×8 31×13 16×7 1×7 4×1
662 45 0 | 1×7 8×1 15×8 31×13 16×7 1×7 5×1
663 45 0 | 1×7 8×1 15×8 31×13 16×7 1×7 6×1
664 45 0 | 1×7 8×1 15×8 31×13 16×7 1×7 7×1
665 45 0 | 1×7 8×1 15×8 31×13 16×7 1×7 8×1
666 45 0 | 1×8 8×1 16×9 33×11 17×8 1×7
667 45 0 | 1×8 8×1 16×8 33×11 17×9 1×7
668 45 0 | 1×8 8×1 16×7 33×12 17×8 1×8
669 46 1 | 1×9 8×1 16×7 33×12 17×8 1×8
670 46 1 | 1×8 8×1 16×9 33×11 17×8 1×7 4×1
671 46 1 | 1×9 10×1 19×10 39×7 20×9 1×9
672 45 0 | 1×8 9×1 17×9 35×10 18×8 1×8
673 45 0 | 1×8 9×1 17×8 35×10 18×9 1×8
674 45 0 | 1×7 7×1 14×6 29×16 15×7 1×7
675 46 1 | 1×9 9×1 18×8 37×9 19×9 1×9
676 46 1 | 1×8 8×1 16×8 33×11 17×9 1×7 9×1
677 46 1 | 1×8 8×1 16×7 33×12 17×8 1×8 9×1
678 46 1 | 1×8 9×1 16×7 33×12 17×8 1×8 9×1
679 46 1 | 1×6 6×1 12×7 25×20 13×6 1×5
680 45 0 | 1×6 7×1 13×7 27×18 14×6 1×6
681 45 0 | 1×6 7×1 13×6 27×18 14×7 1×6
682 46 1 | 1×7 7×1 13×6 27×18 14×7 1×6
683 46 1 | 1×7 8×1 14×6 29×16 15×7 1×7 8×1
684 46 1 | 1×6 7×1 13×7 27×18 14×6 1×6 4×1
685 46 1 | 1×6 7×1 13×7 27×18 14×6 1×6 5×1
686 46 1 | 1×6 7×1 13×7 27×18 14×6 1×6 6×1
687 46 1 | 1×7 8×1 15×10 31×13 16×7 1×7
688 45 0 | 1×7 8×1 15×8 31×14 16×7 1×7
689 45 0 | 1×7 8×1 15×7 31×14 16×8 1×7
690 46 0 | 1×8 8×1 15×7 31×14 16×8 1×7
691 46 0 | 1×7 8×1 15×8 31×14 16×7 1×7 3×1
692 46 0 | 1×7 8×1 15×8 31×14 16×7 1×7 4×1
693 46 0 | 1×7 8×1 15×8 31×14 16×7 1×7 5×1
694 46 0 | 1×7 8×1 15×8 31×14 16×7 1×7 6×1
695 46 0 | 1×7 8×1 15×8 31×14 16×7 1×7 7×1
696 46 0 | 1×7 8×1 15×8 31×14 16×7 1×7 8×1
697 46 0 | 1×7 8×1 15×7 31×14 16×8 1×7 8×1
698 46 0 | 1×7 8×1 15×6 31×15 16×7 1×8 8×1
699 46 0 | 1×8 8×1 16×9 33×12 17×8 1×7
700 46 0 | 1×8 8×1 16×8 33×12 17×9 1×7
701 46 0 | 1×8 8×1 16×7 33×13 17×8 1×8
702 46 0 | 1×7 7×1 14×7 29×16 15×8 1×6
703 46 0 | 1×7 7×1 14×6 29×17 15×7 1×7
704 46 0 | 1×7 8×1 15×8 31×7 16×1 31×7 16×7 1×7
705 46 0 | 1×7 8×1 15×7 31×7 16×1 31×7 16×8 1×7
706 47 1 | 1×8 9×1 17×11 35×10 18×8 1×8
707 46 0 | 1×8 9×1 17×9 35×11 18×8 1×8
708 46 0 | 1×8 9×1 17×8 35×11 18×9 1×8
709 47 1 | 1×9 9×1 17×8 35×11 18×9 1×8
710 47 1 | 1×9 9×1 18×10 37×9 19×9 1×8
711 47 1 | 1×9 9×1 18×9 37×9 19×10 1×8
712 47 1 | 1×9 9×1 18×8 37×10 19×9 1×9
713 47 1 | 1×8 9×1 17×9 35×11 18×8 1×8 6×1
714 47 1 | 1×8 9×1 17×9 35×11 18×8 1×8 7×1
715 47 1 | 1×8 9×1 17×9 35×11 18×8 1×8 8×1
716 47 1 | 1×8 9×1 17×9 35×11 18×8 1×8 9×1
717 47 1 | 1×8 9×1 17×8 35×11 18×9 1×8 9×1
718 47 1 | 1×7 8×1 15×10 31×14 16×7 1×7
719 46 0 | 1×7 8×1 15×8 31×15 16×7 1×7
720 46 0 | 1×7 8×1 15×7 31×15 16×8 1×7
721 47 0 | 1×8 8×1 15×7 31×15 16×8 1×7
722 47 0 | 1×7 8×1 15×8 31×15 16×7 1×7 3×1
723 47 0 | 1×7 8×1 15×8 31×15 16×7 1×7 4×1
724 47 0 | 1×7 8×1 15×8 31×15 16×7 1×7 5×1
725 47 0 | 1×7 8×1 15×8 31×15 16×7 1×7 6×1
726 47 0 | 1×7 8×1 15×8 31×15 16×7 1×7 7×1
727 47 0 | 1×7 8×1 15×8 31×15 16×7 1×7 8×1
728 47 0 | 1×7 8×1 15×7 31×15 16×8 1×7 8×1
729 47 0 | 1×7 8×1 15×6 31×16 16×7 1×8 8×1
730 47 0 | 1×7 7×1 14×8 29×17 15×7 1×6
731 47 0 | 1×7 7×1 14×7 29×17 15×8 1×6
732 47 0 | 1×8 8×1 16×9 33×13 17×8 1×7
733 47 0 | 1×8 8×1 16×8 33×13 17×9 1×7
734 47 0 | 1×8 8×1 16×7 33×14 17×8 1×8
735 47 0 | 1×6 7×1 13×6 27×20 14×7 1×6
736 47 0 | 1×7 8×1 15×7 31×8 16×1 31×7 16×8 1×7
737 48 1 | 1×8 8×1 16×9 33×13 17×8 1×7 5×1
738 48 1 | 1×8 8×1 16×9 33×13 17×8 1×7 6×1
739 48 1 | 1×8 8×1 16×9 33×13 17×8 1×7 7×1
740 48 1 | 1×8 8×1 16×9 33×13 17×8 1×7 8×1
741 48 1 | 1×8 9×1 17×11 35×11 18×8 1×8
742 47 0 | 1×8 9×1 17×9 35×12 18×8 1×8
743 47 0 | 1×8 9×1 17×8 35×12 18×9 1×8
744 48 1 | 1×9 9×1 17×8 35×12 18×9 1×8
745 48 1 | 1×8 9×1 17×9 35×12 18×8 1×8 3×1
746 48 1 | 1×8 9×1 17×9 35×12 18×8 1×8 4×1
747 48 1 | 1×9 9×1 18×10 37×10 19×9 1×8
748 48 1 | 1×9 9×1 18×9 37×10 19×10 1×8
749 48 1 | 1×9 9×1 18×8 37×11 19×9 1×9
750 47 0 | 1×7 8×1 15×8 31×16 16×7 1×7
751 47 0 | 1×7 8×1 15×7 31×16 16×8 1×7
752 48 0 | 1×8 8×1 15×7 31×16 16×8 1×7
753 48 0 | 1×7 8×1 15×8 31×16 16×7 1×7 3×1
754 48 0 | 1×7 8×1 15×8 31×16 16×7 1×7 4×1
755 48 0 | 1×7 8×1 15×8 31×16 16×7 1×7 5×1
756 48 0 | 1×7 8×1 15×8 31×16 16×7 1×7 6×1
757 48 0 | 1×7 8×1 15×8 31×16 16×7 1×7 7×1
758 48 0 | 1×7 8×1 15×8 31×16 16×7 1×7 8×1
759 48 0 | 1×7 7×1 14×8 29×18 15×7 1×6
760 48 0 | 1×7 7×1 14×7 29×18 15×8 1×6
761 48 0 | 1×7 7×1 14×6 29×19 15×7 1×7
762 48 0 | 1×6 7×1 13×6 27×21 14×7 1×6
763 49 1 | 1×7 7×1 13×6 27×21 14×7 1×6
764 49 1 | 1×8 8×1 16×11 33×13 17×8 1×7
765 48 0 | 1×8 8×1 16×9 33×14 17×8 1×7
766 48 0 | 1×8 8×1 16×8 33×14 17×9 1×7
767 48 0 | 1×8 8×1 16×7 33×15 17×8 1×8
768 49 1 | 1×9 8×1 16×7 33×15 17×8 1×8
769 49 1 | 1×8 8×1 16×9 33×14 17×8 1×7 4×1
770 49 1 | 1×8 8×1 16×9 33×14 17×8 1×7 5×1
771 49 1 | 1×8 8×1 16×9 33×14 17×8 1×7 6×1
772 49 1 | 1×8 8×1 16×9 33×14 17×8 1×7 7×1
773 49 1 | 1×8 8×1 16×9 33×14 17×8 1×7 8×1
774 49 1 | 1×8 8×1 16×9 33×14 17×8 1×7 9×1
775 49 1 | 1×8 8×1 16×8 33×14 17×9 1×7 9×1
776 49 1 | 1×8 9×1 17×11 35×12 18×8 1×8
777 48 0 | 1×8 9×1 17×9 35×13 18×8 1×8
778 48 0 | 1×8 9×1 17×8 35×13 18×9 1×8
779 49 1 | 1×9 9×1 17×8 35×13 18×9 1×8
780 49 1 | 1×7 8×1 15×10 31×16 16×7 1×7
781 48 0 | 1×7 8×1 15×8 31×17 16×7 1×7
782 48 0 | 1×7 8×1 15×7 31×17 16×8 1×7
783 49 1 | 1×8 8×1 15×7 31×17 16×8 1×7
784 49 0 | 1×9 9×1 18×10 37×11 19×9 1×8
785 49 0 | 1×9 9×1 18×9 37×11 19×10 1×8
786 49 0 | 1×9 9×1 18×8 37×12 19×9 1×9
787 49 0 | 1×8 9×1 17×8 35×13 18×9 1×8 9×1
788 49 0 | 1×9 10×1 19×10 39×10 20×9 1×9
789 49 0 | 1×9 10×1 19×9 39×10 20×10 1×9
790 49 0 | 1×7 7×1 14×6 29×20 15×7 1×7
791 49 0 | 1×7 8×1 15×6 31×18 16×7 1×8 8×1
792 50 1 | 1×9 9×1 18×10 37×11 19×9 1×8 8×1
793 50 1 | 1×9 9×1 18×10 37×11 19×9 1×8 9×1
794 49 0 | 1×8 9×1 17×9 35×6 17×1 35×7 18×8 1×8
795 49 0 | 1×8 9×1 17×9 35×6 18×1 35×7 18×8 1×8
796 49 0 | 1×8 9×1 17×8 35×7 18×1 35×6 18×9 1×8
797 49 0 | 1×7 8×1 15×8 31×8 16×1 31×9 16×7 1×7
798 49 0 | 1×8 8×1 16×9 33×15 17×8 1×7
799 49 0 | 1×8 8×1 16×8 33×15 17×9 1×7
800 49 0 | 1×8 8×1 16×7 33×16 17×8 1×8
801 50 1 | 1×9 8×1 16×7 33×16 17×8 1×8
802 50 1 | 1×8 8×1 16×9 33×15 17×8 1×7 4×1
803 50 1 | 1×8 8×1 16×9 33×15 17×8 1×7 5×1
804 50 1 | 1×8 8×1 16×9 33×15 17×8 1×7 6×1
805 50 1 | 1×8 8×1 16×9 33×15 17×8 1×7 7×1
806 50 1 | 1×8 8×1 16×9 33×15 17×8 1×7 8×1
807 50 1 | 1×8 8×1 16×9 33×15 17×8 1×7 9×1
808 50 1 | 1×8 8×1 16×8 33×15 17×9 1×7 9×1
809 50 1 | 1×8 8×1 16×7 33×16 17×8 1×8 9×1
810 50 1 | 1×8 9×1 16×7 33×16 17×8 1×8 9×1
811 50 1 | 1×8 9×1 17×11 35×13 18×8 1×8
812 49 0 | 1×8 9×1 17×9 35×14 18×8 1×8
813 49 0 | 1×8 9×1 17×8 35×14 18×9 1×8
814 50 1 | 1×9 9×1 17×8 35×14 18×9 1×8
815 50 1 | 1×6 7×1 13×7 27×23 14×6 1×6
816 50 0 | 1×6 7×1 13×6 27×23 14×7 1×6
817 50 0 | 1×7 7×1 14×8 29×20 15×7 1×6
818 50 0 | 1×7 7×1 14×7 29×20 15×8 1×6
819 50 0 | 1×7 7×1 14×6 29×21 15×7 1×7
820 50 0 | 1×8 9×1 17×9 35×14 18×8 1×8 8×1
821 50 0 | 1×9 9×1 18×10 37×12 19×9 1×8
822 50 0 | 1×9 9×1 18×9 37×12 19×10 1×8
823 50 0 | 1×9 9×1 18×8 37×13 19×9 1×9
824 51 1 | 1×10 9×1 18×8 37×13 19×9 1×9
825 51 1 | 1×9 9×1 18×10 37×12 19×9 1×8 4×1
826 51 1 | 1×10 11×1 21×11 43×8 22×10 1×10
827 50 0 | 1×9 10×1 19×10 39×11 20×9 1×9
828 50 0 | 1×9 10×1 19×9 39×11 20×10 1×9
829 50 0 | 1×8 9×1 17×9 35×7 17×1 35×7 18×8 1×8
830 50 0 | 1×8 9×1 17×9 35×7 18×1 35×7 18×8 1×8
831 50 0 | 1×8 8×1 16×9 33×16 17×8 1×7
832 50 0 | 1×8 8×1 16×8 33×16 17×9 1×7
833 50 0 | 1×8 8×1 16×7 33×17 17×8 1×8
834 51 1 | 1×9 8×1 16×7 33×17 17×8 1×8
835 51 1 | 1×9 10×1 19×10 39×11 20×9 1×9 8×1
836 51 1 | 1×9 10×1 19×10 39×11 20×9 1×9 9×1
837 51 1 | 1×9 10×1 19×10 39×11 20×9 1×9 10×1
838 51 1 | 1×9 10×1 19×9 39×11 20×10 1×9 10×1
839 51 1 | 1×8 8×1 16×9 33×16 17×8 1×7 8×1
840 51 1 | 1×8 8×1 16×9 33×16 17×8 1×7 9×1
841 51 1 | 1×8 8×1 16×8 33×16 17×9 1×7 9×1
842 51 1 | 1×7 8×1 15×10 31×18 16×7 1×7
843 50 0 | 1×7 8×1 15×8 31×19 16×7 1×7
844 50 0 | 1×7 8×1 15×7 31×19 16×8 1×7
845 51 1 | 1×8 8×1 15×7 31×19 16×8 1×7
846 51 1 | 1×8 9×1 17×11 35×14 18×8 1×8
847 50 0 | 1×8 9×1 17×9 35×15 18×8 1×8
848 50 0 | 1×8 9×1 17×8 35×15 18×9 1×8
849 51 1 | 1×9 9×1 17×8 35×15 18×9 1×8
850 51 0 | 1×8 9×1 17×9 35×15 18×8 1×8 3×1
851 51 0 | 1×8 9×1 17×9 35×15 18×8 1×8 4×1
852 51 0 | 1×8 9×1 17×9 35×15 18×8 1×8 5×1
853 51 0 | 1×8 9×1 17×9 35×15 18×8 1×8 6×1
854 51 0 | 1×8 9×1 17×9 35×15 18×8 1×8 7×1
855 51 0 | 1×8 9×1 17×9 35×15 18×8 1×8 8×1
856 51 0 | 1×8 9×1 17×9 35×15 18×8 1×8 9×1
857 51 0 | 1×8 9×1 17×8 35×15 18×9 1×8 9×1
858 51 0 | 1×9 9×1 18×10 37×13 19×9 1×8
859 51 0 | 1×9 9×1 18×9 37×13 19×10 1×8
860 51 0 | 1×9 9×1 18×8 37×14 19×9 1×9
861 52 1 | 1×10 9×1 18×8 37×14 19×9 1×9
862 52 1 | 1×9 9×1 18×10 37×13 19×9 1×8 4×1
863 52 1 | 1×8 8×1 16×11 33×16 17×8 1×7
864 51 0 | 1×8 8×1 16×9 33×17 17×8 1×7
865 51 0 | 1×8 8×1 16×8 33×17 17×9 1×7
866 51 0 | 1×9 10×1 19×10 39×12 20×9 1×9
867 51 0 | 1×9 10×1 19×9 39×12 20×10 1×9
868 52 1 | 1×10 10×1 19×9 39×12 20×10 1×9
869 52 1 | 1×10 10×1 20×11 41×10 21×10 1×9
870 52 1 | 1×10 10×1 20×10 41×10 21×11 1×9
871 52 1 | 1×10 10×1 20×9 41×11 21×10 1×10
872 52 1 | 1×9 10×1 19×10 39×12 20×9 1×9 6×1
873 52 1 | 1×7 8×1 15×10 31×19 16×7 1×7
874 51 0 | 1×7 8×1 15×8 31×20 16×7 1×7
875 51 0 | 1×7 8×1 15×7 31×20 16×8 1×7
876 52 1 | 1×8 8×1 15×7 31×20 16×8 1×7
877 52 1 | 1×7 7×1 14×6 29×23 15×7 1×7
878 52 1 | 1×7 8×1 15×8 31×20 16×7 1×7 4×1
879 52 1 | 1×7 8×1 15×8 31×20 16×7 1×7 5×1
880 52 1 | 1×7 8×1 15×8 31×20 16×7 1×7 6×1
881 52 1 | 1×8 9×1 17×11 35×15 18×8 1×8
882 51 0 | 1×8 9×1 17×9 35×16 18×8 1×8
883 51 0 | 1×8 9×1 17×8 35×16 18×9 1×8
884 52 0 | 1×9 9×1 17×8 35×16 18×9 1×8
885 52 0 | 1×8 9×1 17×9 35×16 18×8 1×8 3×1
886 52 0 | 1×8 9×1 17×9 35×16 18×8 1×8 4×1
887 52 0 | 1×8 9×1 17×9 35×16 18×8 1×8 5×1
888 52 0 | 1×8 9×1 17×9 35×16 18×8 1×8 6×1
889 52 0 | 1×8 9×1 17×9 35×16 18×8 1×8 7×1
890 52 0 | 1×8 9×1 17×9 35×16 18×8 1×8 8×1
891 52 0 | 1×8 9×1 17×9 35×16 18×8 1×8 9×1
892 52 0 | 1×8 9×1 17×8 35×16 18×9 1×8 9×1
893 53 1 | 1×9 8×1 17×8 35×16 18×9 1×8 10×1
894 53 1 | 1×9 9×1 18×12 37×13 19×9 1×8
895 52 0 | 1×9 9×1 18×10 37×14 19×9 1×8
896 52 0 | 1×9 9×1 18×9 37×14 19×10 1×8
897 52 0 | 1×9 9×1 18×8 37×15 19×9 1×9
898 52 0 | 1×8 8×1 16×8 33×18 17×9 1×7
899 52 0 | 1×8 8×1 16×7 33×19 17×8 1×8
900 52 0 | 1×8 9×1 17×9 35×8 18×1 35×8 18×8 1×8
901 52 0 | 1×8 9×1 17×8 35×8 18×1 35×8 18×9 1×8
902 53 1 | 1×9 9×1 18×10 37×14 19×9 1×8 7×1
903 53 1 | 1×9 9×1 18×10 37×14 19×9 1×8 8×1
904 53 1 | 1×9 10×1 19×12 39×12 20×9 1×9
905 52 0 | 1×9 10×1 19×10 39×13 20×9 1×9
906 52 0 | 1×9 10×1 19×9 39×13 20×10 1×9
907 53 1 | 1×10 10×1 19×9 39×13 20×10 1×9
908 53 1 | 1×9 10×1 18×8 37×15 19×9 1×9 10×1
909 53 1 | 1×9 10×1 19×10 39×13 20×9 1×9 4×1
910 53 1 | 1×10 10×1 20×11 41×11 21×10 1×9
911 53 1 | 1×10 10×1 20×10 41×11 21×11 1×9
912 53 1 | 1×10 10×1 20×9 41×12 21×10 1×10
913 53 1 | 1×10 11×1 21×10 43×10 22×11 1×10
914 53 1 | 1×9 10×1 19×10 39×13 20×9 1×9 9×1
915 53 1 | 1×9 10×1 19×10 39×13 20×9 1×9 10×1
916 53 1 | 1×8 9×1 17×11 35×16 18×8 1×8
917 52 0 | 1×8 9×1 17×9 35×17 18×8 1×8
918 52 0 | 1×8 9×1 17×8 35×17 18×9 1×8
919 53 0 | 1×9 9×1 17×8 35×17 18×9 1×8
920 53 0 | 1×8 9×1 17×9 35×17 18×8 1×8 3×1
921 53 0 | 1×8 9×1 17×9 35×17 18×8 1×8 4×1
922 53 0 | 1×8 9×1 17×9 35×17 18×8 1×8 5×1
923 53 0 | 1×8 9×1 17×9 35×17 18×8 1×8 6×1
924 53 0 | 1×8 9×1 17×9 35×17 18×8 1×8 7×1
925 53 0 | 1×8 9×1 17×9 35×17 18×8 1×8 8×1
926 53 0 | 1×8 9×1 17×9 35×17 18×8 1×8 9×1
927 53 0 | 1×8 9×1 17×8 35×17 18×9 1×8 9×1
928 54 1 | 1×9 8×1 17×8 35×17 18×9 1×8 10×1
929 54 1 | 1×8 8×1 16×11 33×18 17×8 1×7
930 53 0 | 1×8 8×1 16×9 33×19 17×8 1×7
931 53 0 | 1×8 8×1 16×8 33×19 17×9 1×7
932 53 0 | 1×9 9×1 18×10 37×15 19×9 1×8
933 53 0 | 1×9 9×1 18×9 37×15 19×10 1×8
934 53 0 | 1×9 9×1 18×8 37×16 19×9 1×9
935 53 0 | 1×8 9×1 17×9 35×8 18×1 35×9 18×8 1×8
936 53 0 | 1×7 8×1 15×8 31×22 16×7 1×7
937 53 0 | 1×7 8×1 15×7 31×22 16×8 1×7
938 54 1 | 1×8 8×1 15×7 31×22 16×8 1×7
939 54 1 | 1×9 9×1 18×10 37×15 19×9 1×8 7×1
940 54 1 | 1×9 9×1 18×10 37×15 19×9 1×8 8×1
941 54 1 | 1×9 9×1 18×10 37×15 19×9 1×8 9×1
942 54 1 | 1×9 9×1 18×10 37×15 19×9 1×8 10×1
943 54 1 | 1×9 10×1 19×12 39×13 20×9 1×9
944 53 0 | 1×9 10×1 19×10 39×14 20×9 1×9
945 53 0 | 1×9 10×1 19×9 39×14 20×10 1×9
946 54 1 | 1×10 10×1 19×9 39×14 20×10 1×9
947 54 1 | 1×9 10×1 19×10 39×14 20×9 1×9 3×1
948 54 1 | 1×9 10×1 19×10 39×14 20×9 1×9 4×1
949 54 1 | 1×9 10×1 19×10 39×14 20×9 1×9 5×1
950 54 1 | 1×9 10×1 19×10 39×14 20×9 1×9 6×1
951 54 1 | 1×10 10×1 20×11 41×12 21×10 1×9
952 53 0 | 1×8 9×1 17×9 35×18 18×8 1×8
953 53 0 | 1×8 9×1 17×8 35×18 18×9 1×8
954 54 0 | 1×9 9×1 17×8 35×18 18×9 1×8
955 54 0 | 1×10 11×1 21×11 43×11 22×10 1×10
956 54 0 | 1×10 11×1 21×10 43×11 22×11 1×10
957 54 0 | 1×8 9×1 17×9 35×18 18×8 1×8 5×1
958 54 0 | 1×8 9×1 17×9 35×18 18×8 1×8 6×1
959 54 0 | 1×8 9×1 17×9 35×18 18×8 1×8 7×1
960 54 0 | 1×8 9×1 17×9 35×18 18×8 1×8 8×1
961 54 0 | 1×8 9×1 17×9 35×18 18×8 1×8 9×1
962 54 0 | 1×8 9×1 17×8 35×18 18×9 1×8 9×1
963 54 0 | 1×8 8×1 16×9 33×20 17×8 1×7
964 54 0 | 1×8 8×1 16×8 33×20 17×9 1×7
965 54 0 | 1×8 8×1 16×7 33×21 17×8 1×8
966 55 1 | 1×9 8×1 16×7 33×21 17×8 1×8
967 54 0 | 1×7 8×1 15×8 31×23 16×7 1×7
968 54 0 | 1×7 8×1 15×7 31×23 16×8 1×7
969 54 0 | 1×9 9×1 18×10 37×16 19×9 1×8
970 54 0 | 1×9 9×1 18×9 37×16 19×10 1×8
971 54 0 | 1×9 9×1 18×8 37×17 19×9 1×9
972 55 1 | 1×10 9×1 18×8 37×17 19×9 1×9
973 55 1 | 1×9 9×1 18×10 37×16 19×9 1×8 4×1
974 55 1 | 1×9 9×1 18×10 37×16 19×9 1×8 5×1
975 55 1 | 1×9 9×1 18×10 37×16 19×9 1×8 6×1
976 55 1 | 1×9 9×1 18×10 37×16 19×9 1×8 7×1
977 55 1 | 1×9 9×1 18×10 37×16 19×9 1×8 8×1
978 55 1 | 1×9 9×1 18×10 37×16 19×9 1×8 9×1
979 55 1 | 1×9 9×1 18×10 37×16 19×9 1×8 10×1
980 55 1 | 1×9 9×1 18×9 37×16 19×10 1×8 10×1
981 55 1 | 1×9 9×1 18×8 37×17 19×9 1×9 10×1
982 55 1 | 1×9 10×1 19×12 39×14 20×9 1×9
983 54 0 | 1×9 10×1 19×10 39×15 20×9 1×9
984 54 0 | 1×9 10×1 19×9 39×15 20×10 1×9
985 55 1 | 1×10 10×1 19×9 39×15 20×10 1×9
986 55 1 | 1×8 9×1 17×11 35×18 18×8 1×8
987 54 0 | 1×8 9×1 17×9 35×19 18×8 1×8
988 54 0 | 1×8 9×1 17×8 35×19 18×9 1×8
989 55 1 | 1×9 9×1 17×8 35×19 18×9 1×8
990 55 0 | 1×9 10×1 19×10 39×15 20×9 1×9 7×1
991 55 0 | 1×9 10×1 19×10 39×15 20×9 1×9 8×1
992 55 0 | 1×10 10×1 20×11 41×13 21×10 1×9
993 55 0 | 1×10 10×1 20×10 41×13 21×11 1×9
994 55 0 | 1×10 10×1 20×9 41×14 21×10 1×10
995 55 0 | 1×8 9×1 17×9 35×19 18×8 1×8 8×1
996 55 0 | 1×8 8×1 16×9 33×21 17×8 1×7
997 55 0 | 1×8 8×1 16×8 33×21 17×9 1×7
998 55 0 | 1×10 11×1 21×11 43×12 22×10 1×10
999 55 0 | 1×10 11×1 21×10 43×12 22×11 1×10
1000 56 1 | 1×11 11×1 21×10 43×12 22×11 1×10
1001 56 1 | 1×11 11×1 22×10 45×11 23×11 1×11
1002 55 0 | 1×9 10×1 19×10 39×7 19×1 39×8 20×9 1×9
1003 55 0 | 1×9 10×1 19×10 39×7 20×1 39×8 20×9 1×9
1004 55 0 | 1×9 10×1 19×9 39×8 20×1 39×7 20×10 1×9
1005 55 0 | 1×8 9×1 17×9 35×9 18×1 35×10 18×8 1×8
1006 55 0 | 1×9 9×1 18×10 37×17 19×9 1×8
1007 55 0 | 1×9 9×1 18×9 37×17 19×10 1×8
1008 55 0 | 1×9 9×1 18×8 37×18 19×9 1×9
1009 56 1 | 1×10 9×1 18×8 37×18 19×9 1×9
1010 56 1 | 1×10 11×1 21×10 43×12 22×11 1×10 11×1
1011 56 1 | 1×9 9×1 18×10 37×17 19×9 1×8 5×1
1012 56 1 | 1×9 9×1 18×10 37×17 19×9 1×8 6×1
1013 56 1 | 1×9 9×1 18×10 37×17 19×9 1×8 7×1
1014 56 1 | 1×9 9×1 18×10 37×17 19×9 1×8 8×1
1015 56 1 | 1×9 9×1 18×10 37×17 19×9 1×8 9×1
1016 56 1 | 1×9 9×1 18×10 37×17 19×9 1×8 10×1
1017 56 1 | 1×9 9×1 18×9 37×17 19×10 1×8 10×1
1018 56 1 | 1×9 9×1 18×8 37×18 19×9 1×9 10×1
1019 56 1 | 1×9 10×1 18×8 37×18 19×9 1×9 10×1
1020 56 1 | 1×10 11×1 21×11 43×6 22×1 43×6 22×10 1×10
1021 56 1 | 1×9 10×1 19×12 39×15 20×9 1×9
1022 55 0 | 1×9 10×1 19×10 39×16 20×9 1×9
1023 55 0 | 1×9 10×1 19×9 39×16 20×10 1×9
1024 56 1 | 1×10 10×1 19×9 39×16 20×10 1×9
1025 56 1 | 1×9 10×1 19×10 39×16 20×9 1×9 3×1
1026 56 0 | 1×9 10×1 19×10 39×16 20×9 1×9 4×1
1027 56 0 | 1×9 10×1 19×10 39×16 20×9 1×9 5×1
1028 56 0 | 1×9 10×1 19×10 39×16 20×9 1×9 6×1
1029 56 0 | 1×8 8×1 16×9 33×22 17×8 1×7
1030 56 0 | 1×8 8×1 16×8 33×22 17×9 1×7
1031 56 0 | 1×8 8×1 16×7 33×23 17×8 1×8
1032 56 0 | 1×9 10×1 19×10 39×16 20×9 1×9 10×1
1033 56 0 | 1×10 10×1 20×11 41×14 21×10 1×9
1034 56 0 | 1×10 10×1 20×10 41×14 21×11 1×9
1035 56 0 | 1×10 10×1 20×9 41×15 21×10 1×10
1036 57 1 | 1×11 10×1 20×9 41×15 21×10 1×10
1037 57 1 | 1×10 10×1 20×11 41×14 21×10 1×9 4×1
1038 57 1 | 1×10 10×1 20×11 41×14 21×10 1×9 5×1
1039 56 0 | 1×8 9×1 17×9 35×10 17×1 35×10 18×8 1×8
1040 56 0 | 1×8 9×1 17×9 35×10 18×1 35×10 18×8 1×8
1041 56 0 | 1×10 11×1 21×11 43×13 22×10 1×10
1042 56 0 | 1×10 11×1 21×10 43×13 22×11 1×10
1043 56 0 | 1×9 9×1 18×10 37×18 19×9 1×8
1044 56 0 | 1×9 9×1 18×9 37×18 19×10 1×8
1045 56 0 | 1×9 9×1 18×8 37×19 19×9 1×9
1046 57 1 | 1×11 11×1 22×10 45×12 23×11 1×11
1047 57 1 | 1×10 11×1 20×9 41×15 21×10 1×10 11×1
1048 57 1 | 1×10 11×1 21×11 43×13 22×10 1×10 7×1
1049 57 1 | 1×10 11×1 21×11 43×13 22×10 1×10 8×1
1050 57 1 | 1×10 11×1 21×11 43×13 22×10 1×10 9×1
1051 57 1 | 1×10 11×1 21×11 43×13 22×10 1×10 10×1
1052 57 1 | 1×10 11×1 21×11 43×13 22×10 1×10 11×1
1053 57 1 | 1×10 11×1 21×10 43×13 22×11 1×10 11×1
1054 57 1 | 1×9 9×1 18×9 37×18 19×10 1×8 10×1
1055 57 1 | 1×9 9×1 18×8 37×19 19×9 1×9 10×1
1056 57 1 | 1×8 9×1 17×11 35×20 18×8 1×8
1057 56 0 | 1×8 9×1 17×9 35×21 18×8 1×8
1058 56 0 | 1×8 9×1 17×8 35×21 18×9 1×8
1059 57 1 | 1×9 9×1 17×8 35×21 18×9 1×8
1060 57 1 | 1×9 10×1 19×12 39×16 20×9 1×9
1061 56 0 | 1×9 10×1 19×10 39×17 20×9 1×9
1062 56 0 | 1×9 10×1 19×9 39×17 20×10 1×9
1063 57 1 | 1×10 10×1 19×9 39×17 20×10 1×9
1064 57 0 | 1×8 8×1 16×7 33×24 17×8 1×8
1065 57 0 | 1×9 10×1 19×10 39×17 20×9 1×9 4×1
1066 57 0 | 1×9 10×1 19×10 39×17 20×9 1×9 5×1
1067 57 0 | 1×9 10×1 19×10 39×17 20×9 1×9 6×1
1068 57 0 | 1×9 10×1 19×10 39×17 20×9 1×9 7×1
1069 57 0 | 1×9 10×1 19×10 39×17 20×9 1×9 8×1
1070 57 0 | 1×9 10×1 19×10 39×17 20×9 1×9 9×1
1071 57 0 | 1×9 10×1 19×10 39×17 20×9 1×9 10×1
1072 57 0 | 1×9 10×1 19×9 39×17 20×10 1×9 10×1
1073 58 1 | 1×10 10×1 20×13 41×14 21×10 1×9
1074 57 0 | 1×10 10×1 20×11 41×15 21×10 1×9
1075 57 0 | 1×10 10×1 20×10 41×15 21×11 1×9
1076 57 0 | 1×10 10×1 20×9 41×16 21×10 1×10
1077 58 1 | 1×11 10×1 20×9 41×16 21×10 1×10
1078 58 1 | 1×10 10×1 20×11 41×15 21×10 1×9 4×1
1079 58 1 | 1×9 9×1 18×12 37×18 19×9 1×8
1080 57 0 | 1×9 9×1 18×10 37×19 19×9 1×8
1081 57 0 | 1×9 9×1 18×9 37×19 19×10 1×8
1082 57 0 | 1×9 9×1 18×8 37×20 19×9 1×9
1083 58 1 | 1×10 9×1 18×8 37×20 19×9 1×9
1084 57 0 | 1×10 11×1 21×11 43×14 22×10 1×10
1085 57 0 | 1×10 11×1 21×10 43×14 22×11 1×10
1086 58 1 | 1×11 11×1 21×10 43×14 22×11 1×10
1087 58 1 | 1×10 10×1 20×9 41×16 21×10 1×10 11×1
1088 58 1 | 1×10 11×1 20×9 41×16 21×10 1×10 11×1
1089 58 1 | 1×11 11×1 22×12 45×12 23×11 1×10
1090 58 1 | 1×11 11×1 22×11 45×12 23×12 1×10
1091 58 1 | 1×11 11×1 22×10 45×13 23×11 1×11
1092 57 0 | 1×8 9×1 17×9 35×22 18×8 1×8
1093 57 0 | 1×8 9×1 17×8 35×22 18×9 1×8
1094 58 1 | 1×9 9×1 17×8 35×22 18×9 1×8
1095 58 1 | 1×8 8×1 16×9 33×24 17×8 1×7
1096 58 1 | 1×8 8×1 16×8 33×24 17×9 1×7
1097 58 1 | 1×8 8×1 16×7 33×25 17×8 1×8
1098 58 1 | 1×8 9×1 17×9 35×22 18×8 1×8 6×1
1099 58 1 | 1×9 10×1 19×12 39×17 20×9 1×9
1100 57 0 | 1×9 10×1 19×10 39×18 20×9 1×9

Answer 1

El complemento del grafo siguiente es un grafo agraciado de valencia 11 con 99 aristas y 18 vértices. Es probable que haya millones de grafos de este tipo, pero son difíciles de encontrar. Este definitivamente no es el más bonito de ellos. Un grafo de valencia 11 con 88 aristas es probadamente imposible por fuerza bruta.

El complemento del grafo siguiente es un grafo agraciado de valencia 13 con 130 aristas y 20 vértices. Es probable que haya millones de grafos de este tipo dentro de las 14189192868003840 posibilidades.

Un gráfico elegante con vértices mínimos suele tener valores de vértices que hacen un regla escasa . He reunido unas 10^6 reglas dispersas de una longitud de 1200. Lo siguiente da un límite superior a por lo menos bordes=1200.

Conjetura del Gráfico de Gracia: Cuando un grafo agraciado con $e$ bordes y $v$ tiene el mínimo de vértices posibles, entonces $v - \lceil \sqrt{3 \times e +9/4} \rfloor \in (0,1)$ y el conjunto de vértices es una regla dispersa.

Hasta la longitud 213 el valor es cero, excepto para las cuentas de borde 51, 59, 69, ... ( A308766 ) donde el valor es uno. Para el límite inferior, observaré que las reglas dispersas están muy relacionadas entre sí. La mayoría de las reglas dispersas pueden generar cientos de otras reglas dispersas de mayor y menor tamaño mediante operaciones sencillas. Si existiera un grafo/regla escasa con gracia para que $v - \lceil \sqrt{3 \times e +9/4} \rfloor = -1$ Probablemente generaría ondulaciones hacia valores más grandes y más pequeños. No se observan tales ondulaciones hasta la longitud 213.

John Leech ("On the "Representation of 1,2,...,n by Differences", J. of London Math Soc, April 1956) dio límites de $\sqrt{2.434 n}$ y $\sqrt{3.348 n}$ . Podemos comparar estos límites con los mejores valores reales conocidos ahora que los tenemos. Para los valores 51, 59, 69 su límite superior es demasiado bajo.

A algunas reglas dispersas se les puede quitar una marca interna y sólo perder un valor. Por ejemplo, $0, 1, 2, 3, 7, 13, 15, 24, 33, 42, 51, 60, 63, 67, 70$ se puede eliminar la marca del 3 para que sólo falte una diferencia de 64. De todas las miles de reglas dispersas que tengo con exceso 0, ninguna con longitud>70 tiene esta propiedad. ¿Existe alguna más? Muchas con exceso 1 tienen esta propiedad, como por ejemplo $0, 1, 3, 8, 9, 10, 17, 24, 37, 50, 63, 76, 89, 102, 115, 128, 134, 140, 145, 146, 149, 150$ que puede tener el 149 eliminado y sólo perder una diferencia de 148.

Si la valencia es par, el gráfico es Euleriano . Rosa 1967 "Sobre ciertas valoraciones de los vértices de un grafo" demostró que un grafo euleriano gracioso debe tener aristas (mod 4) $\in (0,3)$ . Basándonos en los datos de la regla dispersa y en este requisito de modulación, podemos hacer una cuadrícula de posibles grafismos con valencia uniforme. Los seis primeros se verifican arriba.

Para las valencias Impares no hay un requisito de módulo. A continuación se presentan algunos posibles gráficos graciosos con valencia impar. Los cinco primeros se verifican arriba.

Es posible que algunas de las reglas dispersas con longitud>213 y exceso 1 sean mejorables para tener exceso 0. Si esas reglas dispersas existen, eso abre los siguientes grafos graciosos potenciales.

Es posible que el grafo más pequeño con valencia $2 n$ tendrá $3 n^2$ bordes.

Si algunos de esos valores en exceso son realmente inmejorables, aquí hay algunos gráficos potenciales no basados en reglas dispersas que pueden rellenar los valores de valencia que faltan.

Según mis últimos resultados, el comportamiento de las valencias 4-37 debería ser el siguiente Vértices: {6, 8, 9, 10, 12, 14, 15, 18, 18, 20, 21, 24, 24, 26, 27, 30, 32, 32, 36, 36, 37, 38, 40, 42, 44, 44, 48, 48, 49, 50, 51, 54, 56, 56}
Bordes: {12, 20, 27, 35, 48, 63, 75, 99, 108, 130, 147, 180, 192, 221, 243, 285, 320, 336, 396, 414, 444, 475, 520, 567, 616, 638, 720, 744, 784, 825, 867, 945, 1008, 1036}

Un gráfico de aristas/valencia^2

Otro punto débil del problema es la suerte. Arriba doy los mínimos grafos posibles con valencias 2 a 10 y un grafo mínimo para la valencia 12. Para la valencia 7 el gráfico es único. Sólo hay cinco reglas dispersas de longitud 35 y cada una de ellas sólo puede generar unos cientos de grafos graciosos. Por suerte, exactamente uno de esos 2688 grafos tiene valencia 7.

La regla dispersa para la longitud 88 es única. Ninguno de los 53 millones de grafos gráciles que genera es 11-regular. El número de aristas tiene que ser divisible por 11, por lo que la solución tendrá 99 aristas y 18 vértices.

La cuestión de la suerte puede evaporarse para los pedidos superiores. Por ejemplo, resulta que la longitud 130 tiene exactamente 130 reglas dispersas con 20 marcas. Pueden producir 14189192868003840 gráficos elegantes. Para la longitud 147 sólo hay cinco reglas dispersas, pero hay muchas posibilidades de que uno de los 1775755607408640 grafos graciosos que generan tenga valencia 14.

Tengo algunos programas para tomar una regla / conjunto de vértices dispersos y encontrar un gráfico con ciertas propiedades, como el gráfico no regular de gracia que se muestra a continuación. Mis programas necesitan más velocidad para abordar las valencias más altas.

Answer 2

Este es un comentario extenso. El mensaje de recompensa de David Speyer tiene una bonita conjetura/pregunta pero parece que hay cierta confusión sobre el significado de $n$ así que tracé A308722 $(n)/n^2$ para $n=1,\ldots,16$ y esto es lo que vi:

Para aclarar la discusión, hay que tener en cuenta que aquí hay tres variables: el número de vértices, la valencia y el número de aristas. El ejemplo de Misha Lavrov de $K_{n,n}$ tiene $2n$ vértices, valencia $n$ y $n^2$ bordes. Así que asumo que el mensaje de recompensa de David Speyer se refiere a los límites de la función

$$ f(n) =\min\{v\in\mathbb N\colon \text{there exists a valence }n\text{ graceful graph with }v\text{ vertices}\}. $$