Block Graph¶

is a type of undirected graph in which every biconnected component (block) is a clique.

Version: v1 · 2026-09-28 · History
Domain-specific #: 8228
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Graph Theory → Mathematics

Core Idea¶

Block Graph is treated here as the recurring mathematics, logic, and statistics identity summarized by this source-grounded definition: is a type of undirected graph in which every biconnected component (block) is a clique. In graph theory, a branch of combinatorial mathematics, a block graph or clique tree. is a type of undirected graph in which every biconnected component (block) is a clique. Block graphs are sometimes erroneously called Husimi trees (after Kôdi Husimi), but that name more properly refers to cactus graphs, graphs in which every nontrivial biconnected component is a cycle.

How would you explain it like I'm…

Tree of Dot Clumps

Draw some dots and connect some of them with lines. In a block graph, the dots come in clumps where every dot in a clump is connected to every other dot in that clump. Clumps can only touch each other at a single shared dot, and they never make a big loop, so it branches like a tree made of clumps.

Clumps of All-Connected Dots

A graph is a drawing of dots (vertices) joined by lines (edges). A block of a graph is a biggest possible piece that stays connected even if you remove any one dot from it. In a block graph, every block is a clique, which means every dot in it is joined to every other dot in it. The blocks are joined together only at single dots, like beads touching at one point, and they are arranged like a tree with no loops of blocks. A nice fact: in a connected block graph, between any two dots there is exactly one path that doesn't use any shortcuts.

Graphs Whose Blocks Are Cliques

A block graph (also called a clique tree) is an undirected graph in which every biconnected component, or block, is a clique, meaning all its vertices are pairwise adjacent. A block is a maximal piece of the graph that cannot be disconnected by deleting one vertex, and blocks meet only at cut vertices. So a block graph looks like complete graphs glued together at single vertices in a tree-like pattern. An equivalent description is that connected block graphs are exactly the graphs in which each pair of vertices is joined by a unique induced path. Block graphs are sometimes wrongly called Husimi trees; that name more properly belongs to cactus graphs, where every nontrivial block is a cycle instead of a clique.

A block graph, or clique tree, is an undirected graph whose every biconnected component (block) induces a clique. Since the blocks of any graph intersect only in cut vertices and form a tree-like block-cut structure, a connected block graph is a tree of cliques glued at cut vertices. Block graphs are exactly the intersection graphs of the blocks of arbitrary undirected graphs. Two further characterizations follow: the connected block graphs are exactly the graphs in which every pair of vertices is joined by a unique induced path, and the connected vertex subsets of a connected block graph form a convex geometry, a property that holds for no graph that is not a block graph. The name Husimi tree is sometimes misapplied to block graphs but properly denotes cactus graphs, in which every nontrivial block is a cycle; the clique condition on blocks is what identifies a block graph.

Scope of Application¶

Related graph classes. Line graphs of trees have been used to find graphs with a given number of edges and vertices in which the largest induced subgraph that is a tree is as small.
Related graph classes. Since triangular cactus graphs are planar graphs, the largest triangular cactus can be used as an approximation to the largest planar subgraph, an important subproblem in planarization.
Related graph classes. As an approximation algorithm, this method has approximation ratio 4/9, the best known for the maximum planar subgraph problem.
Characterization. Block graphs are exactly the graphs for which, for every four vertices , , , and , the largest two of the three distances ,.
Characterization. They also have a forbidden graph characterization as the graphs that do not have the diamond graph or a cycle of four or more vertices as an induced subgraph; that is.

Clarity¶

A clear use of Block Graph names the carrier, the operative relation, and the conditions under which the source treats the identity as present. The minimal definition is is a type of undirected graph in which every biconnected component (block) is a clique. The strongest recognition evidence in the frozen account is: They also have a forbidden graph characterization as the graphs that do not have the diamond graph or.

Manages Complexity¶

Block Graph compresses multiple mathematics, logic, and statistics details into a stable diagnostic relation. The source shows both the central mechanism—they are also the Ptolemaic graphs (chordal distance-hereditary graphs) in which every two nodes at distance two from each other are connected by a unique shortest path, and the chordal graphs in which every two maximal cliques have at most one vertex in common.—and the practical consequence—therefore.

Abstract Reasoning¶

Type the carrier. Identify the mathematics, logic, and statistics entities to which the claim applies.
State the relation. Use the source-grounded identity: is a type of undirected graph in which every biconnected component (block) is a clique.
Check operation and conditions. Block graphs are exactly the graphs for which, for every four vertices , , , and , the largest two of the three distances ,.
Demand recognition evidence.

Knowledge Transfer¶

Within the home domain. Knowledge about Block Graph transfers literally when a new case preserves the same carrier type, relation, and recognition test. Line graphs of trees have been used to find graphs with a given number of edges and vertices in which the largest induced subgraph that is a tree is as small as possible. Since triangular cactus graphs are planar graphs, the largest triangular cactus can be used as an approximation to the largest planar subgraph, an important subproblem in planarization.

Relationships to Other Abstractions¶

Current abstraction Block Graph Domain-specific

Parents (1) — more general patterns this builds on

Block Graph is a kind of Network Prime

Block Graph is a domain-specific kind of graph under its frozen identity and differentia. Complete-catalog comparison found the corresponding live broader identity.

Hierarchy path (1) — routes to 1 parentless root

Block Graph → Network → Reservoir-Flux Network → Conservation Laws → Invariance

Neighborhood in Abstraction Space¶

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

Family — Graph Classes & Invariants (37 abstractions)

Nearest neighbors

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