#math #combinatorics #graphtheory
For a graph with n vertices and m edges, when m is small enough, it is possible to keep the graph triangle free, up to a threshold value of m. Just 1 above the threshold, the graph will suddenly be guaranteed to have a minimum of floor(n/2) triangles! This phenomenon is an illustration of supersaturation, and there is a more general statement for arbitrary subgraphs.
Do you know these graph theory terms: bipartite graph, path, tree, spanning tree, Eulerian, Hamiltonian, cycle, circuit, tournament, directed graph, subgraph, induced subgraph, complete graph, Hall's marriage theorem, matching, handshaking lemma
