Intersection number (graph theory)¶

The minimum ground-set size needed to represent a graph as intersections among finite vertex-associated sets, equivalently its minimum edge-clique cover size.

Version: v2 · 2026-09-19 · History
Domain-specific #: 5088
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Graph Theory → Mathematics

Core Idea¶

Each vertex receives a subset of a finite universe and two vertices are adjacent exactly when their subsets intersect; minimizing universe elements equals minimizing cliques whose union covers every edge. Each universe element induces a clique of vertices containing it, and conversely each edge-covering clique can be encoded as one shared element, establishing the equivalence. The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

How would you explain it like I'm…

Fewest Friendship Stickers

Picture a drawing of kids where a line joins every pair of friends. Give each kid some colored stickers so that two kids share a sticker color exactly when they are friends. Kids who are not friends must not share any color. The fewest sticker colors you can do this with is the Intersection number.

Fewest Shared Labels

Start with a graph of dots and lines. Give each dot a little bag of labels taken from one shared pile of label kinds. The rule is that two dots must share a label if they are connected by a line, and must share nothing if they are not. The intersection number is the fewest label kinds that can do the job. There is another way to see it. Each label kind marks a group of dots that are all connected to one another, and you need enough such groups to cover every line.

Minimum Set-Intersection Representation

The intersection number of a graph is the smallest size of a universe of elements that lets you represent the graph this way: - each vertex gets a subset of the universe; - two vertices are adjacent exactly when their subsets intersect. This equals the minimum number of cliques needed to cover every edge. The equivalence works in both directions. The vertices containing a given element are pairwise adjacent, so they form a clique. Conversely, each clique in a covering can be encoded as one shared element given to all of its vertices. You also have to state how you treat isolated vertices, since they have no edges to cover.

The Intersection number of a graph G is the minimum size of a ground set U for which there is an assignment v ↦ S_v ⊆ U with uv ∈ E exactly when S_u ∩ S_v ≠ ∅. It equals the edge clique cover number: the fewest cliques whose union covers every edge. The proof works in both directions. Each element x ∈ U defines a clique {v : x ∈ S_v}, and these cliques cover all edges. Conversely, given an edge clique cover, assign one fresh element per clique to all of its vertices. Both conditions are load-bearing. Adjacency must be exactly nonempty intersection, not merely implied by it, and the ground set must be minimal. Isolated vertices need a stated convention, such as giving them empty sets or a private element, because conventions differ.

Scope of Application¶

Intersection number (graph theory) belongs to graph theory and is useful where the analyst can specify the typed graph theory carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets, then evaluate adjacency is exactly nonempty set intersection and the ground-set size is minimal, with isolated-vertex conventions stated. The scope is broad within that domain but bounded by the need for adjacency is exactly nonempty set intersection and the ground-set size is minimal, with isolated-vertex conventions stated. The entry records a descriptive analytical identity; practical use requires the governing domain's evidence, standards, and safety obligations.

Clarity¶

The abstraction clarifies a crowded vocabulary by making adjacency is exactly nonempty set intersection and the ground-set size is minimal, with isolated-vertex conventions stated the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test. A bare label is insufficient because the name Intersection number (graph theory) can be used for a formal identity, an implementation, or a neighboring result unless carrier and convention are stated.

Manages Complexity¶

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to Intersection number (graph theory). Intersection number (graph theory) compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

Abstract Reasoning¶

Identify the carrier. State what the elements, states, objects, or observations are: the typed graph theory carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets. Reject examples whose alleged carrier belongs to a different problem.
Lock the constitutive rule. Express adjacency is exactly nonempty set intersection and the ground-set size is minimal, with isolated-vertex conventions stated independently of one notation or implementation.

Knowledge Transfer¶

Knowledge transfers strongly among subfields of graph theory because they reuse the typed graph theory carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets, Each universe element induces a clique of vertices containing it, and conversely each edge-covering clique can be encoded as one shared element, establishing the equivalence., and type the carrier, state every parameter and convention in the definition, test that adjacency is exactly nonempty set intersection and the ground-set size is minimal, with isolated-vertex conventions stated, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions¶

Current abstraction Intersection number (graph theory) Domain-specific

Parents (1) — outgoing typed relations

Intersection number (graph theory) is a kind of Representation Prime

What makes it its own entry: the domain-specific identity determined by adjacency is exactly nonempty set intersection and the ground-set size is minimal, with isolated-vertex conventions stated.

Hierarchy path (1) — routes to 1 parentless root

Intersection number (graph theory) → is a kind of Representation → presupposes Abstraction

Neighborhood in Abstraction Space¶

Intersection number (graph theory) sits in a crowded region of the domain-specific corpus (0^th percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Graph Theory Structures & Invariants (48 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25