This is a bit of a continuation from a previous video about Lusternik-Schnirelmann and Morse. I would like to have this chapter as elegant as possible. As for the video, there is a bit of overlap with a previous video on this from the fall, when I circled back to this topic triggered by the passing of Frank Josellis in 2022. Lusternik-Schnirelmann theory is a parallel theory to Morse theory. Both theories can be effectively incarnated within graph theory. A key notion in both theories is contractibitily. A graph G is called contractible, if there exists a vertex such that both the unit sphere S(x) and the graph G – x without x are contractible. [ My standard rant about this: Both in Lusternik and Schnirelmann (with Frank) and Morse theory, I always used “contractible” what sometimes is called “collapsible” and call “homotopic to 1” the wider equivalence relation among graphs. The notion “homotopic to one” is from the computer science point of view a very hard notion: it can be very costly (even undecidable with a Turing machine) to decide whether two graphs are homotopic to each other, while contractibility is more straight forward. ]
In Morse theory, contracibility is important when defining what a k-sphere is. This in turn is a pivotal notion, when defining Morse functions. It looks like a very restrictive notion but every simplicial complex defines a graph ( pairs of simplices are connected if one is contained in the other), for which the natural function building up the complex is always a Morse function. When adding an even dimensional k-simplex, the Morse index is (k-1) since the boundary of a k-simplex is a (k-1) sphere.
In Lusternik-Schnirelmann theory, contractibility enters in a more basic manner. We look how many contractible subgraphs we need to cover the graph. If the graph is contractible, then the category is one and the homotopy build-up shows that there are functions with exactly one critical point (the minimum, because the empty graph is not contractible). If we have a graph of category 1, then for any function, the minimal value of the complement of a maximal subgraph of category 1 is a critical point because if it were not, then we could extend the subgraph contradicting maximality. The difficulty I battle with is that the proof in the continuum goes over to the discrete. Take a maximal subgraph S of category k. The claim is that for any function, the minimum of f on the complement of S is a critical point. If k is larger than 2, I can no more simply conclude that this is a critical point. We know that all contractible parts of S in the L-S cover can not be extended, but this does not mean that S can not be extended. It boils down essentially to show that the minimal number of critical points does not change under a homotopy deformation. In the talk, I simply bypassed the difficulty by only allowing functions f for which the difficulty does not exist. This is a mild condition and not unreasonable as in Morse theory we also have to restrict the functions. But it would be nice if we do not need that condition.
Here is an other take to the problem. Assume we have a locally injective function f on a graph G and that there are k critical points in the sense that 
