Lights Out on a Random Graph

  • Bradley Forrest Stockton University
  • Nicole Manno University of Delaware
Keywords: Lights Out; random graph; Monte Carlo


We consider the generalized game Lights Out played on a graph and investigate the following question: for a given positive integer n, what is the probability that a graph chosen uniformly at random from the set of graphs with n vertices yields a universally solvable game of Lights Out? When n ≤ 11, we compute this probability exactly by determining if the game is universally solvable for each graph with n vertices. We approximate this probability for each positive integer n with n ≤ 87 by applying a Monte Carlo method using 1,000,000 trials. We also perform the analogous computations for connected graphs.

How to Cite
Forrest, B., & Manno, N. (2022). Lights Out on a Random Graph. The PUMP Journal of Undergraduate Research, 5, 165-175. Retrieved from