Discrete Mathematics Glossary

$\binom{n}{k}$, the number of ways to choose $k$ items from $n$, equal to $\frac{n!}{k!(n-k)!}$.

A graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to one in the other.

A variable that can take only two values: true (1) or false (0).

The minimum number of colors needed to properly color the vertices of a graph.

An explicit formula for the $n$th term of a sequence, derived from solving a recurrence relation.

An unordered selection of objects from a set, where order does not matter.

A compound proposition that is false regardless of the truth values of its individual components.

The number of edges incident to a vertex. In a directed graph, in-degree and out-degree are counted separately.

A graph in which edges have a direction, going from one vertex to another.

A structure $G = (V, E)$ consisting of vertices $V$ and edges $E$ representing connections between vertices.

The largest positive integer that divides two or more integers without a remainder.

A function where distinct inputs always map to distinct outputs (one-to-one).

A structure-preserving bijection between two graphs (or other algebraic structures).

The divisor in modular arithmetic. In $a \equiv b \pmod{m}$, $m$ is the modulus.

An ordered arrangement of distinct objects from a set.

A statement containing variables that becomes a proposition when specific values are assigned to those variables.

A declarative statement that is either true or false, but not both.

A symbol indicating the scope of a variable: universal ($\forall$, for all) or existential ($\exists$, there exists).

An equation that defines each term of a sequence as a function of preceding terms.

An unordered collection of distinct objects, called elements or members.

A subgraph that includes all vertices of the original graph and is a tree (connected, acyclic).

Set $A$ is a subset of set $B$ if every element of $A$ is also in $B$, written $A \subseteq B$.

A function where every element in the codomain is mapped to by at least one element in the domain (onto).

A compound proposition that is true regardless of the truth values of its individual components.

A table showing all possible truth values of a logical expression for every combination of its variables.