Revision history [back]

In fact, I can use the following code (in conjunction with Edmonds' 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) == 2:
        selected_graphs.append(g)
len(selected_graphs)

I'm wondering if it's possible to combine the structure of such graphs to improve efficiency. For example, Let $G$ be a connected grpah with maximum matching 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 connected to the two endpoints of a matching in M, respectively.

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

PS: Theorem (Erdős and Gallai, 1959) For all $n \geq 2 s$ and $s \geq 1$,

$$ ex(n, M_s) = \max \large( ( \frac{s - 1}{2} ) + (s - 1)(n - s + 1), \left( \frac{2s - 1}{2} \right) \large) $$ 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$.

In fact, I can use the following code (in conjunction with Edmonds' 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) == 2:
4:
        selected_graphs.append(g)
len(selected_graphs)

I'm wondering if it's possible to combine the structure of such graphs to improve efficiency. For example, Let $G$ be a connected grpah with maximum matching 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 connected to the two endpoints of a matching in M, respectively.

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

PS: Theorem (Erdős and Gallai, 1959) For all $n \geq 2 s$ and $s \geq 1$,

$$ ex(n, M_s) = \max \large( ( \frac{s - 1}{2} ) + (s - 1)(n - s + 1), \left( \frac{2s - 1}{2} \right) \large) $$ 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$.

In fact, I can use the following code (in conjunction with Edmonds' 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'm wondering if it's possible to combine the structure of such graphs to improve efficiency. For example, Let $G$ be a connected grpah with maximum matching 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 connected to the two endpoints of a matching in M, respectively.

Perhaps in this way, we can need to traverse the order of non-isomorphic graphs, graphs with small 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.

PS: Theorem (Erdős and Gallai, 1959) For all $n \geq 2 s$ and $s \geq 1$,

$$ ex(n, M_s) = \max \large( ( \frac{s - 1}{2} ) + (s - 1)(n - s + 1), \left( \frac{2s - 1}{2} \right) \large) $$ 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$.

In fact, I can use the following code (in conjunction with Edmonds' 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'm wondering if it's possible to combine the structure of such graphs to improve efficiency. For example, Let $G$ be a connected grpah with maximum matching 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 connected to the two endpoints of a matching in M, respectively.

Perhaps in this way, we can need to traverse non-isomorphic graphs with small 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.

Do this may be good for generating all such graphs with more vertices, for example, 14 vertices.

PS: Theorem (Erdős and Gallai, 1959) For all $n \geq 2 s$ and $s \geq 1$,

$$ ex(n, M_s) = \max \large( ( \frac{s - 1}{2} ) + (s - 1)(n - s + 1), \left( \frac{2s - 1}{2} \right) \large) $$ 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$.

In fact, I can use the following code (in conjunction with Edmonds' 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'm wondering if it's possible to combine the structure of such graphs to improve efficiency. For example, Let $G$ be a connected grpah with maximum matching 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 connected to the two endpoints of a matching in M, respectively.

Perhaps in this way, we can need to traverse non-isomorphic graphs with small 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.

Do Doing this may be good for generating all such graphs with more vertices, for example, 14 vertices.

PS: Theorem (Erdős and Gallai, 1959) For all $n \geq 2 s$ and $s \geq 1$,

$$ ex(n, M_s) = \max \large( ( \frac{s - 1}{2} ) + (s - 1)(n - s + 1), \left( \frac{2s - 1}{2} \right) \large) $$ 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$.

In fact, I can use the following code (in conjunction with Edmonds' 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'm wondering if it's possible to combine the structure of such graphs to improve efficiency. For example, Let $G$ be a connected grpah with maximum matching 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 connected to the two endpoints of a matching in M, respectively.

Perhaps in this way, we can need to traverse non-isomorphic graphs with small 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, for example, 14 vertices.

PS: Theorem (Erdős and Gallai, 1959) For all $n \geq 2 s$ and $s \geq 1$,

$$ ex(n, M_s) = \max \large( ( \frac{s - 1}{2} ) + (s - 1)(n - s + 1), \left( \frac{2s - 1}{2} \right) \large) $$ 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$.

In fact, I can use the following code (in conjunction with Edmonds' 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'm wondering if it's possible to combine the structure of such graphs to improve efficiency. For example, Let $G$ be a connected grpah with maximum matching 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 connected to the two endpoints of a matching in M, respectively.

Perhaps in this way, we can need to traverse non-isomorphic graphs with small 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, for example, 14 vertices.

PS: Theorem (Erdős and Gallai, 1959) For all $n \geq 2 s$ and $s \geq 1$,

$$ ex(n, M_s) = \max \large( ( \frac{s - 1}{2} ) + (s - 1)(n - s + 1), \left( \frac{2s - 1}{2} \right) \large) $$ 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$.

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'm wondering if it's possible to combine the structure of such graphs to improve efficiency. For example, Let $G$ be a connected grpah with maximum matching 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 connected to the two endpoints of a matching in M, respectively.

Perhaps in this way, we can need to traverse non-isomorphic graphs with small 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, for example, such as 14 vertices.

PS: Theorem (Erdős and Gallai, 1959) For all $n \geq 2 s$ and $s \geq 1$,

$$ ex(n, M_s) = \max \large( ( \frac{s - 1}{2} ) + (s - 1)(n - s + 1), \left( \frac{2s - 1}{2} \right) \large) $$ 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$.

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'm wondering if it's possible to combine the structure of such graphs to improve efficiency. For example, Let $G$ be a connected grpah with maximum matching 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 connected adjacent to the two endpoints of a matching in M, respectively.

Perhaps in this way, we can need to traverse non-isomorphic graphs with small 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.

PS: Theorem (Erdős and Gallai, 1959) For all $n \geq 2 s$ and $s \geq 1$,

$$ ex(n, M_s) = \max \large( ( \frac{s - 1}{2} ) + (s - 1)(n - s + 1), \left( \frac{2s - 1}{2} \right) \large) $$ 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$.

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'm wondering if it's possible to combine the structure of such graphs to improve efficiency. For example, Let $G$ be a connected grpah with 12 vertices and maximum matching 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 two endpoints of a matching in M, respectively.

Perhaps in this way, we can need to traverse non-isomorphic graphs with small 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.

PS: Theorem (Erdős and Gallai, 1959) For all $n \geq 2 s$ and $s \geq 1$,

$$ ex(n, M_s) = \max \large( ( \frac{s - 1}{2} ) + (s - 1)(n - s + 1), \left( \frac{2s - 1}{2} \right) \large) $$ 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$.

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'm wondering if it's possible to combine the structure of such graphs to improve efficiency. For example, Let $G$ be a connected grpah 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)$. $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 two endpoints of a matching in M, respectively.

Perhaps in this way, we can need to traverse non-isomorphic graphs with small 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.

PS: Theorem (Erdős and Gallai, 1959) For all $n \geq 2 s$ and $s \geq 1$,

$$ ex(n, M_s) = \max \large( ( \frac{s - 1}{2} ) + (s - 1)(n - s + 1), \left( \frac{2s - 1}{2} \right) \large) $$ 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$.

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'm wondering if it's possible to combine the structure of such graphs to improve efficiency. For example, Let $G$ be a connected grpah 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 two endpoints of a matching in M, respectively.

Perhaps in this way, we can need to traverse non-isomorphic graphs with small 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.

PS: Theorem (Erdős and Gallai, 1959) For all $n \geq 2 s$ and $s \geq 1$,

$$ ex(n, M_s) = \max \large( ( \frac{s - 1}{2} ) + (s - 1)(n - s + 1), \left( \frac{2s - 1}{2} \right) \large) $$ 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$.

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'm I am wondering if it's possible to combine the structure of such graphs to improve efficiency. For example, Let $G$ be a connected grpah 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 two endpoints of a matching in M, respectively.

Perhaps in this way, we can need to traverse non-isomorphic graphs with small 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.

PS: Theorem (Erdős and Gallai, 1959) For all $n \geq 2 s$ and $s \geq 1$,

$$ ex(n, M_s) = \max \large( ( \frac{s - 1}{2} ) + (s - 1)(n - s + 1), \left( \frac{2s - 1}{2} \right) \large) $$ 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$.

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 grpah 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}$. $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 two endpoints of a matching in M, respectively.

Perhaps in this way, we can need to traverse non-isomorphic graphs with small 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.

PS: Theorem (Erdős and Gallai, 1959) For all $n \geq 2 s$ and $s \geq 1$,

$$ ex(n, M_s) = \max \large( ( \frac{s - 1}{2} ) + (s - 1)(n - s + 1), \left( \frac{2s - 1}{2} \right) \large) $$ 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$.

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 grpah 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 two endpoints of a matching in M, respectively.

Perhaps in this way, we can need to traverse non-isomorphic graphs with small 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.

PS: Theorem (Erdős and Gallai, 1959) For all $n \geq 2 s$ and $s \geq 1$,

$$ ex(n, M_s) = \max \large( ( \{( \frac{s - 1}{2} ) + (s - 1)(n - s + 1), \left( \frac{2s - 1}{2} \right) \large) $$ \} $$, 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$.

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 grpah with 12 vertices and maximum matchings with size of 4. Let $M=[u_1u_2,u_3u_4,u_5u_6,u_7u_8]$ $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 two endpoints of a matching in M, respectively.

Perhaps in this way, we can need to traverse non-isomorphic graphs with small 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.

PS: Theorem (Erdős and Gallai, 1959) For all $n \geq 2 s$ and $s \geq 1$,

$$ ex(n, M_s) = \max \{( \frac{s - 1}{2} ) + (s - 1)(n - s + 1), \left( \frac{2s - 1}{2} \right) \} $$, 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$.

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 grpah 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 two distinct endpoints of a matching in M, respectively.

Perhaps in this way, we can need to traverse non-isomorphic graphs with small 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.

PS: Theorem (Erdős and Gallai, 1959) For all $n \geq 2 s$ and $s \geq 1$,

$$ ex(n, M_s) = \max \{( \frac{s - 1}{2} ) + (s - 1)(n - s + 1), \left( \frac{2s - 1}{2} \right) \} $$, 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$.

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 small 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.

PS: Theorem (Erdős and Gallai, 1959) For all $n \geq 2 s$ and $s \geq 1$,

$$ ex(n, M_s) = \max \{( \frac{s - 1}{2} ) + (s - 1)(n - s + 1), \left( \frac{2s - 1}{2} \right) \} $$, 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$.size $s$.

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.

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 small 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.

PS: Theorem (Erdős and Gallai, 1959) For all $n \geq 2 s$ and $s \geq 1$,

$$ ex(n, M_s) = \max \{( \frac{s \{\binom{s - 1}{2} ) + (s - 1)(n - s + 1), \left( \frac{2s \binom{2s - 1}{2} \right) \} $$, 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$.

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.

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 small 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.

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), \left( \binom{2s - 1}{2} \right) \} $$, $$ 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$.

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.

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 small 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$.

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.$s$.

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 small 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) 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$.

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 small 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 iTheorem* (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$.

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 small 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: iTheorem* 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$.

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 small 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$.