Discrete mathematics Created 2026-10-31 Updated 2026-11-05
Discrete mathematics studies structures built from distinct objects and finite or countable choices. Its main connections include combinatorics, graph theory, number theory, mathematical logic and the analysis of algorithms. The distinction concerns the structures under study, rather than a ban on using real numbers or analysis in proofs.
For example, a graph with vertices has possible unordered edges when loops and repeated edges are excluded. Counting possible edge sets gives labeled simple graphs. A small modeling assumption about allowed edges has turned a structural question into an exact counting formula. Such translations underpin scheduling, networks and computer science.
Edge set 2026-10-31
The set of edges of a specified graph. In a simple graph, an edge is determined by its endpoints; a multigraph additionally distinguishes parallel edges with the same endpoints. A subgraph can be specified by selecting a vertex set and an edge set whose endpoints belong to it.
Edge set respecting a cut 2026-10-31
An edge set respects a cut of a graph when none of its edges crosses that cut. In the minimum spanning tree cut property, this guarantees that exchanging a crossing tree edge cannot remove an edge already committed to the partial solution.
A complete three-uniform hypergraph on four vertices has four edges. In the binomial random hypergraph , its count has mean . If , the first moment method gives . Two distinct four-sets have independent clique indicators unless they share three vertices; in that case their combined edge set has seven triples. There are such ordered pairs, so . Consequently if . The second moment method then gives . These two implications establish the threshold function.
Hypergraph chromatic index Created 2026-10-14 Updated 2026-11-05
The chromatic index of a hypergraph is the minimum number of colours needed to colour its edges so that intersecting edges have different colours. Each colour class is a matching in a hypergraph. It is at least the maximum hypergraph vertex degree, and, when the edge set is nonempty, at most for an -uniform hypergraph of maximum degree , by greedily colouring edges: an edge meets at most others.
Past exam of the integer programming course of the University of Oxford 2011 1 a Solution 2026-10-31
Use vertices . Reading each symmetric off-diagonal pair once gives the edge setHere abbreviates the undirected edge . The diagram displays these seven edges and no loops. The displayed square matrix is an adjacency matrix in the usual terminology: its two indices both label vertices. A vertex-edge incidence matrix would instead have one index for vertices and one for edges. This explains how the source's node-node terminology is being read.
