Consider a connected undirected graph. A matching set of edges on this graph is defined as a set of edges such that no two edges in the set share a common vertex. For example, the left figure denotes a matching set in green, while the right figure denotes a non-matching set in red.

enter image description here

A matching set is said to be maximally matching, or a maximal matching if it is impossible to add another edge of the graph to the matching set. So both examples above are not maximal matching sets, but both of the sets below in blue are maximal matchings. Note that maximal matchings are not necessarily unique. Furthermore, there's not requirement that the size of each possible maximal matching for a graph is equal to another matching.enter image description here

The goal of this challenge is to write a program/function to find a maximal matching of a graph.


Assume all vertices of the input graph have some consecutive integer numbering starting at any beginning integer value of your choice. An edge is described by an unordered pair of integers denoting the vertices the edge connects. For example, the graph shown above could be described with the following unordered set of edges (assuming the numbering of vertices starts at 0):

[(0,1), (0,2), (1,3), (1,4), (2,3), (3,4), (3,5), (5,6)]

An alternative way to describe a graph is via an adjacency list. Here is an example adjacency list for the above graph:

[0:(1,2), 1:(0,3,4), 2:(0,3), 3:(1,2,4,5), 4:(1,3), 5:(3,6), 6:(5)]

Your program/function must take as input a graph from any source (stdio, function parameter, etc.). You may use any notation desired so long as the no additional non-trivial information is communicated to your program. For example, having an extra parameter denoting the number of input edges is perfectly acceptable. Similarly, passing in an unordered multiset of edges, adjacency list, or adjacency matrix is fine.

You may assume:

  1. The graph is connected (e.g. it is possible to reach any vertex given any starting vertex).
  2. There is at least one edge.
  3. An edge never connects a vertex directly to itself (ex. the edge (1,1) will not be given as input). Note that cycles are still possible (ex.: the above graphs).
  4. You may require that the input vertices start at any index (e.g. the first vertex can be 0, 1, -1, etc.).
  5. Vertex numbering is sequentially increasing from your chosen starting index (ex.: 1,2,3,4,..., or 0,1,2,3,...).


Your program/function should output a list of edges denoting a maximal matching set. An edge is defined by the two vertices which that edge connects. Ex. output for the left blue set (using the example input vertex ordering):

[(1,4), (2,3), (5,6)]

Note that the order of the vertices are not important; So the following output describes the same matching set:

[(4,1), (2,3), (6,5)]   

Output may be to stdout, a file, function return value, etc.


Here are a few example inputs (using the adjacency list format). These examples happen to start counting vertices at 0.

Note that no example outputs are given, instead I've included a Python 3 validation code.

[0:(1), 1:(0)]

[0:(1,2), 1:(0,3,4), 2:(0,3), 3:(1,2,4,5), 4:(1,3), 5:(3,6), 6:(5)]

[0:(1,2), 1:(0,2,3,4,5), 2:(0,1), 3:(1), 4:(1), 5:(1)]

[0:(1,2), 1:(0,2,3), 2:(0,1,4), 3:(1,4,5), 4:(2,3), 5:(3)]

Validation Python 3 code

Here's a Python 3 validation code which takes in a graph and set of edges and prints out whether that set is maximally matching or not. This code works with any vertex start index.

def is_maximal_matching(graph, edges):
    Determines if the given set of edges is a maximal matching of graph
    @param graph a graph specified in adjacency list format
    @param edges a list of edges specified as vertex pairs

    @return True if edges describes a maximal matching, False otherwise.
    Prints out some diagnostic text for why edges is not a maximal matching

    graph_vtxs = {k for k,v in graph.items()}
    vtxs = {k for k,v in graph.items()}

    # check that all vertices are valid and not used multiple times
    for e in edges:
        if(e[0] in graph_vtxs):
            if(e[0] in vtxs):
                print('edge (%d,%d): vertex %d is used by another edge'%(e[0],e[1],e[0]))
                return False
            print('edge (%d,%d): vertex %d is not in the graph'%(e[0],e[1],e[0]))
            return False
        if(e[1] in graph_vtxs):
            if(e[1] in vtxs):
                print('edge (%d,%d): vertex %d is used by another edge'%(e[0],e[1],e[1]))
                return False
            print('edge (%d,%d): vertex %d is not in the graph'%(e[0],e[1],e[0]))
            return False
        if(e[1] not in graph[e[0]]):
            print('edge (%d,%d): edge not in graph'%(e[0],e[1]))
            return False

    # check that any edges can't be added
    for v in vtxs:
        ovtxs = graph[v]
        for ov in ovtxs:
            if(ov in vtxs):
                print('could add edge (%d,%d) to maximal set'%(v,ov))
                return False

    return True

Example usage:

graph = {0:[1,2], 1:[0,3,4], 2:[0,3], 3:[1,2,4,5], 4:[1,3], 5:[3,6], 6:[5]}
candidate = [(0,1),(2,3)]
is_maximal_matching(graph, candidate) // False
candidate = [(0,1),(2,3),(5,6),(0,1)]
is_maximal_matching(graph, candidate) // False
candidate = [(0,1),(2,3),(5,6)]
is_maximal_matching(graph, candidate) // True


This is code golf; shortest code wins. Standard loopholes apply. You may use any built-ins desired.


9 Answers 9


CJam (16 chars)


Online demo

