n(n-1)/2

n(n-1)/2 - r(r-1)/2

n(n-1)/2 + r(r-1)/2

n(n-1)/2 - r(r+1)/2

The smallest integer n such that every graph on n vertices contains either a complete subgraph of order r or an independent set of order s.

The smallest integer n such that every graph on n vertices contains either a complete subgraph of order r or a clique of order s.

The smallest integer n such that every graph on n vertices contains either a complete subgraph of order r or a cycle of order s.

The smallest integer n such that every graph on n vertices contains either a complete subgraph of order r or a path of order s.

A theorem that characterizes the graphs with the maximum number of edges among all graphs with a given number of vertices and no induced subgraph isomorphic to a given graph.

A theorem that characterizes the graphs with the minimum number of edges among all graphs with a given number of vertices and no induced subgraph isomorphic to a given graph.

A theorem that characterizes the graphs with the maximum number of vertices among all graphs with a given number of edges and no induced subgraph isomorphic to a given graph.

A theorem that characterizes the graphs with the minimum number of vertices among all graphs with a given number of edges and no induced subgraph isomorphic to a given graph.

A theorem that states that every graph with n vertices and at least n/2 edges contains a cycle.

A theorem that states that every graph with n vertices and at least n/2 edges contains a Hamiltonian cycle.

A theorem that states that every graph with n vertices and at least n/2 edges contains a path of length n.

A theorem that states that every graph with n vertices and at least n/2 edges contains a tree of order n.

A theorem that states that the maximum number of edges in a triangle-free graph on n vertices is 3n/2.

A theorem that states that the maximum number of edges in a triangle-free graph on n vertices is 2n.

A theorem that states that the maximum number of edges in a triangle-free graph on n vertices is n(n-1)/2.

A theorem that states that the maximum number of edges in a triangle-free graph on n vertices is n(n+1)/2.

A theorem that states that every graph with n vertices and at least cn^2 edges contains a clique of order at least cn.

A theorem that states that every graph with n vertices and at least cn^2 edges contains an independent set of order at least cn.

A theorem that states that every graph with n vertices and at least cn^2 edges contains a cycle of length at least cn.

A theorem that states that every graph with n vertices and at least cn^2 edges contains a path of length at least cn.

A theorem that states that the maximum number of pairwise disjoint sets that can be chosen from an n-set is (n choose k).

A theorem that states that the maximum number of pairwise disjoint sets that can be chosen from an n-set is (n choose k) - 1.

A theorem that states that the maximum number of pairwise disjoint sets that can be chosen from an n-set is (n choose k) + 1.

A theorem that states that the maximum number of pairwise disjoint sets that can be chosen from an n-set is (n choose k) / 2.

A conjecture that states that every graph with n vertices and at least 3n/2 edges contains a Hamiltonian cycle.

A conjecture that states that every graph with n vertices and at least 3n/2 edges contains a cycle of length at least n.

A conjecture that states that every graph with n vertices and at least 3n/2 edges contains a path of length at least n.

A conjecture that states that every graph with n vertices and at least 3n/2 edges contains a tree of order n.

A conjecture that states that every graph with n vertices and at least cn^2 edges contains a clique of order at least cn.

A conjecture that states that every graph with n vertices and at least cn^2 edges contains an independent set of order at least cn.

A conjecture that states that every graph with n vertices and at least cn^2 edges contains a cycle of length at least cn.

A conjecture that states that every graph with n vertices and at least cn^2 edges contains a path of length at least cn.

A lemma that states that if a collection of events in a probability space are mutually independent, then the probability that at least one of them occurs is at most the sum of their probabilities.

A lemma that states that if a collection of events in a probability space are mutually independent, then the probability that at least one of them occurs is at least the sum of their probabilities.

A lemma that states that if a collection of events in a probability space are mutually independent, then the probability that at least one of them occurs is equal to the sum of their probabilities.

A lemma that states that if a collection of events in a probability space are mutually independent, then the probability that at least one of them occurs is less than the sum of their probabilities.

An inequality that states that for any graph G with n vertices and m edges, the probability that a random subgraph of G with k vertices contains a cycle is at most (m choose k) / (n choose k).

An inequality that states that for any graph G with n vertices and m edges, the probability that a random subgraph of G with k vertices contains a cycle is at least (m choose k) / (n choose k).

An inequality that states that for any graph G with n vertices and m edges, the probability that a random subgraph of G with k vertices contains a cycle is equal to (m choose k) / (n choose k).

An inequality that states that for any graph G with n vertices and m edges, the probability that a random subgraph of G with k vertices contains a cycle is less than (m choose k) / (n choose k).

A theorem that states that the maximum number of edges in a graph with n vertices and no induced subgraph isomorphic to a given graph is at most cn^2.

A theorem that states that the maximum number of edges in a graph with n vertices and no induced subgraph isomorphic to a given graph is at least cn^2.

A theorem that states that the maximum number of edges in a graph with n vertices and no induced subgraph isomorphic to a given graph is equal to cn^2.

A theorem that states that the maximum number of edges in a graph with n vertices and no induced subgraph isomorphic to a given graph is less than cn^2.

A theorem that states that every graph with n vertices and at least cn^2 edges contains a clique of order at least cn.

A theorem that states that every graph with n vertices and at least cn^2 edges contains an independent set of order at least cn.

A theorem that states that every graph with n vertices and at least cn^2 edges contains a cycle of length at least cn.

A theorem that states that every graph with n vertices and at least cn^2 edges contains a path of length at least cn.

A random graph model where each edge is present with probability p, independently of all other edges.

A random graph model where each edge is present with probability p, dependent on all other edges.

A random graph model where each edge is present with probability p, dependent on some other edges.

A random graph model where each edge is present with probability p, independent of some other edges.