• A novel graph theory-based synthesis method for origami crease patterns is proposed, enabling systematic design rather than relying on intuition.
• The method generates 12 unique double symmetrical crease patterns via directed graph product operations and simplification techniques.
• An improved mixed-integer linear programming model automates the assignment of peak and valley creases, enhancing design efficiency.
• The approach expands the application potential of origami mechanisms in aerospace engineering and intelligent robotics, particularly for space debris capture.