Generate all connected graphs of order 12 with matching number of 4

edit

In fact, I can use the following code (in conjunction with Erdős and Gallai's theorem) where the number of edges is less than or equal to 38.

num_vertices = 12
selected_graphs = []
for g in graphs.nauty_geng(f'{num_vertices} -c 11:38'):
    if g.matching(value_only=True) == 4:
        selected_graphs.append(g)
len(selected_graphs)

I am wondering if it's possible to combine the structure of such graphs to improve efficiency. For example, Let $G$ be a connected graph with 12 vertices and maximum matchings with size of 4. Let $M=\{u_1u_2,u_3u_4,u_5u_6,u_7u_8\}$ be a matching. Let $S=V(G)-\{u_1,u_2\dots u_8\}$. Then：

• there is no edge in $S$.
• Any two vertices in $S$ cannot be adjacent to the distinct endpoints of a matching in M, respectively.

Perhaps in this way, we can need to traverse non-isomorphic graphs with smaller order, in this case only running some non-isomorphic graphs on 8 vertices. Or nauty can forbid matchings of fixed size, which could also achieve some purposes.

Doing this may be good for generating all such graphs with more vertices, such as 14 vertices. Actually, it might be more generally meaningful to generate non-isomorphic graphs containing a subgraph, and perhaps we can reduce the search space by using some basic structures.

PS:

Theorem (Erdős and Gallai, 1959) For all $n \geq 2 s$ and $s \geq 1$, $$ ex(n, M_s) = \max \{\binom{s - 1}{2} + (s - 1)(n - s + 1), \binom{2s - 1}{2} \}, $$ that is, for any given graph $G$ of order $ n$, if $|E(G)| > ex(n, M_s) $, then $ G $ contains a matching of size $s$.