# Graceful graphs with Valence $k$

For a graceful graph ( code ), vertices are labeled with values from 0 to $$e$$ so that the $$e$$ edge differences are all values from 1 to $$e$$.
The below is now OEIS sequence A308722.
$$K_3$$ is the minimal valence 2 graph with $$e=3$$.
$$K_4$$ is the minimal valence 3 graph with $$e=6$$.
$$O$$ is the minimal valence 4 graph with $$e=12$$.

The minimal graceful graph with valence 5 has $$e=20$$.

The minimal graceful graph with valence 6 has $$e=27$$.

The minimal graceful graph for valence 7 has $$e=35$$. It is unique.

What are minimal graceful graphs with valence 8 and up? These are heavily related to sparse rulers. My guess for future behavior is:
e=48 with 12 vertices of valence 8. (verified this one)

e=63 with 14 vertices of valence 9. Verified. The graph complement of the following is graceful.

Or in the more normal form

e=75 with 15 vertices of valence 10. Verified. There are 37 such graphs. The graph complement of the following is graceful.

e=99 with 18 vertices of valence 11. (e=88 proved impossible). Verified.

e=108 with 18 vertices of valence 12. Verified. The graph complement of the following is graceful.

e=130 with 20 vertices of valence 13. Verified.
e=147 with 21 vertices of valence 14.
e=180 with 24 vertices of valence 15.
e=192 with 24 vertices of valence 16.
e=221 with 26 vertices of valence 17.
e=243 with 27 vertices of valence 18.
e=285 with 30 vertices of valence 19.
e=320 with 32 vertices of valence 20.
e=336 with 32 vertices of valence 21.

Many of these graceful graphs are based on data obtained for the Sparse Ruler Conjecture. That page lists sample sparse rulers to length 600. Here are lengths 601 to 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

• For an upper bound, $K_{n,n}$ is a graceful $n$-regular graph with $n^2$ edges. – Misha Lavrov May 31 at 15:56
• Some authors require the labels of the vertices to be 0 to $e$. Am I correct in thinking that you don't? Or is there a theorem showing that this holds automatically? – Peter Taylor Jun 4 at 6:55
• Peter Taylor -- yes. I edited to add that requirement. – Ed Pegg Jun 4 at 16:18

The graph complement of the following is a graceful graph of valence 11 with 99 edges and 18 vertices. There are likely millions of such graphs, but they are hard to find. This definitely isn't the prettiest of them. A valence 11 graph with 88 edges is provably impossible by brute force.

The graph complement of the following is a graceful graph of valence 13 with 130 edges and 20 vertices. There are likely millions of such graphs within the 14189192868003840 possibilities.

A graceful graph with minimal vertices usually has vertex values that make a sparse ruler. I've collected about 10^6 sparse rulers to length 1200. The following gives an upper bound to at least edges=1200.

Graceful Graph Conjecture: When a graceful graph with $$e$$ edges and $$v$$ vertices has the minimum possible vertices, then $$v - \lceil \sqrt{3 \times e +9/4} \rfloor \in (0,1)$$ and the vertex set is a sparse ruler.

Up to length 213 the value is zero except for edgecounts 51, 59, 69, ... ( A308766) where the value is one. For the lower bound I'll note that sparse rulers are heavily related to each other. Most sparse rulers can generate hundreds of other sparse rulers of larger and smaller sizes through simple operations. If a graceful graph / sparse ruler existed so that $$v - \lceil \sqrt{3 \times e +9/4} \rfloor = -1$$, it would likely generate ripples to larger and smaller values. No such ripples are seen up to length 213.

John Leech ("On the "Representation of 1,2,...,n by Differences", J. of London Math Soc, April 1956) gave bounds of $$\sqrt{2.434 n}$$ and $$\sqrt{3.348 n}$$. We can compare these bounds to best known actual values now that we have them. For values 51, 59, 69 his upper bound is too low.

Some sparse rulers can have one internal mark removed and only miss a single value. For example, $$0, 1, 2, 3, 7, 13, 15, 24, 33, 42, 51, 60, 63, 67, 70$$ can have the mark at 3 removed so that only a difference of 64 is missing. From all of the thousands of sparse rulers I have with excess 0, none of them with length>70 has this property. Do any more exist? Many with excess 1 have this property, such as $$0, 1, 3, 8, 9, 10, 17, 24, 37, 50, 63, 76, 89, 102, 115, 128, 134, 140, 145, 146, 149, 150$$ which can have the 149 removed and only miss a difference of 148.

If the valence is even, the graph is Eulerian. Rosa 1967 "On Certain Valuations of the Vertices of a Graph" proved that an Eulerian graceful graph must have edges (mod 4) $$\in (0,3)$$. Based on sparse ruler data and this mod requirement we can make a grid of potential graceful graphs with even valence. The first six of these are verified above.

For odd valences there isn't a modulus requirement. Here are some potential graceful graphs with odd valence. The first five of these are verified above.

It is possible that some of the sparse rulers with length>213 and excess 1 are improvable to have excess 0. If those sparse rulers exist, that opens up the following potential graceful graphs.

It's possible that the smallest graceful graph with valence $$2 n$$ will have $$3 n^2$$ edges.

If some of those excess values really are unimprovable here are some potential graphs not based on sparse rulers that can fill in missing valence values.

Based on my latest results behavior for valences 4-37 should be as follows: Vertices: {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}
Edges: {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}

A plot of edges/valence^2

Another foible in the problem is luck. Above I give the minimal possible graceful graphs with valences 2 to 10 and a minimal graph for valence 12. For valence 7 the graph is unique. There are only five sparse rulers of length 35 and each can only generate a few hundred graceful graphs. By the luck of the draw, exactly one of those 2688 graphs had valence 7.

The sparse ruler for length 88 is unique. None of the 53 million graceful graphs it generates is 11-regular. The number of edges needs to divisible by 11, so the solution will have 99 edges and 18 vertices.

The luck issue may evaporate for higher orders. For example, length 130 happens to have exactly 130 sparse rulers with 20 marks. They can produce 14189192868003840 graceful graphs. For length 147 there are only five sparse rulers, but chances are good that one of the 1775755607408640 graceful graphs they generate has valence 14.

I have a few programs for taking a sparse ruler / vertex set and finding a graph with certain properties, such as the non-regular graceful graph below. My programs need further speed-ups to tackle the higher valences.

This is an extended comment. David Speyer's bounty message has a nice conjecture/question but there seems to be some confusion about the meaning of $$n$$, so I plotted A308722$$(n)/n^2$$ for $$n=1,\ldots,16$$ and this is what I saw:

To clarify the discussion, note there are three variables here: the number of vertices, the valence, and the number of edges. Misha Lavrov's example of $$K_{n,n}$$ has $$2n$$ vertices, valence $$n$$, and $$n^2$$ edges. So I assume that David Speyer's bounty message is referring to bounds on the function

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

• The three variables are related: If we have $n$ vertices, valence $d$ and $e$ edges, then $2e=dn$. – David E Speyer Jul 16 at 10:17
• Yep. Looks like the smallest graceful graph with valence $2 n$ will have $3 n^2$ edges. The graceful graphs of odd valence are weirder. I've learned to trust weird patterns, so I'm thinking a sparse ruler of length 300 and excess 0 exists even though I haven't found it yet. – Ed Pegg Jul 16 at 12:46
• @EdPegg I see you liked my plot enough to add an extended version of it to your answer! – pre-kidney Jul 19 at 5:15