This is a greedy approach which accumulates edges which don't have any vertex in common with the previously accumulated edges.

  • \$\begingroup\$ I'm pretty sure this fails on the third example, giving [[0 1] [3 4]] instead of the maximal set [[0 2] [1 4] [3 5]]. (I'm ignoring the (1, 1) edge that seem to be in there by mistake) \$\endgroup\$ Apr 26, 2017 at 13:05
  • \$\begingroup\$ @ETHproductions, you're confusing maximal with maximum. \$\endgroup\$ Apr 26, 2017 at 13:33
  • 3
    \$\begingroup\$ Dangit, sorry about that... I'll just leave my comment to help any others who are confused, if you don't mind, since this seems to be a recurring issue :-P \$\endgroup\$ Apr 26, 2017 at 14:09

Pyth, 8 bytes

       y  power set (gerenate all set of edges)
      t   remove the first one (the first one is
          empty and will cause problems)
 f        filter for sets T satisfying:
     T        T
    s         flatten
  {I          is invariant under deduplicate, i.e. contains no
              duplicating vertices, as the elements represent vertices
e         pick the last one (the power set is ordered from
          smallest to largest)

Try it online!


  • Input: [(0,1), (0,2), (1,3), (1,4), (2,3), (3,4), (3,5), (5,6)]
  • Output: [(1, 4), (2, 3), (5, 6)]

Brachylog, 5 bytes


?⊇.cL≠   implicit ? at the beginning;
         ∧ breaks implicit . at the end;
         temporary variable inserted.
?⊇.      input is a superset of output
  .cL    output concatenated is L
    L≠   L contains distinct elements

Try it online!

This is guaranteed to be maximal, since Brachylog searches from the largest subset.

  • \$\begingroup\$ I think that your explanation has different code than your actual code. \$\endgroup\$ Apr 26, 2017 at 12:15
  • \$\begingroup\$ @EriktheOutgolfer That is because I inserted characters that are implicit in my explanation. The original code is in the first line. Brachylog is quite terse in this aspect. \$\endgroup\$
    – Leaky Nun
    Apr 26, 2017 at 12:16
  • \$\begingroup\$ I don't mean that, but the first code ends in ≠∧, while the second code ends in L≠. \$\endgroup\$ Apr 26, 2017 at 12:17
  • \$\begingroup\$ Without , there would be an implicit . at the end. All means here is that the . is not to be inserted at the end. \$\endgroup\$
    – Leaky Nun
    Apr 26, 2017 at 12:18
  • \$\begingroup\$ The L is a temporary variable that is used nowhere, hence its ability to be omitted. \$\endgroup\$
    – Leaky Nun
    Apr 26, 2017 at 12:18

Wolfram Language, 25 22 bytes

Saved 3 bytes thanks to @MartinEnder


This takes input as a Graph object (defined as Graph[{1<->2,2<->3,1<-3>}] etc.)

  • \$\begingroup\$ You don't need the @#&. \$\endgroup\$ Apr 26, 2017 at 5:45
  • \$\begingroup\$ @MartinEnder Thanks. \$\endgroup\$ Apr 26, 2017 at 13:36
  • \$\begingroup\$ Pfft. import solve_problem; run(). Now someone just needs to write a plugin for Wolfram that takes in a codegolf challenge URL and outputs the desired output. Call it Golf. \$\endgroup\$ Apr 26, 2017 at 18:17

Husk, 10 bytes


Try it online!


JavaScript (ES6), 67 bytes

let f =

let g = a => console.log("[%s]", f(a).map(x => "[" + x + "]").join(", "))
g([[0,1], [0,2], [1,3], [1,4], [2,3], [3,4], [3,5], [5,6]])
g([[0,1], [0,2], [1,2], [1,3], [1,4], [1,5]])
g([[0,1], [0,2], [1,2], [1,3], [2,4], [3,4], [3,5]])

Uses the greedy approach for maximal golfiness.


JavaScript (ES6), 68 66 bytes


I thought I'd give the recursive approach a go, and by stealing @ETHproduction's set intersection trick I managed to undercut his answer!

I was not the first to misread the original question, and I was about to submit the following recursive function which finds a maximal set of matching edges, rather than a set of maximal matching edges. Subtle difference, I know!


Simple recursive approach. For each input element, deletes all conflicting edges from the set and finds the maximal set of matching edges of the remaining subset, then finds the maximal result over each input element. Somewhat inefficient for large sets (9-byte speed-up possible).


Jelly, 12 11 bytes


Try it online!

Sample input: [0,1],[0,2],[1,3],[1,4],[2,3],[3,4],[3,5],[5,6]

Sample output: [[1, 4], [2, 3], [5, 6]]

How it works

FQ⁼F    - Helper function, returns 1 if a set of edges is non-matching
F       - Flatten input
 Q      - Remove repeated elements
  ⁼     - Return boolean value. Is this equal to
   F    - The flattened input list

ŒPÇÐfṪ - Main link.
ŒP     - Power set of input list of edges
   Ðf  - Remove all elements which return 1 if
  Ç    - (Helper function) it is a non-matching set
     Ṫ - Get the last element in the resultant list (the longest). 
           Always maximal because it is the longest, so any
           edge added would not be in this list (not matching)

Python 3, 68 bytes

f=lambda g:len({*sum(g,())})<2*len(g)and max(f(g-{k})for k in g)or g

Try it online!

Takes input as set. Recursively removes one item until there are no duplicate vertices. It then returns the set with the most items.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.