mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, a simple subcubic graph (SSCG) is a finite simple

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

in which each vertex has a degree of at most three. Suppose we have a sequence of simple subcubic graphs ''G''₁, ''G''₂, ... such that each graph ''G''_''i'' has at most ''i'' + ''k'' vertices (for some integer ''k'') and for no ''i'' < ''j'' is ''G''_''i'' homeomorphically embeddable into (i.e. is a

graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges, vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...

of) ''G''_''j''. The

Robertson–Seymour theorem In graph theory, the Robertson–Seymour theorem (also called the graph minors theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is ...

proves that subcubic graphs (simple or not) are well-founded by homeomorphic embeddability, implying such a sequence cannot be infinite. Then, by applying

Kőnig's lemma Kőnig's lemma or Kőnig's infinity lemma is a theorem in graph theory due to the Hungarian mathematician Dénes Kőnig who published it in 1927. It gives a sufficient condition for an infinite graph to have an infinitely long path. The computab ...

on the tree of such sequences under extension, for each value of ''k'' there is a sequence with maximal length. The function SSCG(''k'') denotes that length for simple subcubic graphs. The function SCG(''k'') denotes that length for (general) subcubic graphs. Adam P. Goucher claims there is no qualitative difference between the asymptotic growth rates of SSCG and SCG. He writes "It's clear that SCG(''n'') ≥ SSCG(''n''), but I can also prove SSCG(4''n'' + 3) ≥ SCG(''n'')."TREE(3) and impartial games , Complex Projective 4-Space
/ref> The function was proposed and studied by Harvey Friedman.

References

{{DEFAULTSORT:Friedman's SSCG function Mathematical logic Theorems in discrete mathematics Order theory Wellfoundedness Graph theory

See also

References