Can a triangle be a minor of a square without diagonals?

Yes. Contracting one square edge produces a triangle under simple-graph conventions.

Is every subgraph a minor?

Yes. Vertex and edge deletions are permitted minor operations.

Can I contract two vertices with no connecting edge?

Not in one edge-contraction operation. A connected set can be merged through suitable edge contractions, but arbitrary identification is a different operation.

AI Glossary / Graphs and symbolic AI / Intermediate

Minors

Definition

A graph minor is a graph obtainable from another graph by deleting vertices, deleting edges, and contracting edges. Contraction merges the two endpoints of an edge into one vertex while preserving their connections to other vertices. Minors provide a precise way to describe structural patterns hidden inside a larger graph.

What it means

A subgraph is formed by removing parts of a graph. A minor permits an additional operation: connected pieces can be compressed through edge contractions. This means a pattern may exist as a minor even when it does not appear as a literal subgraph on the original vertices.
Here, minors refers to graph theory, matching the supplied NetworkX reference. It is unrelated to matrix minors or the age-related meaning of the word. For the main examples, use simple undirected graphs, discarding contraction-created loops and merging duplicate edges when needed. Other graph types require their conventions to be stated.

How it works

To contract edge uv, replace its endpoints with one merged vertex. An edge from u or v to another vertex becomes an edge from the merged vertex to that other vertex. The contracted edge itself becomes a loop before simplification.
Vertex deletion removes a vertex and its incident edges; edge deletion removes a chosen connection. A sequence of these operations demonstrates that the resulting graph is a minor. Such a sequence is a structural certificate, not an instruction to preserve distances, edge weights, or application meaning automatically. Software contraction routines may retain loops or metadata according to their options.

Three practical examples

A graph-theory analysis can identify a simpler structural pattern by contracting paths in a larger network.
A teaching tool can compare a graph with its subgraphs and minors to show what contraction adds.
A network-analysis prototype can experiment with merging connected regions, while separately checking which application properties survive the transformation.

Think of it this way

Think of simplifying a route map by shrinking selected road segments until their endpoint junctions merge. The remaining connections reveal a smaller structural map. The analogy is limited because contraction changes the graph's representation and can alter distances or capacities; it does not mean physical roads can actually be removed without consequences.

Worked example

Consider an invented square graph with vertices A, B, C, and D and edges AB, BC, CD, and DA. There are no diagonals. Contract edge AB into a merged vertex X.
Edge BC becomes XC because B is part of X. Edge DA becomes DX because A is part of X. Edge CD remains CD. The contracted AB produces a self-loop at X, which we discard under the simple-graph convention. The resulting graph has vertices X, C, and D and edges XC, CD, and DX: a triangle.
Thus the triangle is a minor of the square. It is not a subgraph of the original square, because no three original vertices have all three pairwise edges. Contraction, rather than deletion alone, creates the smaller triangle pattern.
If we then delete edge CD, the result is the two-edge path C-X-D, which is also a minor of the original square. Alternatively, delete original vertex D before contracting anything; the remaining graph A-B-C is another path obtained by vertex deletion alone.
The example also shows what is not preserved. In the original graph, A and B are distinct adjacent vertices. After contraction, both are represented by X, so a query about their separation has lost information. If the original edges carried travel times, this simple structural operation would not automatically define meaningful travel times for every resulting edge.
A library routine that retains self-loops would return the triangle together with a loop at X unless configured otherwise. That output reflects its chosen representation, so the desired simple-graph convention must be matched explicitly.

Illustrative case study

In a fictional dependency-visualization project, Laurel Networks merges adjacent components to produce a smaller diagram. A stakeholder then interprets the diagram's edge counts as though each edge still represented exactly one original dependency.
The team adds a record of which original vertices and edges each displayed element represents. It distinguishes structural simplification from quantitative aggregation. This invented case illustrates why a valid graph contraction is not automatically a valid summary for every downstream business question.

Common misconceptions and mistakes

A minor is not necessarily an induced subgraph or even a subgraph. The square-to-triangle example establishes the difference. Also, a minor need not have strictly fewer vertices: allowing no operations means a graph is a minor of itself.
Do not assume that merging any two unrelated vertices is an edge contraction. The operation requires an edge between the endpoints; contracting a connected region can be implemented through a sequence of such contractions. Finally, preserving graph structure in the minor sense does not preserve every numerical property. Degree, shortest-path distance, edge multiplicity, and application attributes may change.

Business use

The term is most useful for teams applying graph algorithms or interpreting structural graph research. State the graph type and transformation rules before using a minor-based conclusion. Keep a mapping back to the original graph when people need to inspect what a merged vertex represents.
For software work, check whether contraction modifies the input graph or creates a copy, whether loops are retained, and how attributes are stored. The NetworkX reference exposes such options, but this glossary entry is conceptual rather than a version-specific usage recipe. Verify any property needed by the application instead of assuming it survives contraction.

Check your understanding

Why is the triangle in the worked example a minor but not a subgraph of the original square?

Answer: Contracting AB merges A and B so their connections create a triangle on X, C, and D. The original square has no triangle among any three of its original vertices.

Related terms

Graph contraction
subgraph
induced subgraph
vertex deletion
edge deletion
self-loop
multigraph
graph simplification
structural pattern

Learn next

Draw a five-cycle and contract two selected edges, tracking every endpoint change. Then repeat using edge deletion only. Compare which smaller graphs each operation can produce, and record when loop removal or duplicate-edge merging is needed for a simple-graph interpretation.

Sources

NetworkX, official contracted_edge documentation: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.minors.contracted_edge.html Reconfiguration of graph minors, original research abstract defining the minor relationship through subgraphs and contraction: https://arxiv.org/abs/1804.09240

Previous: Minority class Next: Mipmap