Editing Glossary of graph theory (section)

==M==
{{glossary}}

{{term|magnification}}
{{defn|Synonym for vertex {{gli|expansion}}.}}

{{term|matching}}
{{defn|A [[Matching (graph theory)|matching]] is a set of edges in which no two share any vertex. A vertex is matched or saturated if it is one of the endpoints of an edge in the matching. A [[perfect matching]] or complete matching is a matching that matches every vertex; it may also be called a 1-factor, and can only exist when the order is even. A near-perfect matching, in a graph with odd order, is one that saturates all but one vertex. A [[maximum matching]] is a matching that uses as many edges as possible; the matching number {{math|''&alpha;''′(''G'')}} of a graph {{mvar|G}} is the number of edges in a maximum matching. A [[maximal matching]] is a matching to which no additional edges can be added.}}

{{term|maximal}}
{{defn|no=1|A subgraph of given graph {{mvar|G}} is maximal for a particular property if it has that property but no other supergraph of it that is also a subgraph of {{mvar|G}} also has the same property. That is, it is a [[maximal element]] of the subgraphs with the property. For instance, a [[maximal clique]] is a complete subgraph that cannot be expanded to a larger complete subgraph. The word "maximal" should be distinguished from "maximum": a maximum subgraph is always maximal, but not necessarily vice versa.}}
{{defn|no=2|A simple graph with a given property is maximal for that property if it is not possible to add any more edges to it (keeping the vertex set unchanged) while preserving both the simplicity of the graph and the property. Thus, for instance, a [[maximal planar graph]] is a planar graph such that adding any more edges to it would create a non-planar graph.}}

{{term|maximum}}
{{defn|A subgraph of a given graph {{mvar|G}} is maximum for a particular property if it is the largest subgraph (by order or size) among all subgraphs with that property. For instance, a [[maximum clique]] is any of the largest cliques in a given graph.}}

{{term|median}}
{{defn|no=1|A median of a triple of vertices, a vertex that belongs to shortest paths between all pairs of vertices, especially in median graphs and [[modular graph]]s.}}
{{defn|no=2|A [[median graph]] is a graph in which every three vertices have a unique median.}}

{{term|Meyniel}}
{{defn|no=1|Henri Meyniel, French graph theorist.}}
{{defn|no=2|A [[Meyniel graph]] is a graph in which every odd cycle of length five or more has at least two chords.}}

{{term|minimal}}
{{defn|A subgraph of given graph is minimal for a particular property if it has that property but no proper subgraph of it also has the same property. That is, it is a [[minimal element]] of the subgraphs with the property.}}

{{term|minimum cut|[[minimum cut]]}}
{{defn|A {{gli|cut}} whose {{gli|cut-set}} has minimum total weight, possibly restricted to cuts that separate a designated pair of vertices; they are characterized by the [[max-flow min-cut theorem]].}}

{{term|minor}}
{{defn|A graph {{mvar|H}} is a [[graph minor|minor]] of another graph {{mvar|G}} if {{mvar|H}} can be obtained by deleting edges or vertices from {{mvar|G}} and contracting edges in {{mvar|G}}. It is a [[shallow minor]] if it can be formed as a minor in such a way that the subgraphs of {{mvar|G}} that were contracted to form vertices of {{mvar|H}} all have small diameter. {{mvar|H}} is a [[topological minor]] of {{mvar|G}} if {{mvar|G}} has a subgraph that is a [[Subdivision (graph theory)|subdivision]] of {{mvar|H}}. A graph is {{mvar|H}}-minor-free if it does not have {{mvar|H}} as a minor. A family of graphs is minor-closed if it is closed under minors; the [[Robertson–Seymour theorem]] characterizes minor-closed families as having a finite set of {{gli|forbidden}} minors.}}

{{term|mixed}}
{{defn|A [[mixed graph]] is a graph that may include both directed and undirected edges.}}

{{term|modular}}
{{defn|no=1|[[Modular graph]], a graph in which each triple of vertices has at least one median vertex that belongs to shortest paths between all pairs of the triple.}}
{{defn|no=2|[[Modular decomposition]], a decomposition of a graph into subgraphs within which all vertices connect to the rest of the graph in the same way.}}
{{defn|no=3|[[Modularity (networks)|Modularity]] of a graph clustering, the difference of the number of cross-cluster edges from its expected value.}}

{{term|monotone}}
{{defn|A monotone property of graphs is a property that is closed under subgraphs: if {{mvar|G}} has a monotone property, then so must every subgraph of {{mvar|G}}. Compare {{gli|hereditary}} (closed under induced subgraphs) or ''minor-closed'' (closed under minors).}}

{{term|Moore graph}}
{{defn|A [[Moore graph]] is a regular graph for which the Moore bound is met exactly. The Moore bound is an inequality relating the degree, diameter, and order of a graph, proved by [[Edward F. Moore]]. Every Moore graph is a cage.}}

{{term|multigraph}}
{{defn|A [[multigraph]] is a graph that allows multiple adjacencies (and, often, self-loops); a graph that is not required to be simple.}}

{{term|multiple adjacency}}
{{defn|A multiple adjacency or multiple edge is a set of more than one edge that all have the same endpoints (in the same direction, in the case of directed graphs). A graph with multiple edges is often called a multigraph.}}

{{term|multiplicity}}
{{defn|The multiplicity of an edge is the number of edges in a multiple adjacency. The multiplicity of a graph is the maximum multiplicity of any of its edges.}}

{{glossary end}}