Network structure is a mechanism for promoting cooperation in social dilemma games. In the present study, we explore graph surgery, i.e., to slightly perturb the given network, towards a network that better fosters cooperation. To this end, we develop a perturbation theory to assess the change in the propensity of cooperation when we add or remove a single edge to/from the given network. Our perturbation theory is for a previously proposed random-walk-based theory that provides the threshold benefit-to-cost ratio,\documentclass[12pt]{minimal}
				\usepackage{amsmath}
				\usepackage{wasysym} 
				\usepackage{amsfonts} 
				\usepackage{amssymb} 
				\usepackage{amsbsy}
				\usepackage{mathrsfs}
				\usepackage{upgreek}
				\setlength{\oddsidemargin}{-69pt}
				\begin{document}$$(b/c)^*$$\end{document}(b/c)∗, which is the value of the benefit-to-cost ratio in the donation game above which the cooperator is more likely to fixate than in a control case, for any finite networks. We find that\documentclass[12pt]{minimal}
				\usepackage{amsmath}
				\usepackage{wasysym} 
				\usepackage{amsfonts} 
				\usepackage{amssymb} 
				\usepackage{amsbsy}
				\usepackage{mathrsfs}
				\usepackage{upgreek}
				\setlength{\oddsidemargin}{-69pt}
				\begin{document}$$(b/c)^*$$\end{document}(b/c)∗decreases when we remove a single edge in a majority of cases and that our perturbation theory captures at a reasonable accuracy which edge removal makes\documentclass[12pt]{minimal}
				\usepackage{amsmath}
				\usepackage{wasysym} 
				\usepackage{amsfonts} 
				\usepackage{amssymb} 
				\usepackage{amsbsy}
				\usepackage{mathrsfs}
				\usepackage{upgreek}
				\setlength{\oddsidemargin}{-69pt}
				\begin{document}$$(b/c)^*$$\end{document}(b/c)∗small to facilitate cooperation. In contrast,\documentclass[12pt]{minimal}
				\usepackage{amsmath}
				\usepackage{wasysym} 
				\usepackage{amsfonts} 
				\usepackage{amssymb} 
				\usepackage{amsbsy}
				\usepackage{mathrsfs}
				\usepackage{upgreek}
				\setlength{\oddsidemargin}{-69pt}
				\begin{document}$$(b/c)^*$$\end{document}(b/c)∗tends to increase when we add an edge, and the perturbation theory is not good at predicting the edge addition that changes\documentclass[12pt]{minimal}
				\usepackage{amsmath}
				\usepackage{wasysym} 
				\usepackage{amsfonts} 
				\usepackage{amssymb} 
				\usepackage{amsbsy}
				\usepackage{mathrsfs}
				\usepackage{upgreek}
				\setlength{\oddsidemargin}{-69pt}
				\begin{document}$$(b/c)^*$$\end{document}(b/c)∗by a large amount. Our perturbation theory significantly reduces the computational complexity for calculating the outcome of graph surgery.