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.

Block graphs may be characterized as the intersection graphs of the blocks of arbitrary undirected graphs. Therefore, the connected subsets of vertices in a connected block graph form a convex geometry, a property that is not true of any graphs that are not block graphs. The connected block graphs are exactly the graphs in which there is a unique induced path connecting every pair of vertices.

For Block Graph, the abstraction is narrower than the article's general subject matter: a positive case must preserve is a type of undirected graph in which every biconnected component (block) is a clique. Retaining only the name, a familiar example, or a downstream effect is insufficient. The specialist roles and tests remain anchored in mathematics, logic, and statistics, which is why this identity is domain-specific rather than prime.

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.

Structural Signature¶

Sig role-phrases:

Defining carrier — B(G) is necessarily a block graph: it has one biconnected component for each articulation vertex of G, and each biconnected component formed in this way must be a clique.
Constitutive relation — 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.
Operating condition — Block graphs are exactly the graphs for which, for every four vertices , , , and , the largest two of the three distances ,.
Recognition evidence — 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, they are the diamond-free chordal graphs.
Admissible variation — A graph is a block graph if and only if the intersection of every two connected subsets of vertices of is empty or connected.
Characteristic consequence — Therefore, the connected subsets of vertices in a connected block graph form a convex geometry, a property that is not true of any graphs that are not block graphs.
Failure boundary — Because of this property, in a connected block graph, every set of vertices has a unique minimal connected superset, its closure in the convex geometry.

What It Is Not¶

Not the whole field of mathematics, logic, and statistics. The node requires the specific identity stated by is a type of undirected graph in which every biconnected component (block) is a clique.
Not an over-broad reading. 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, they are the diamond-free chordal graphs.
Not an over-broad reading. Therefore, the connected subsets of vertices in a connected block graph form a convex geometry, a property that is not true of any graphs that are not block graphs.
Not an over-broad reading. Block graphs are exactly the graphs for which, for every four vertices , , , and , the largest two of the three distances ,.
Not automatically Tree Decomposition. Retrieval proximity does not establish equivalence; the two identities must be compared by carrier, operation, and failure boundary.

Scope of Application¶

Block Graph applies literally inside mathematics, logic, and statistics wherever the source-defined carrier and relation can be established. Its documented habitats include:

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 as possible.
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, they are the diamond-free chordal graphs.
Characterization. A graph is a block graph if and only if the intersection of every two connected subsets of vertices of is empty or connected.

Outside mathematics, logic, and statistics, the name should be retained only when these same operational conditions survive; otherwise the comparison belongs to the broader parent Pattern or should be marked as analogy.

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 a cycle of four or more vertices as an induced subgraph; that is, they are the diamond-free chordal graphs. A report should distinguish that evidence from a proxy, consequence, or common implementation. It should also state the qualification 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, they are the diamond-free chordal graphs. so that a reader can reproduce the classification rather than infer it from topical resemblance.

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, the connected subsets of vertices in a connected block graph form a convex geometry, a property that is not true of any graphs that are not block graphs. This compression makes cases comparable while leaving parameters, conventions, exceptions, and evidential quality explicit. It is lossy by design: local history and implementation details may be omitted only when they do not alter the defining relation.

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. 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, they are the diamond-free chordal graphs.
Test variation. Change an implementation or setting while preserving a graph is a block graph if and only if the intersection of every two connected subsets of vertices of is empty or connected.
Run the collapse test. Remove the defining operation; if the label still seems equally apt, only a topic or correlate was retained.
Reduce cautiously. When the specialist conditions cannot be carried, route the residual comparison to Pattern.

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.

Beyond the home domain. No canonical parent is asserted for Block Graph. An outside case receives the specialist name only when the same typed roles and rejection conditions can be filled literally; otherwise the comparison remains an analogy pending later graph densification.

Examples¶

Canonical¶

Block graphs are exactly the graphs for which, for every four vertices , , , and , the largest two of the three distances ,. This case is canonical because it supplies a concrete carrier and lets the defining relation be checked rather than merely named.

Mapped back: carrier → the entities in the documented case; operation → is a type of undirected graph in which every biconnected component (block) is a clique; recognition evidence → 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, they are the diamond-free chordal graphs

Applied / In Practice¶

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, they are the diamond-free chordal graphs. The applied case shows how the identity is used under a second setting or qualification while keeping the same operative relation.

Mapped back: changed setting → Characterization; invariant → is a type of undirected graph in which every biconnected component (block) is a clique; boundary → the case exits the class when 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, they are the diamond-free chordal graphs

Structural Tensions¶

T1 — Stable identity versus admissible variation. 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, they are the diamond-free chordal graphs. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Which changes preserve the defining relation, and which replace it?

T2 — Recognition versus proxy. Therefore, the connected subsets of vertices in a connected block graph form a convex geometry, a property that is not true of any graphs that are not block graphs. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Does the cited evidence establish the identity or only a correlated sign?

