Beauty-Elegance-Difficulty-Surprise

Surprise: in the context of the acyclic chromatic number of a graph there has already been work 50 years ago. Branko Gruenbaum had conjectured that for a planar graph the acyclic chromatic number is 5 or less. This had been proven by Borodin 5 years later. We actually had (without knowing about this) shown that except for prism graphs, one can go down to 4.

Difficulty: what is the reason that some problems are hard while others are difficult. A meta statement is that for easy problems, we often have a theorem. We can compute determinants fast because of row reduction, and this is lacking for permanents. For Eulerian paths, we have the Euler-Hierholzer theorem while for Hamiltonian paths we have nothing as such. For edge arboricity we have the Nash-Williams theorem while for vertex arboricity, we have no general theoretical result which allows to pinpoint the number.

Elegance: to illustrate elegance, one can look at the Gauss-Bonnet formula for the f-function of a finite simple graph G, where is the number of k-dimensional complete subgraphs of . Here is the 1 line code. What is nice about Mathematica is that the code is essentially self-explanatory (there is a theorem invoked which is not so obvious and which is linked in a natural way to very classical Gauss-Bonnet results in differential geometry. The following procedure is 133 characters and produces the generating function encoding the number of all complete subgraphs of G. It uses a General Gauss-Bonnet theorem developed for Dehn-Sommerville. (I added also an example on how to use the procedure for a random graph):

f[G_,t_]:=Module[{V=VertexList[G]},n=Length[V];1+Integrate[Sum[v=V[[k]];f[VertexDelete[NeighborhoodGraph[G,v],v],s],{k,n}],{s,0,t}]]
f[RandomGraph[{50,240}],t]

Beauty: the developments in the 4-color theorem is a good example to show how beauty can play a role too. If a problem in topology (regions in the plane) can be reformulated in a pure combinatorial manner using graphs, this is an idea which already Euler did when thinking about the Koenigsberg bridge problem. Regions in the plane can be messy. The boundary can have positive area. The intersection of two regions can have positive area. Without graph theory have to make assumptions which involve calculus like continuity or smoothness or invoke Euclidean geometry in order to make even the statement of the 4-color problem rigorous. It is much nicer to be in a purely combinatorial setting. One can reduce the problem to coloring 2-spheres which are finite simple graphs for which every unit sphere is a circular graph with 4 or more elements. This is Whitney’s theorem: a maximally planar 4-connected graph is either K4 or a 2-sphere. The idea of Fisk to go into higher dimensions reduces the 4-color problem into a constructive task. See this presentation from 2014 and this paper from 2014.