When Graphs Are a Matter of Life and Death