matching in a graph

匹配

Combinatorics · Undergraduate · Mathematics Resources editorial compilation (AI-assisted)

Other names / variants: independent edge set

Translation evidence: Literature usage

Meaning in context

A matching in a finite simple graph is a subset of edges such that no two chosen edges share an endpoint.

有限简单图中的匹配是一个边子集，其中任意两条所选边都没有公共端点。

Example

In a−b−c−da-b-c-d, the edges abab and cdcd form a matching of size two.

Usage and distinctions

Matching size counts edges. A matching of size k saturates exactly 2k vertices; it need not be maximum.

Recommended reading in this subject · Preparation & skip guidance

Definition sources

  1. Keller and Trotter — Applied Combinatorics (2016)Section 14.2, matching and saturation definitions · Checked 2026-10-14

Translation sources

  1. Reinhard Diestel — 图论，第五版，于青林译第二章开篇，印刷p.33，「匹配 (matching)」定义 · Checked 2026-10-14
Edit source / propose a PRReport a correction

Original encyclopedia and terminology content: CC BY-SA 4.0. Contribute or report a correction.