T3 — Definition versus implementation. Block graphs are exactly the graphs for which, for every four vertices , , , and , the largest two of the three distances ,. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Is the observed implementation constitutive, optional, or merely common?

T4 — Scope versus overextension. A graph is a block graph if and only if the intersection of every two connected subsets of vertices of is empty or connected. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Can every claimed application fill the same typed roles without metaphor?

T5 — Transfer versus domain accent. B(G) is necessarily a block graph: it has one biconnected component for each articulation vertex of G, and each biconnected component formed in this way must be a clique. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: Does the receiving case instantiate Block Graph literally, co-instantiate Pattern, or only resemble it?

T6 — Autonomy versus reduction. 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. The tension matters because emphasizing only one side either dissolves the identity or overstates what the evidence and domain conventions warrant.

Diagnostic: What does Block Graph distinguish that the broader parent Pattern leaves together?

Structural–Framed Character¶

Block Graph is structural-leaning. Its structural side is the repeatable organization summarized by is a type of undirected graph in which every biconnected component (block) is a clique. Its framed side is the mathematics, logic, and statistics vocabulary that fixes the carrier, evidence, exceptions, and admissible transformations.

Evaluative weight: the identity can be stated descriptively even when applications carry practical stakes. Human-practice dependence: the source-grounded carrier determines whether the relation exists independently or is constituted by a practice. Institutional origin: disciplinary conventions stabilize the name and test. Vocabulary portability: Block graphs are exactly the graphs for which, for every four vertices , , , and , the largest two of the three distances ,. Import versus recognition: literal transfer requires the same mechanism; shape alone is analogy.

Its portable skeleton is Pattern. Its character: a recurring specialist identity whose thin organization can be abstracted, while its operational meaning remains domain-bound.

Structural Core vs. Domain Accent¶

What is skeletal. is a type of undirected graph in which every biconnected component (block) is a clique. The stable skeleton is the typed relation expressed in that definition and the entry's recognition and collapse tests. The source identifies these operative conditions: B(G) is necessarily a block graph: it has one biconnected component for each articulation vertex of G, and each biconnected component formed in this way must be a clique. 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. It further constrains recognition and variation through: Block graphs are exactly the graphs for which, for every four vertices , , , and , the largest two of the three distances ,. 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, they are the diamond-free chordal graphs.

What is domain-bound. mathematics, logic, and statistics supplies the operative entities, technical vocabulary, warrants, and exceptions that make Block Graph literal. Its documented scope includes the condition that 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. Another bounded application condition is that 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. These are not decorative examples; they determine which carrier and evidence can fill the abstraction's roles.

Why no parent is asserted. Removing those specialist details does not currently yield one live catalog node that is a necessary genus for every instance. The entry is therefore approved as unparented rather than attached by topical resemblance. Its collapse evidence remains specific—A graph is a block graph if and only if the intersection of every two connected subsets of vertices of is empty or connected.—and future graph densification may discover a defensible relation only if it preserves that boundary.

This entry is a kind of Network.

Approved unparented node. No current live node supplies a defensible necessary genus or structural prerequisite for Block Graph. The reviewed identity is: is a type of undirected graph in which every biconnected component (block) is a clique. The accelerated suggestion was declined because topical or lexical similarity does not establish hierarchy; the node is admitted without a parent pending later graph densification.
Related reasoning operations. Evidence, representation, comparison, classification, transformation, or evaluation may participate in particular cases, but participation does not make any one of them a necessary parent of every instance.

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

Not to Be Confused With¶

Pattern. The parent omits the specialist differentia. Tell: Can the case establish is a type of undirected graph in which every biconnected component (block) is a clique?
Tree Decomposition. A tree decomposition represents a graph by overlapping vertex bags arranged as a tree so that the bags cover every vertex, the endpoints of every graph edge co-occur in some bag, and the bags containing any one vertex form a connected subtree. Tell: Which entry's carrier, operation, and failure condition are satisfied?
Clique (Graph Theory). A vertex subset of an undirected graph in which every two distinct vertices are adjacent, equivalently an induced complete subgraph. Tell: Which entry's carrier, operation, and failure condition are satisfied?
SPQR Tree. A canonical tree representation of a biconnected graph's decomposition at separation pairs, whose S, P, Q, and R skeletons expose series, parallel, edge, and rigid triconnected structure and reconstruct the graph through paired virtual edges. Tell: Which entry's carrier, operation, and failure condition are satisfied?
A measurement, proxy, or consequence. Those may provide evidence without being the identity. Tell: Would Block Graph remain present if the detector or downstream effect changed?
A metaphorical analogue. A similar shape outside mathematics, logic, and statistics lacks the specialist mechanism. Tell: Do the native roles transfer literally, or only the parent Pattern?

References¶

Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Block_graph (revision 1269155126).
Preserved source candidate: http://eprints.whiterose.ac.uk/74347/2/ehfsurvey.pdf
Preserved source candidate: http://www.graphclasses.org/classes/gc_93.html
Preserved source candidate: http://real.mtak.hu/110576/1/1-s2.0-0095895686900286-main.pdf

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.