Matching covered graphs

This module implements functions and operations pertaining to matching covered graphs.

A matching in a graph is a set of pairwise nonadjacent links (nonloop edges). In other words, a matching in a graph is the edge set of an 1-regular subgraph. A matching is called a perfect matching if it the subgraph generated by a set of matching edges spans the graph, i.e. it’s the edge set of an 1-regular spanning subgraph. A connected nontrivial graph is called matching covered if each edge participates in some perfect matching.

Barriers and canonical partition

canonical_partition()	Return the canonical partition of the (matching covered) graph.
maximal_barrier()	Return the (unique) maximal barrier containing the vertex.

Bricks, braces and tight cut decomposition

is_brace()	Check if the (matching covered) graph is a brace.
is_brick()	Check if the (matching covered) graph is a brick.

Miscellaneous methods

get_matching()	Return an EdgesView of self._matching.
update_matching()	Update the perfect matching captured in self._matching.

Overwritten methods

add_edge()	Add an edge from vertex u to vertex v.
add_edges()	Add edges from an iterable container.
add_vertex()	Add a vertex to the (matching covered) graph.
add_vertices()	Add vertices to the (matching covered) graph from an iterable container of vertices.
allow_loops()	Change whether loops are allowed in (matching covered) graphs.
allows_loops()	Return whether loops are permitted in (matching covered) graphs.
delete_vertex()	Delete a vertex, removing all incident edges.
delete_vertices()	Delete specified vertices form self.
has_loops()	Check whether there are loops in the (matching covered) graph.
has_perfect_matching()	Check whether the graph has a perfect matching.
loop_vertices()	Return a list of vertices with loops.
loops()	Return a list of all loops in the (matching covered) graph.
number_of_loops()	Return the number of edges that are loops.
remove_loops()	Remove loops on vertices in vertices.

REFERENCES:

• This methods of this module has been adopted and inspired by the book of Lucchesi and Murty — Perfect Matchings: a theory of matching covered graphs [LM2024].

AUTHORS:

• Janmenjaya Panda (2024-06-14): initial version

Todo

The following methods are to be incorporated in MatchingCoveredGraph:

__hash__()	Compute a hash for self, if self is immutable.
_subgraph_by_deleting()	Return the matching covered subgraph containing the provided vertices and edges.

Overwritten Methods

add_clique()	Add a clique to the graph with the provided vertices.
add_cycle()	Add a cycle to the graph with the provided vertices.
add_path()	Add a path to the graph with the provided vertices.
cartesian_product()	Return the Cartesian product of self and other.
clear()	Empties the graph of vertices and edges and removes name, associated objects, and position information.
complement()	Return the complement of the graph.
contract_edge()	Contract an edge from u to v.
contract_edges()	Contract edges from an iterable container.
degree_constrained_subgraph()	Return a degree-constrained matching covered subgraph.
delete_edge()	Delete the edge from u to v.
delete_edges()	Delete edges from an iterable container.
delete_multiedge()	Delete all edges from u to v.
disjoint_union()	Return the disjoint union of self and other.
disjunctive_product()	Return the disjunctive product of self and other.
is_biconnected()	Check if the matching covered graph is biconnected.
is_block_graph()	Check whether the matching covered graph is a block graph.
is_cograph()	Check whether the matching covered graph is cograph.
is_forest()	Check if the matching covered graph is a forest, i.e. a disjoint union of trees.
is_matching_covered()	Check if the graph is matching covered.
is_path()	Check whether the graph is a path.
is_subgraph()	Check whether the matching covered graph is a subgraph of other.
is_tree()	Check whether the matching covered graph is a tree.
join()	Return the join of self and other.
lexicographic_product()	Return the lexicographic product of self and other.
load_afile()	Load the matching covered graph specified in the given file into the current object.
merge_vertices()	Merge vertices.
minor()	Return the vertices of a minor isomorphic to \(H\) in the current graph.
random_subgraph()	Return a random matching covered subgraph containing each vertex with probability p.
save_afile()	Save the graph to file in alist format.
strong_product()	Return the strong product of self and other.
subdivide_edge()	Subdivide an edge \(k\) times.
subdivide_edges()	Subdivide \(k\) times edges from an iterable container.
subgraph()	Return the matching covered subgraph containing the given vertices and edges.
subgraph_search()	Return a copy of (matching covered) G in self.
subgraph_search_count()	Return the number of labelled occurrences of (matching covered) G in self.
subgraph_search_iterator()	Return an iterator over the labelled copies of (matching covered) G in self.
tensor_product()	Return the tensor product of self and other.
to_undirected()	Return an undirected Graph instance of the matching covered graph.
topological_minor()	Return a topological \(H\)-minor from self if one exists.
transitive_closure()	Return the transitive closure of the matching covered graph.
transitive_reduction()	Return a transitive reduction of the matching covered graph.
union()	Return the union of self and other.

Bricks, braces and tight cut decomposition

bricks_and_braces()	Return the list of (underlying simple graph of) the bricks and braces of the (matching covered) graph.
number_of_braces()	Return the number of braces.
number_of_bricks()	Return the number of bricks.
number_of_petersen_bricks()	Return the number of Petersen bricks.
tight_cut_decomposition()	Return a maximal set of laminar nontrivial tight cuts and a corresponding vertex set partition.

Removability and ear decomposition

add_ear()	Add an ear to the graph with the provided end vertices number of internal vertices.
bisubdivide_edge()	Bisubdivide an edge \(k\) times.
bisubdivide_edges()	Bisubdivide \(k\) times edges from an iterable container.
efficient_ear_decomposition()	Return a matching covered ear decomposition computed at the fastest possible time.
is_removable_double_ear()	Check whether the pair of ears form a removable double ear.
is_removable_doubleton()	Check whether the pair of edges constitute a removable doubleton.
is_removable_ear()	Check whether the ear is removable.
is_removable_edge()	Check whether the edge is removable.
optimal_ear_decomposition()	Return an optimal ear decomposition.
removable_double_ears()	Return a list of removable double ears.
removable_doubletons()	Return a list of removable doubletons.
removable_ears()	Return a list of removable ears.
removable_edges()	Return a EdgesView of removable edges.
retract()	Compute the retract of the (matching covered) graph.

Generating bricks and braces

brace_generation_sequence()	Return a McCuaig brace generation sequence of the (provided) brace.
brick_generation_sequence()	Return a Norine-Thomas brick generation sequence of the (provided) brick.
is_mccuaig_brace()	Check if the brace is a McCuaig brace.
is_norine_thomas_brick()	Check if the brick is a Norine-Thomas brick.

Methods

class sage.graphs.matching_covered_graph.MatchingCoveredGraph(data=None, matching=None, algorithm='Edmonds', solver=None, verbose=0, integrality_tolerance=0.001, *args, **kwds)

Bases: Graph

Matching covered graph

INPUT:

• data – can be any of the following:

  • Empty or None (throws a ValueError as the graph must be nontrival).

  • An arbitrary graph.

• matching – (default: None); a perfect matching of the graph, that can be given using any valid input format of Graph.

  If set to None, a matching is computed using the other parameters.

• algorithm – string (default: 'Edmonds'); the algorithm to be used to compute a maximum matching of the graph among

  • 'Edmonds' selects Edmonds’ algorithm as implemented in NetworkX,

  • 'LP' uses a Linear Program formulation of the matching problem.

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• verbose – integer (default: 0); sets the level of verbosity: set to 0 by default, which means quiet (only useful when algorithm == 'LP').

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

OUTPUT:

• An object of the class MatchingCoveredGraph if the input is valid and the graph is matching covered, or otherwise an error is thrown.

Note

All remaining arguments are passed to the Graph constructor

EXAMPLES:

Generating an object of the class MatchingCoveredGraph from the provided instance of Graph without providing any other information:

Sage

sage: G = MatchingCoveredGraph(graphs.PetersenGraph())
sage: G
Matching covered petersen graph: graph on 10 vertices
sage: sorted(G.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]

sage: G = graphs.StaircaseGraph(4)
sage: H = MatchingCoveredGraph(G)
sage: H
Matching covered staircase graph: graph on 8 vertices
sage: H == G
True
sage: sorted(H.get_matching())
[(0, 1, None), (2, 7, None), (3, 6, None), (4, 5, None)]

sage: G = Graph({0: [1, 2, 3, 4], 1: [2, 5],
....:            2: [5], 3: [4, 5], 4: [5]})
sage: H = MatchingCoveredGraph(G)
sage: H
Matching covered graph on 6 vertices
sage: H == G
True
sage: sorted(H.get_matching())
[(0, 4, None), (1, 2, None), (3, 5, None)]

sage: # needs networkx
sage: import networkx
sage: G = Graph(networkx.complete_bipartite_graph(12, 12))
sage: H = MatchingCoveredGraph(G)
sage: H
Matching covered graph on 24 vertices
sage: H == G
True
sage: sorted(H.get_matching())
[(0, 15, None), (1, 14, None), (2, 13, None), (3, 12, None),
 (4, 23, None), (5, 22, None), (6, 21, None), (7, 20, None),
 (8, 19, None), (9, 18, None), (10, 17, None), (11, 16, None)]

sage: G = Graph('E|fG', sparse=True)
sage: H = MatchingCoveredGraph(G)
sage: H
Matching covered graph on 6 vertices
sage: H == G
True
sage: sorted(H.get_matching())
[(0, 5, None), (1, 2, None), (3, 4, None)]

sage: # needs sage.modules
sage: M = Matrix([(0,1,0,0,1,1,0,0,0,0),
....:             (1,0,1,0,0,0,1,0,0,0),
....:             (0,1,0,1,0,0,0,1,0,0),
....:             (0,0,1,0,1,0,0,0,1,0),
....:             (1,0,0,1,0,0,0,0,0,1),
....:             (1,0,0,0,0,0,0,1,1,0),
....:             (0,1,0,0,0,0,0,0,1,1),
....:             (0,0,1,0,0,1,0,0,0,1),
....:             (0,0,0,1,0,1,1,0,0,0),
....:             (0,0,0,0,1,0,1,1,0,0)])
sage: M
[0 1 0 0 1 1 0 0 0 0]
[1 0 1 0 0 0 1 0 0 0]
[0 1 0 1 0 0 0 1 0 0]
[0 0 1 0 1 0 0 0 1 0]
[1 0 0 1 0 0 0 0 0 1]
[1 0 0 0 0 0 0 1 1 0]
[0 1 0 0 0 0 0 0 1 1]
[0 0 1 0 0 1 0 0 0 1]
[0 0 0 1 0 1 1 0 0 0]
[0 0 0 0 1 0 1 1 0 0]
sage: G = Graph(M)
sage: H = MatchingCoveredGraph(G)
sage: H == G
True
sage: sorted(H.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]

sage: # needs sage.modules
sage: M = Matrix([(-1, 0, 0, 0, 1, 0, 0, 0, 0, 0,-1, 0, 0, 0, 0),
....:             ( 1,-1, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1, 0, 0, 0),
....:             ( 0, 1,-1, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1, 0, 0),
....:             ( 0, 0, 1,-1, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1, 0),
....:             ( 0, 0, 0, 1,-1, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1),
....:             ( 0, 0, 0, 0, 0,-1, 0, 0, 0, 1, 1, 0, 0, 0, 0),
....:             ( 0, 0, 0, 0, 0, 0, 0, 1,-1, 0, 0, 1, 0, 0, 0),
....:             ( 0, 0, 0, 0, 0, 1,-1, 0, 0, 0, 0, 0, 1, 0, 0),
....:             ( 0, 0, 0, 0, 0, 0, 0, 0, 1,-1, 0, 0, 0, 1, 0),
....:             ( 0, 0, 0, 0, 0, 0, 1,-1, 0, 0, 0, 0, 0, 0, 1)])
sage: M
[-1  0  0  0  1  0  0  0  0  0 -1  0  0  0  0]
[ 1 -1  0  0  0  0  0  0  0  0  0 -1  0  0  0]
[ 0  1 -1  0  0  0  0  0  0  0  0  0 -1  0  0]
[ 0  0  1 -1  0  0  0  0  0  0  0  0  0 -1  0]
[ 0  0  0  1 -1  0  0  0  0  0  0  0  0  0 -1]
[ 0  0  0  0  0 -1  0  0  0  1  1  0  0  0  0]
[ 0  0  0  0  0  0  0  1 -1  0  0  1  0  0  0]
[ 0  0  0  0  0  1 -1  0  0  0  0  0  1  0  0]
[ 0  0  0  0  0  0  0  0  1 -1  0  0  0  1  0]
[ 0  0  0  0  0  0  1 -1  0  0  0  0  0  0  1]
sage: G = Graph(M)
sage: H = MatchingCoveredGraph(G)
sage: H == G
True
sage: sorted(H.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]

sage: G = Graph([(0, 1), (0, 3), (0, 4), (1, 2), (1, 5), (2, 3),
....:            (2, 6), (3, 7), (4, 5), (4, 7), (5, 6), (6, 7)])
sage: H = MatchingCoveredGraph(G)
sage: H == G
True
sage: sorted(H.get_matching())
[(0, 4, None), (1, 5, None), (2, 6, None), (3, 7, None)]

sage: # optional - python_igraph
sage: import igraph
sage: G = Graph(igraph.Graph([(0, 1), (0, 3), (1, 2), (2, 3)]))
sage: H = MatchingCoveredGraph(G)
sage: H
Matching covered graph on 4 vertices
sage: sorted(H.get_matching())
[(0, 3, {}), (1, 2, {})]

Python

>>> from sage.all import *
>>> G = MatchingCoveredGraph(graphs.PetersenGraph())
>>> G
Matching covered petersen graph: graph on 10 vertices
>>> sorted(G.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]

>>> G = graphs.StaircaseGraph(Integer(4))
>>> H = MatchingCoveredGraph(G)
>>> H
Matching covered staircase graph: graph on 8 vertices
>>> H == G
True
>>> sorted(H.get_matching())
[(0, 1, None), (2, 7, None), (3, 6, None), (4, 5, None)]

>>> G = Graph({Integer(0): [Integer(1), Integer(2), Integer(3), Integer(4)], Integer(1): [Integer(2), Integer(5)],
...            Integer(2): [Integer(5)], Integer(3): [Integer(4), Integer(5)], Integer(4): [Integer(5)]})
>>> H = MatchingCoveredGraph(G)
>>> H
Matching covered graph on 6 vertices
>>> H == G
True
>>> sorted(H.get_matching())
[(0, 4, None), (1, 2, None), (3, 5, None)]

>>> # needs networkx
>>> import networkx
>>> G = Graph(networkx.complete_bipartite_graph(Integer(12), Integer(12)))
>>> H = MatchingCoveredGraph(G)
>>> H
Matching covered graph on 24 vertices
>>> H == G
True
>>> sorted(H.get_matching())
[(0, 15, None), (1, 14, None), (2, 13, None), (3, 12, None),
 (4, 23, None), (5, 22, None), (6, 21, None), (7, 20, None),
 (8, 19, None), (9, 18, None), (10, 17, None), (11, 16, None)]

>>> G = Graph('E|fG', sparse=True)
>>> H = MatchingCoveredGraph(G)
>>> H
Matching covered graph on 6 vertices
>>> H == G
True
>>> sorted(H.get_matching())
[(0, 5, None), (1, 2, None), (3, 4, None)]

>>> # needs sage.modules
>>> M = Matrix([(Integer(0),Integer(1),Integer(0),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0)),
...             (Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0)),
...             (Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0)),
...             (Integer(0),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0)),
...             (Integer(1),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(1)),
...             (Integer(1),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(1),Integer(0)),
...             (Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(1)),
...             (Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(1)),
...             (Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0),Integer(0)),
...             (Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0))])
>>> M
[0 1 0 0 1 1 0 0 0 0]
[1 0 1 0 0 0 1 0 0 0]
[0 1 0 1 0 0 0 1 0 0]
[0 0 1 0 1 0 0 0 1 0]
[1 0 0 1 0 0 0 0 0 1]
[1 0 0 0 0 0 0 1 1 0]
[0 1 0 0 0 0 0 0 1 1]
[0 0 1 0 0 1 0 0 0 1]
[0 0 0 1 0 1 1 0 0 0]
[0 0 0 0 1 0 1 1 0 0]
>>> G = Graph(M)
>>> H = MatchingCoveredGraph(G)
>>> H == G
True
>>> sorted(H.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]

>>> # needs sage.modules
>>> M = Matrix([(-Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)),
...             ( Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0),-Integer(1), Integer(0), Integer(0), Integer(0)),
...             ( Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0),-Integer(1), Integer(0), Integer(0)),
...             ( Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0),-Integer(1), Integer(0)),
...             ( Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0),-Integer(1)),
...             ( Integer(0), Integer(0), Integer(0), Integer(0), Integer(0),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)),
...             ( Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0)),
...             ( Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0)),
...             ( Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0)),
...             ( Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1))])
>>> M
[-1  0  0  0  1  0  0  0  0  0 -1  0  0  0  0]
[ 1 -1  0  0  0  0  0  0  0  0  0 -1  0  0  0]
[ 0  1 -1  0  0  0  0  0  0  0  0  0 -1  0  0]
[ 0  0  1 -1  0  0  0  0  0  0  0  0  0 -1  0]
[ 0  0  0  1 -1  0  0  0  0  0  0  0  0  0 -1]
[ 0  0  0  0  0 -1  0  0  0  1  1  0  0  0  0]
[ 0  0  0  0  0  0  0  1 -1  0  0  1  0  0  0]
[ 0  0  0  0  0  1 -1  0  0  0  0  0  1  0  0]
[ 0  0  0  0  0  0  0  0  1 -1  0  0  0  1  0]
[ 0  0  0  0  0  0  1 -1  0  0  0  0  0  0  1]
>>> G = Graph(M)
>>> H = MatchingCoveredGraph(G)
>>> H == G
True
>>> sorted(H.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]

>>> G = Graph([(Integer(0), Integer(1)), (Integer(0), Integer(3)), (Integer(0), Integer(4)), (Integer(1), Integer(2)), (Integer(1), Integer(5)), (Integer(2), Integer(3)),
...            (Integer(2), Integer(6)), (Integer(3), Integer(7)), (Integer(4), Integer(5)), (Integer(4), Integer(7)), (Integer(5), Integer(6)), (Integer(6), Integer(7))])
>>> H = MatchingCoveredGraph(G)
>>> H == G
True
>>> sorted(H.get_matching())
[(0, 4, None), (1, 5, None), (2, 6, None), (3, 7, None)]

>>> # optional - python_igraph
>>> import igraph
>>> G = Graph(igraph.Graph([(Integer(0), Integer(1)), (Integer(0), Integer(3)), (Integer(1), Integer(2)), (Integer(2), Integer(3))]))
>>> H = MatchingCoveredGraph(G)
>>> H
Matching covered graph on 4 vertices
>>> sorted(H.get_matching())
[(0, 3, {}), (1, 2, {})]

One may specify a perfect matching:

Sage

sage: P = graphs.PetersenGraph()
sage: M = P.matching()
sage: sorted(M)
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]
sage: G = MatchingCoveredGraph(P, matching=M)
sage: G
Matching covered petersen graph: graph on 10 vertices
sage: P == G
True
sage: sorted(G.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]
sage: sorted(G.get_matching()) == sorted(M)
True

sage: G = graphs.TruncatedBiwheelGraph(14)
sage: M = G.matching()
sage: sorted(M)
[(0, 27, None), (1, 26, None), (2, 3, None), (4, 5, None),
 (6, 7, None), (8, 9, None), (10, 11, None), (12, 13, None),
 (14, 15, None), (16, 17, None), (18, 19, None), (20, 21, None),
 (22, 23, None), (24, 25, None)]
sage: H = MatchingCoveredGraph(G, M)
sage: H
Matching covered truncated biwheel graph: graph on 28 vertices
sage: H == G
True
sage: sorted(H.get_matching()) == sorted(M)
True

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> M = P.matching()
>>> sorted(M)
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]
>>> G = MatchingCoveredGraph(P, matching=M)
>>> G
Matching covered petersen graph: graph on 10 vertices
>>> P == G
True
>>> sorted(G.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]
>>> sorted(G.get_matching()) == sorted(M)
True

>>> G = graphs.TruncatedBiwheelGraph(Integer(14))
>>> M = G.matching()
>>> sorted(M)
[(0, 27, None), (1, 26, None), (2, 3, None), (4, 5, None),
 (6, 7, None), (8, 9, None), (10, 11, None), (12, 13, None),
 (14, 15, None), (16, 17, None), (18, 19, None), (20, 21, None),
 (22, 23, None), (24, 25, None)]
>>> H = MatchingCoveredGraph(G, M)
>>> H
Matching covered truncated biwheel graph: graph on 28 vertices
>>> H == G
True
>>> sorted(H.get_matching()) == sorted(M)
True

One may specify some keyword arguments:

Sage

sage: G = Graph([(0, 1, 5)], {'weighted': True})
sage: kwds = {
....:   'loops': False,
....:   'multiedges': True,
....:   'pos': {0: (0, 0), 1: (1, 1)}
....: }
sage: H = MatchingCoveredGraph(G, **kwds)
sage: H
Matching covered multi-graph on 2 vertices
sage: H.add_edge(0, 1)
sage: H.edges()
[(0, 1, None), (0, 1, 5)]

Python

>>> from sage.all import *
>>> G = Graph([(Integer(0), Integer(1), Integer(5))], {'weighted': True})
>>> kwds = {
...   'loops': False,
...   'multiedges': True,
...   'pos': {Integer(0): (Integer(0), Integer(0)), Integer(1): (Integer(1), Integer(1))}
... }
>>> H = MatchingCoveredGraph(G, **kwds)
>>> H
Matching covered multi-graph on 2 vertices
>>> H.add_edge(Integer(0), Integer(1))
>>> H.edges()
[(0, 1, None), (0, 1, 5)]

add_edge(u, v=None, label=None)

Add an edge from vertex u to vertex v.

Note

This method overwrites the add_edge() method to ensure that resultant graph is also matching covered.

INPUT:

The following forms are all accepted:

• G.add_edge(1, 2)

• G.add_edge((1, 2))

• G.add_edges([(1, 2)])

• G.add_edge(1, 2, ‘label’)

• G.add_edge((1, 2, ‘label’))

• G.add_edges([(1, 2, ‘label’)])

OUTPUT:

• If an edge is provided with a valid format, but addition of the edge leaves the resulting graph not being matching covered, a ValueError is returned without any alteration to the existing matching covered graph. If the addition of the edge preserves the property of matching covered, then the graph is updated and nothing is returned.

• If the edge is provided with an invalid format, a ValueError is returned.

WARNING:

The following intuitive input results in nonintuitive output, even though the resulting graph behind the intuition might be matching covered:

Sage

sage: P = graphs.WheelGraph(6)
sage: G = MatchingCoveredGraph(P)
sage: G.add_edge((1, 4), 'label')
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
(((1, 4), 'label', None)) is not matching covered
sage: G.edges(sort=False)
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 5, None), (2, 3, None),
 (3, 4, None), (4, 5, None)]

Python

>>> from sage.all import *
>>> P = graphs.WheelGraph(Integer(6))
>>> G = MatchingCoveredGraph(P)
>>> G.add_edge((Integer(1), Integer(4)), 'label')
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
(((1, 4), 'label', None)) is not matching covered
>>> G.edges(sort=False)
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 5, None), (2, 3, None),
 (3, 4, None), (4, 5, None)]

The key word label must be used:

Sage

sage: W = graphs.WheelGraph(6)
sage: G = MatchingCoveredGraph(W)
sage: G.add_edge((1, 4), label='label')
sage: G.edges(sort=False)  # No alteration to the existing graph
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 4, 'label'), (1, 5, None),
 (2, 3, None), (3, 4, None), (4, 5, None)]

Python

>>> from sage.all import *
>>> W = graphs.WheelGraph(Integer(6))
>>> G = MatchingCoveredGraph(W)
>>> G.add_edge((Integer(1), Integer(4)), label='label')
>>> G.edges(sort=False)  # No alteration to the existing graph
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 4, 'label'), (1, 5, None),
 (2, 3, None), (3, 4, None), (4, 5, None)]

An expression, analogous to the syntax mentioned above may be used:

Sage

sage: S = graphs.StaircaseGraph(4)
sage: G = MatchingCoveredGraph(S)
sage: G.add_edge(0, 5)
sage: G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 5, None), (0, 6, None),
 (1, 2, None), (1, 4, None), (2, 5, None), (2, 7, None),
 (3, 4, None), (3, 6, None), (4, 5, None), (5, 7, None),
 (6, 7, None)]
sage: G.add_edge((2, 3))
sage: G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 5, None), (0, 6, None),
 (1, 2, None), (1, 4, None), (2, 3, None), (2, 5, None),
 (2, 7, None), (3, 4, None), (3, 6, None), (4, 5, None),
 (5, 7, None), (6, 7, None)]
sage: G.add_edges([(0, 4)])
sage: G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 5, None),
 (0, 6, None), (1, 2, None), (1, 4, None), (2, 3, None),
 (2, 5, None), (2, 7, None), (3, 4, None), (3, 6, None),
 (4, 5, None), (5, 7, None), (6, 7, None)]
sage: G.add_edge(2, 4, 'label')
sage: G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 5, None),
 (0, 6, None), (1, 2, None), (1, 4, None), (2, 3, None),
 (2, 4, 'label'), (2, 5, None), (2, 7, None), (3, 4, None),
 (3, 6, None), (4, 5, None), (5, 7, None), (6, 7, None)]
sage: G.add_edge((4, 6, 'label'))
sage: G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 5, None),
 (0, 6, None), (1, 2, None), (1, 4, None), (2, 3, None),
 (2, 4, 'label'), (2, 5, None), (2, 7, None), (3, 4, None),
 (3, 6, None), (4, 5, None), (4, 6, 'label'), (5, 7, None),
 (6, 7, None)]
sage: G.add_edges([(4, 7, 'label')])
sage: G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 5, None),
 (0, 6, None), (1, 2, None), (1, 4, None), (2, 3, None),
 (2, 4, 'label'), (2, 5, None), (2, 7, None), (3, 4, None),
 (3, 6, None), (4, 5, None), (4, 6, 'label'), (4, 7, 'label'),
 (5, 7, None), (6, 7, None)]

Python

>>> from sage.all import *
>>> S = graphs.StaircaseGraph(Integer(4))
>>> G = MatchingCoveredGraph(S)
>>> G.add_edge(Integer(0), Integer(5))
>>> G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 5, None), (0, 6, None),
 (1, 2, None), (1, 4, None), (2, 5, None), (2, 7, None),
 (3, 4, None), (3, 6, None), (4, 5, None), (5, 7, None),
 (6, 7, None)]
>>> G.add_edge((Integer(2), Integer(3)))
>>> G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 5, None), (0, 6, None),
 (1, 2, None), (1, 4, None), (2, 3, None), (2, 5, None),
 (2, 7, None), (3, 4, None), (3, 6, None), (4, 5, None),
 (5, 7, None), (6, 7, None)]
>>> G.add_edges([(Integer(0), Integer(4))])
>>> G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 5, None),
 (0, 6, None), (1, 2, None), (1, 4, None), (2, 3, None),
 (2, 5, None), (2, 7, None), (3, 4, None), (3, 6, None),
 (4, 5, None), (5, 7, None), (6, 7, None)]
>>> G.add_edge(Integer(2), Integer(4), 'label')
>>> G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 5, None),
 (0, 6, None), (1, 2, None), (1, 4, None), (2, 3, None),
 (2, 4, 'label'), (2, 5, None), (2, 7, None), (3, 4, None),
 (3, 6, None), (4, 5, None), (5, 7, None), (6, 7, None)]
>>> G.add_edge((Integer(4), Integer(6), 'label'))
>>> G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 5, None),
 (0, 6, None), (1, 2, None), (1, 4, None), (2, 3, None),
 (2, 4, 'label'), (2, 5, None), (2, 7, None), (3, 4, None),
 (3, 6, None), (4, 5, None), (4, 6, 'label'), (5, 7, None),
 (6, 7, None)]
>>> G.add_edges([(Integer(4), Integer(7), 'label')])
>>> G.edges(sort=False)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 5, None),
 (0, 6, None), (1, 2, None), (1, 4, None), (2, 3, None),
 (2, 4, 'label'), (2, 5, None), (2, 7, None), (3, 4, None),
 (3, 6, None), (4, 5, None), (4, 6, 'label'), (4, 7, 'label'),
 (5, 7, None), (6, 7, None)]

Note that the weight of the edge shall be input as the label:

Sage

sage: G.add_edge((1, 3), label=5)
sage: G.edges()
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 5, None),
 (0, 6, None), (1, 2, None), (1, 3, 5), (1, 4, None),
 (2, 3, None), (2, 4, 'label'), (2, 5, None), (2, 7, None),
 (3, 4, None), (3, 6, None), (4, 5, None), (4, 6, 'label'),
 (4, 7, 'label'), (5, 7, None), (6, 7, None)]
sage: G.add_edge((2, 4, 6), label=6)
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
(((2, 4, 6), None, 6)) is not matching covered

Python

>>> from sage.all import *
>>> G.add_edge((Integer(1), Integer(3)), label=Integer(5))
>>> G.edges()
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 5, None),
 (0, 6, None), (1, 2, None), (1, 3, 5), (1, 4, None),
 (2, 3, None), (2, 4, 'label'), (2, 5, None), (2, 7, None),
 (3, 4, None), (3, 6, None), (4, 5, None), (4, 6, 'label'),
 (4, 7, 'label'), (5, 7, None), (6, 7, None)]
>>> G.add_edge((Integer(2), Integer(4), Integer(6)), label=Integer(6))
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
(((2, 4, 6), None, 6)) is not matching covered

Vertex name cannot be None, so:

Sage

sage: W = graphs.WheelGraph(6)
sage: H = MatchingCoveredGraph(W)
sage: H.add_edge(None, 1)
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
((None, 1, None)) is not matching covered
sage: H.edges(sort=False)  # No alteration to the existing graph
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 5, None), (2, 3, None),
 (3, 4, None), (4, 5, None)]
sage: H.add_edge(None, None)
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
((None, None, None)) is not matching covered
sage: H.edges(sort=False)  # No alteration to the existing graph
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 5, None), (2, 3, None),
 (3, 4, None), (4, 5, None)]

Python

>>> from sage.all import *
>>> W = graphs.WheelGraph(Integer(6))
>>> H = MatchingCoveredGraph(W)
>>> H.add_edge(None, Integer(1))
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
((None, 1, None)) is not matching covered
>>> H.edges(sort=False)  # No alteration to the existing graph
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 5, None), (2, 3, None),
 (3, 4, None), (4, 5, None)]
>>> H.add_edge(None, None)
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
((None, None, None)) is not matching covered
>>> H.edges(sort=False)  # No alteration to the existing graph
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 5, None), (2, 3, None),
 (3, 4, None), (4, 5, None)]

EXAMPLES:

Adding an already existing edge:

Sage

sage: P = graphs.PetersenGraph()
sage: G = MatchingCoveredGraph(P)
sage: G.add_edge(next(G.edge_iterator()))
sage: P == G
True
sage: G.size()
15
sage: G.allow_multiple_edges(True)
sage: G.add_edge(0, 1)
sage: G.size()
16

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> G = MatchingCoveredGraph(P)
>>> G.add_edge(next(G.edge_iterator()))
>>> P == G
True
>>> G.size()
15
>>> G.allow_multiple_edges(True)
>>> G.add_edge(Integer(0), Integer(1))
>>> G.size()
16

Adding an edge such that the resulting graph is matching covered:

Sage

sage: P = graphs.PetersenGraph()
sage: G = MatchingCoveredGraph(P)
sage: G.add_edge(1, 4)
sage: G.edges(sort=False)
[(0, 1, None), (0, 4, None), (0, 5, None), (1, 2, None),
 (1, 4, None), (1, 6, None), (2, 3, None), (2, 7, None),
 (3, 4, None), (3, 8, None), (4, 9, None), (5, 7, None),
 (5, 8, None), (6, 8, None), (6, 9, None), (7, 9, None)]

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> G = MatchingCoveredGraph(P)
>>> G.add_edge(Integer(1), Integer(4))
>>> G.edges(sort=False)
[(0, 1, None), (0, 4, None), (0, 5, None), (1, 2, None),
 (1, 4, None), (1, 6, None), (2, 3, None), (2, 7, None),
 (3, 4, None), (3, 8, None), (4, 9, None), (5, 7, None),
 (5, 8, None), (6, 8, None), (6, 9, None), (7, 9, None)]

Adding an edge with both the incident vertices being existent such that the resulting graph is not matching covered:

Sage

sage: C = graphs.CycleGraph(4)
sage: G = MatchingCoveredGraph(C)
sage: G.add_edge(0, 2)
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
((0, 2, None)) is not matching covered
sage: G.edges(sort=False) # No alteration to the existing graph
[(0, 1, None), (0, 3, None), (1, 2, None), (2, 3, None)]

Python

>>> from sage.all import *
>>> C = graphs.CycleGraph(Integer(4))
>>> G = MatchingCoveredGraph(C)
>>> G.add_edge(Integer(0), Integer(2))
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
((0, 2, None)) is not matching covered
>>> G.edges(sort=False) # No alteration to the existing graph
[(0, 1, None), (0, 3, None), (1, 2, None), (2, 3, None)]

Adding an edge with exactly one incident vertex that is nonexistent throws a ValueError exception, as the resulting graph would have an odd order:

Sage

sage: C = graphs.CycleGraph(4)
sage: G = MatchingCoveredGraph(C)
sage: G.add_edge(0, 4)
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
((0, 4, None)) is not matching covered
sage: G.edges(sort=False) # No alteration to the existing graph
[(0, 1, None), (0, 3, None), (1, 2, None), (2, 3, None)]

Python

>>> from sage.all import *
>>> C = graphs.CycleGraph(Integer(4))
>>> G = MatchingCoveredGraph(C)
>>> G.add_edge(Integer(0), Integer(4))
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
((0, 4, None)) is not matching covered
>>> G.edges(sort=False) # No alteration to the existing graph
[(0, 1, None), (0, 3, None), (1, 2, None), (2, 3, None)]

Adding an edge with both the incident vertices that is nonexistent throws a ValueError exception, as the resulting graph would have been disconnected:

Sage

sage: C = graphs.CycleGraph(4)
sage: G = MatchingCoveredGraph(C)
sage: G.add_edge(4, 5)
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
((4, 5, None)) is not matching covered
sage: G.edges(sort=False) # No alteration to the existing graph
[(0, 1, None), (0, 3, None), (1, 2, None), (2, 3, None)]

Python

>>> from sage.all import *
>>> C = graphs.CycleGraph(Integer(4))
>>> G = MatchingCoveredGraph(C)
>>> G.add_edge(Integer(4), Integer(5))
Traceback (most recent call last):
...
ValueError: the graph obtained after the addition of edge
((4, 5, None)) is not matching covered
>>> G.edges(sort=False) # No alteration to the existing graph
[(0, 1, None), (0, 3, None), (1, 2, None), (2, 3, None)]

Adding a self-loop:

Sage

sage: H = graphs.HeawoodGraph()
sage: G = MatchingCoveredGraph(H)
sage: v = next(G.vertex_iterator())
sage: G.add_edge(v, v)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs

Python

>>> from sage.all import *
>>> H = graphs.HeawoodGraph()
>>> G = MatchingCoveredGraph(H)
>>> v = next(G.vertex_iterator())
>>> G.add_edge(v, v)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs

add_edges(edges, loops=False)

Add edges from an iterable container.

Note

This method overwrites the add_edges() method to ensure that resultant graph is also matching covered.

INPUT:

• edges – an iterable of edges, given either as (u, v) or (u, v, 'label')

• loops – boolean (default: False); note that this shall always be set to either False or None (since matching covered graphs are free of loops), in which case all the loops (v, v, 'label') are removed from the iterator. If loops is set to True, a ValueError is thrown.

OUTPUT:

• If loops is set to True, a ValueError is returned.

• If edges is provided with a valid format, but addition of the edges leave the resulting graph not being matching covered, a ValueError is returned without any alteration to the existing matching covered graph. If the addition of the edges preserves the property of matching covered, then the graph is updated and nothing is returned.

• If edges is provided with an invalid format, a ValueError is returned.

EXAMPLES:

Providing with an empty list of edges:

Sage

sage: C = graphs.CycleGraph(6)
sage: G = MatchingCoveredGraph(C)
sage: G.add_edges([])
sage: G == C
True

Python

>>> from sage.all import *
>>> C = graphs.CycleGraph(Integer(6))
>>> G = MatchingCoveredGraph(C)
>>> G.add_edges([])
>>> G == C
True

Adding some edges, the incident vertices of each of which are existent, such that the resulting graph is matching covered:

Sage

sage: S = graphs.StaircaseGraph(4)
sage: G = MatchingCoveredGraph(S)
sage: F = [(0, 4), (2, 4), (4, 6), (4, 7)]
sage: G.add_edges(F)
sage: G.edges(sort=True)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 6, None),
 (1, 2, None), (1, 4, None), (2, 4, None), (2, 5, None),
 (2, 7, None), (3, 4, None), (3, 6, None), (4, 5, None),
 (4, 6, None), (4, 7, None), (5, 7, None), (6, 7, None)]

Python

>>> from sage.all import *
>>> S = graphs.StaircaseGraph(Integer(4))
>>> G = MatchingCoveredGraph(S)
>>> F = [(Integer(0), Integer(4)), (Integer(2), Integer(4)), (Integer(4), Integer(6)), (Integer(4), Integer(7))]
>>> G.add_edges(F)
>>> G.edges(sort=True)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 6, None),
 (1, 2, None), (1, 4, None), (2, 4, None), (2, 5, None),
 (2, 7, None), (3, 4, None), (3, 6, None), (4, 5, None),
 (4, 6, None), (4, 7, None), (5, 7, None), (6, 7, None)]

Adding some edges, at least one of the incident vertices of some of which are nonexistent such that the resulting graph is matching covered:

Sage

sage: C = graphs.CycleGraph(8)
sage: G = MatchingCoveredGraph(C)
sage: F = [(0, 9), (1, 8), (2, 9), (3, 8),
....:      (4, 9), (5, 8), (6, 9), (7, 8)]
sage: G.add_edges(F)
sage: G.edges(sort=True)
[(0, 1, None), (0, 7, None), (0, 9, None), (1, 2, None),
 (1, 8, None), (2, 3, None), (2, 9, None), (3, 4, None),
 (3, 8, None), (4, 5, None), (4, 9, None), (5, 6, None),
 (5, 8, None), (6, 7, None), (6, 9, None), (7, 8, None)]
sage: G.is_isomorphic(graphs.BiwheelGraph(5))
True

Python

>>> from sage.all import *
>>> C = graphs.CycleGraph(Integer(8))
>>> G = MatchingCoveredGraph(C)
>>> F = [(Integer(0), Integer(9)), (Integer(1), Integer(8)), (Integer(2), Integer(9)), (Integer(3), Integer(8)),
...      (Integer(4), Integer(9)), (Integer(5), Integer(8)), (Integer(6), Integer(9)), (Integer(7), Integer(8))]
>>> G.add_edges(F)
>>> G.edges(sort=True)
[(0, 1, None), (0, 7, None), (0, 9, None), (1, 2, None),
 (1, 8, None), (2, 3, None), (2, 9, None), (3, 4, None),
 (3, 8, None), (4, 5, None), (4, 9, None), (5, 6, None),
 (5, 8, None), (6, 7, None), (6, 9, None), (7, 8, None)]
>>> G.is_isomorphic(graphs.BiwheelGraph(Integer(5)))
True

Adding a removable double ear to a matching covered graph:

Sage

sage: H = graphs.HexahedralGraph()
sage: G = MatchingCoveredGraph(H)
sage: F = {(0, 8, None), (1, 10), (4, 11, 'label'),
....:      (5, 9), (8, 9), (10, 11)}
sage: G.add_edges(F)
sage: G.edges(sort=True)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 8, None),
 (1, 2, None), (1, 5, None), (1, 10, None), (2, 3, None),
 (2, 6, None), (3, 7, None), (4, 5, None), (4, 7, None),
 (4, 11, 'label'), (5, 6, None), (5, 9, None), (6, 7, None),
 (8, 9, None), (10, 11, None)]

Python

>>> from sage.all import *
>>> H = graphs.HexahedralGraph()
>>> G = MatchingCoveredGraph(H)
>>> F = {(Integer(0), Integer(8), None), (Integer(1), Integer(10)), (Integer(4), Integer(11), 'label'),
...      (Integer(5), Integer(9)), (Integer(8), Integer(9)), (Integer(10), Integer(11))}
>>> G.add_edges(F)
>>> G.edges(sort=True)
[(0, 1, None), (0, 3, None), (0, 4, None), (0, 8, None),
 (1, 2, None), (1, 5, None), (1, 10, None), (2, 3, None),
 (2, 6, None), (3, 7, None), (4, 5, None), (4, 7, None),
 (4, 11, 'label'), (5, 6, None), (5, 9, None), (6, 7, None),
 (8, 9, None), (10, 11, None)]

Adding some edges, the incident vertices of each of which are existent, such that the resulting graph is NOT matching covered:

Sage

sage: C = graphs.CycleGraph(6)
sage: G = MatchingCoveredGraph(C)
sage: F = [(0, 2), (3, 5)]
sage: G.add_edges(F)
Traceback (most recent call last):
...
ValueError: the resulting graph after the addition ofthe edges is not matching covered

Python

>>> from sage.all import *
>>> C = graphs.CycleGraph(Integer(6))
>>> G = MatchingCoveredGraph(C)
>>> F = [(Integer(0), Integer(2)), (Integer(3), Integer(5))]
>>> G.add_edges(F)
Traceback (most recent call last):
...
ValueError: the resulting graph after the addition ofthe edges is not matching covered

Adding some edges, at least one of the incident vertices of some of which are nonexistent such that the resulting graph is NOT matching covered:

Sage

sage: H = graphs.HexahedralGraph()
sage: G = MatchingCoveredGraph(H)
sage: F = [(3, 8), (6, 9), (8, 9)]
sage: G.add_edges(F)
Traceback (most recent call last):
...
ValueError: the resulting graph after the addition ofthe edges is not matching covered
sage: I = [(0, 8), (1, 9)]
sage: G.add_edges(I)
Traceback (most recent call last):
...
ValueError: the resulting graph after the addition ofthe edges is not matching covered
sage: J = [(u, 8) for u in range(8)]
sage: G.add_edges(J)
Traceback (most recent call last):
...
ValueError: odd order is not allowed for matching covered graphs

Python

>>> from sage.all import *
>>> H = graphs.HexahedralGraph()
>>> G = MatchingCoveredGraph(H)
>>> F = [(Integer(3), Integer(8)), (Integer(6), Integer(9)), (Integer(8), Integer(9))]
>>> G.add_edges(F)
Traceback (most recent call last):
...
ValueError: the resulting graph after the addition ofthe edges is not matching covered
>>> I = [(Integer(0), Integer(8)), (Integer(1), Integer(9))]
>>> G.add_edges(I)
Traceback (most recent call last):
...
ValueError: the resulting graph after the addition ofthe edges is not matching covered
>>> J = [(u, Integer(8)) for u in range(Integer(8))]
>>> G.add_edges(J)
Traceback (most recent call last):
...
ValueError: odd order is not allowed for matching covered graphs

Setting the parameter loops to either False or None:

Sage

sage: W = graphs.WheelGraph(6)
sage: G = MatchingCoveredGraph(W)
sage: F = [(0, 0), (1, 3), (2, 4)]
sage: G.add_edges(edges=F, loops=False)
sage: G.edges(sort=True)
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 3, None), (1, 5, None),
 (2, 3, None), (2, 4, None), (3, 4, None), (4, 5, None)]
sage: J = [(1, 1), (3, 5)]
sage: G.add_edges(edges=J, loops=True)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
sage: G.edges(sort=True)
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 3, None), (1, 5, None),
 (2, 3, None), (2, 4, None), (3, 4, None), (4, 5, None)]

Python

>>> from sage.all import *
>>> W = graphs.WheelGraph(Integer(6))
>>> G = MatchingCoveredGraph(W)
>>> F = [(Integer(0), Integer(0)), (Integer(1), Integer(3)), (Integer(2), Integer(4))]
>>> G.add_edges(edges=F, loops=False)
>>> G.edges(sort=True)
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 3, None), (1, 5, None),
 (2, 3, None), (2, 4, None), (3, 4, None), (4, 5, None)]
>>> J = [(Integer(1), Integer(1)), (Integer(3), Integer(5))]
>>> G.add_edges(edges=J, loops=True)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
>>> G.edges(sort=True)
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 3, None), (1, 5, None),
 (2, 3, None), (2, 4, None), (3, 4, None), (4, 5, None)]

Setting the parameter loops to True:

Sage

sage: P = graphs.PetersenGraph()
sage: G = MatchingCoveredGraph(P)
sage: F = [(0, 0), (0, 2), (0, 3)]
sage: G.add_edges(edges=F, loops=True)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> G = MatchingCoveredGraph(P)
>>> F = [(Integer(0), Integer(0)), (Integer(0), Integer(2)), (Integer(0), Integer(3))]
>>> G.add_edges(edges=F, loops=True)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs

Adding a multiple edge:

Sage

sage: S = graphs.StaircaseGraph(4)
sage: G = MatchingCoveredGraph(S)
sage: G.allow_multiple_edges(True)
sage: F = [(0, 1, 'label'), (0, 4), (1, 2)]
sage: G.add_edges(F)
sage: G.edges(sort=False)
[(0, 1, None), (0, 1, 'label'), (0, 3, None), (0, 4, None),
 (0, 6, None), (1, 2, None), (1, 2, None), (1, 4, None),
 (2, 5, None), (2, 7, None), (3, 4, None), (3, 6, None),
 (4, 5, None), (5, 7, None), (6, 7, None)]

Python

>>> from sage.all import *
>>> S = graphs.StaircaseGraph(Integer(4))
>>> G = MatchingCoveredGraph(S)
>>> G.allow_multiple_edges(True)
>>> F = [(Integer(0), Integer(1), 'label'), (Integer(0), Integer(4)), (Integer(1), Integer(2))]
>>> G.add_edges(F)
>>> G.edges(sort=False)
[(0, 1, None), (0, 1, 'label'), (0, 3, None), (0, 4, None),
 (0, 6, None), (1, 2, None), (1, 2, None), (1, 4, None),
 (2, 5, None), (2, 7, None), (3, 4, None), (3, 6, None),
 (4, 5, None), (5, 7, None), (6, 7, None)]

add_vertex(name=None)

Add a vertex to the (matching covered) graph.

Note

This method overwrites the add_vertex() method to ensure that isolated vertices are forbidden in MatchingCoveredGraph.

INPUT:

• name – an immutable object (default: None); when no name is specified (default), then the new vertex will be represented by the least integer not already representing a vertex. name must be an immutable object (e.g., an integer, a tuple, etc.).

OUTPUT:

• If name specifies an existing vertex, then nothing is done. Otherwise a ValueError is returned with no change to the existing (matching covered) graph is returned since matching covered graphs are free of isolated vertices.

EXAMPLES:

Adding an existing vertex:

Sage

sage: P = graphs.PetersenGraph()
sage: P
Petersen graph: Graph on 10 vertices
sage: G = MatchingCoveredGraph(P)
sage: G
Matching covered petersen graph: graph on 10 vertices
sage: u = next(G.vertex_iterator())
sage: G.add_vertex(u)
sage: G
Matching covered petersen graph: graph on 10 vertices

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> P
Petersen graph: Graph on 10 vertices
>>> G = MatchingCoveredGraph(P)
>>> G
Matching covered petersen graph: graph on 10 vertices
>>> u = next(G.vertex_iterator())
>>> G.add_vertex(u)
>>> G
Matching covered petersen graph: graph on 10 vertices

Adding a new/ non-existing vertex:

Sage

sage: G.add_vertex()
Traceback (most recent call last):
...
ValueError: isolated vertices are not allowed in matching covered graphs
sage: u = 100
sage: G.add_vertex(u)
Traceback (most recent call last):
...
ValueError: isolated vertices are not allowed in matching covered graphs

Python

>>> from sage.all import *
>>> G.add_vertex()
Traceback (most recent call last):
...
ValueError: isolated vertices are not allowed in matching covered graphs
>>> u = Integer(100)
>>> G.add_vertex(u)
Traceback (most recent call last):
...
ValueError: isolated vertices are not allowed in matching covered graphs

add_vertices(vertices)

Add vertices to the (matching covered) graph from an iterable container of vertices.

Note

This method overwrites the add_vertices() method to ensure that isolated vertices are forbidden in MatchingCoveredGraph.

INPUT:

• vertices – iterator container of vertex labels. A new label is created, used and returned in the output list for all None values in vertices.

OUTPUT:

• If all of the vertices are existing vertices of the (matching covered) graph, then nothing is done; otherwise a ValueError is returned with no change to the existing (matching covered) graph since matching covered graphs are free of isolated vertices.

EXAMPLES:

Adding a list of already existing vertices:

Sage

sage: T = graphs.TruncatedBiwheelGraph(15)
sage: T
Truncated biwheel graph: Graph on 30 vertices
sage: G = MatchingCoveredGraph(T)
sage: G
Matching covered truncated biwheel graph: graph on 30 vertices
sage: S = [0, 1, 2, 3]  # We choose 4 existing vertices
sage: G.add_vertices(S)
sage: G
Matching covered truncated biwheel graph: graph on 30 vertices

Python

>>> from sage.all import *
>>> T = graphs.TruncatedBiwheelGraph(Integer(15))
>>> T
Truncated biwheel graph: Graph on 30 vertices
>>> G = MatchingCoveredGraph(T)
>>> G
Matching covered truncated biwheel graph: graph on 30 vertices
>>> S = [Integer(0), Integer(1), Integer(2), Integer(3)]  # We choose 4 existing vertices
>>> G.add_vertices(S)
>>> G
Matching covered truncated biwheel graph: graph on 30 vertices

Adding a list of vertices in which at least one is non-existent or None or possibly both:

Sage

sage: T = graphs.CompleteGraph(2)
sage: T
Complete graph: Graph on 2 vertices
sage: G = MatchingCoveredGraph(T)
sage: G
Matching covered complete graph: graph on 2 vertices
sage: S1 = [2, 3, 4]
sage: G.add_vertices(S1)
Traceback (most recent call last):
...
ValueError: isolated vertices are not allowed in matching covered graphs
sage: S2 = [None, None]
sage: G.add_vertices(S2)
Traceback (most recent call last):
...
ValueError: isolated vertices are not allowed in matching covered graphs
sage: S3 = [2, None, None, 5]
sage: G.add_vertices(S3)
Traceback (most recent call last):
...
ValueError: isolated vertices are not allowed in matching covered graphs

Python

>>> from sage.all import *
>>> T = graphs.CompleteGraph(Integer(2))
>>> T
Complete graph: Graph on 2 vertices
>>> G = MatchingCoveredGraph(T)
>>> G
Matching covered complete graph: graph on 2 vertices
>>> S1 = [Integer(2), Integer(3), Integer(4)]
>>> G.add_vertices(S1)
Traceback (most recent call last):
...
ValueError: isolated vertices are not allowed in matching covered graphs
>>> S2 = [None, None]
>>> G.add_vertices(S2)
Traceback (most recent call last):
...
ValueError: isolated vertices are not allowed in matching covered graphs
>>> S3 = [Integer(2), None, None, Integer(5)]
>>> G.add_vertices(S3)
Traceback (most recent call last):
...
ValueError: isolated vertices are not allowed in matching covered graphs

allow_loops(new, check=True)

Change whether loops are allowed in (matching covered) graphs.

Note

This method overwrites the allow_loops() method to ensure that loops are forbidden in MatchingCoveredGraph.

INPUT:

• new – boolean

• check – boolean (default: True); whether to remove existing loops from the graph when the new status is False. It is an argument in allow_loops() method and is not used in this overwritten one.

OUTPUT:

• A ValueError is returned with no change to the existing (matching covered) graph if new is True since a matching covered graph, by definition, is free of self-loops. If new is set to False, there is no output.

EXAMPLES:

Petersen graph is matching covered:

Sage

sage: P = graphs.PetersenGraph()
sage: P.is_matching_covered()
True
sage: G = MatchingCoveredGraph(P)
sage: G.allow_loops(True)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> P.is_matching_covered()
True
>>> G = MatchingCoveredGraph(P)
>>> G.allow_loops(True)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs

See also

• allows_loops()

• has_loops()

• loop_edges()

• loop_vertices()

• loops()

• number_of_loops()

• remove_loops()

allows_loops()

Return whether loops are permitted in (matching covered) graphs.

Note

This method overwrites the allows_loops() method to show that loops are forbidden in MatchingCoveredGraph.

OUTPUT:

• A boolean value False is returned, since matching covered graphs, by definition, are free of loops.

EXAMPLES:

Petersen graph is matching covered:

Sage

sage: P = graphs.PetersenGraph()
sage: P.is_matching_covered()
True
sage: G = MatchingCoveredGraph(P)
sage: G.allows_loops()
False

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> P.is_matching_covered()
True
>>> G = MatchingCoveredGraph(P)
>>> G.allows_loops()
False

See also

• allow_loops()

• has_loops()

• loop_edges()

• loop_vertices()

• loops()

• number_of_loops()

• remove_loops()

canonical_partition()

Return the canonical partition of the (matching covered) graph.

For a matching covered graph \(G\), a subset \(B\) of the vertex set \(V\) is a barrier if \(|B| = o(G - B)\), where \(|B|\) denotes the cardinality of the set \(B\) and \(o(G - B)\) denotes the number of odd components in the graph \(G - B\). And a barrier \(B\) is a maximal barrier if \(C\) is not a barrier for each \(C\) such that \(B \subset C \subseteq V\).

Note that in a matching covered graph, each vertex belongs to a unique maximal barrier. The maximal barriers of a matching covered graph partitions its vertex set and the partition of the vertex set of a matching covered graph into its maximal barriers is called as its canonical partition.

OUTPUT:

• A list of sets that constitute a (canonical) partition of the vertex set, wherein each set is a (unique) maximal barrier of the (matching covered) graph.

EXAMPLES:

Show the maximal barrier of the graph \(K_4 \odot K_{3, 3}\):

Sage

sage: G = Graph([
....:    (0, 2), (0, 3), (0, 4), (1, 2),
....:    (1, 3), (1, 4), (2, 5), (3, 6),
....:    (4, 7), (5, 6), (5, 7), (6, 7)
....: ])
sage: H = MatchingCoveredGraph(G)
sage: H.canonical_partition()
[{0}, {1}, {2, 3, 4}, {5}, {6}, {7}]

Python

>>> from sage.all import *
>>> G = Graph([
...    (Integer(0), Integer(2)), (Integer(0), Integer(3)), (Integer(0), Integer(4)), (Integer(1), Integer(2)),
...    (Integer(1), Integer(3)), (Integer(1), Integer(4)), (Integer(2), Integer(5)), (Integer(3), Integer(6)),
...    (Integer(4), Integer(7)), (Integer(5), Integer(6)), (Integer(5), Integer(7)), (Integer(6), Integer(7))
... ])
>>> H = MatchingCoveredGraph(G)
>>> H.canonical_partition()
[{0}, {1}, {2, 3, 4}, {5}, {6}, {7}]

For a bicritical graph (for instance, the Petersen graph), the canonical parition constitutes of only singleton sets each containing an individual vertex:

Sage

sage: P = graphs.PetersenGraph()
sage: G = MatchingCoveredGraph(P)
sage: G.canonical_partition()
[{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}]

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> G = MatchingCoveredGraph(P)
>>> G.canonical_partition()
[{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}]

For a bipartite matching covered graph (for instance, the Hexahedral graph), the canonical partition consists of two sets each of which corresponds to the individual color class:

Sage

sage: H = graphs.HexahedralGraph()
sage: G = MatchingCoveredGraph(H)
sage: G.canonical_partition()
[{0, 2, 5, 7}, {1, 3, 4, 6}]
sage: B = BipartiteGraph(H)
sage: list(B.bipartition()) == G.canonical_partition()
True

Python

>>> from sage.all import *
>>> H = graphs.HexahedralGraph()
>>> G = MatchingCoveredGraph(H)
>>> G.canonical_partition()
[{0, 2, 5, 7}, {1, 3, 4, 6}]
>>> B = BipartiteGraph(H)
>>> list(B.bipartition()) == G.canonical_partition()
True

REFERENCES:

• [LM2024]

See also

• is_bicritical()

• is_matching_covered()

• maximal_barrier()

delete_vertex(vertex, in_order=False)

Delete a vertex, removing all incident edges.

Note

This method overwrites the delete_vertex() method to ensure that an odd order is forbidden in MatchingCoveredGraph.

INPUT:

• vertex – a vertex that is to be deleted.

• in_order – boolean (default: False); if True, this deletes the \(i\)-th vertex in the sorted list of vertices, i.e. G.vertices(sort=True)[i]

OUTPUT:

• Deleting a non-existent vertex raises a ValueError exception; also a (different) ValueError is returned on deleting an existing vertex since matching covered graphs are of even order. In both cases no modifications are made to the existing (matching covered) graph.

EXAMPLES:

Deleting a non-existent vertex:

Sage

sage: W = graphs.WheelGraph(12)
sage: G = MatchingCoveredGraph(W)
sage: u = 100
sage: G.delete_vertex(u)
Traceback (most recent call last):
...
ValueError: vertex (100) not in the graph
sage: G.delete_vertex(vertex=u, in_order=True)
Traceback (most recent call last):
...
ValueError: vertex (100) not in the graph

Python

>>> from sage.all import *
>>> W = graphs.WheelGraph(Integer(12))
>>> G = MatchingCoveredGraph(W)
>>> u = Integer(100)
>>> G.delete_vertex(u)
Traceback (most recent call last):
...
ValueError: vertex (100) not in the graph
>>> G.delete_vertex(vertex=u, in_order=True)
Traceback (most recent call last):
...
ValueError: vertex (100) not in the graph

Deleting an existing vertex:

Sage

sage: W = graphs.WheelGraph(12)
sage: G = MatchingCoveredGraph(W)
sage: u = next(G.vertex_iterator())
sage: G.delete_vertex(u)
Traceback (most recent call last):
...
ValueError: odd order is not allowed for matching covered graphs
sage: G.delete_vertex(vertex=u, in_order=True)
Traceback (most recent call last):
...
ValueError: odd order is not allowed for matching covered graphs

Python

>>> from sage.all import *
>>> W = graphs.WheelGraph(Integer(12))
>>> G = MatchingCoveredGraph(W)
>>> u = next(G.vertex_iterator())
>>> G.delete_vertex(u)
Traceback (most recent call last):
...
ValueError: odd order is not allowed for matching covered graphs
>>> G.delete_vertex(vertex=u, in_order=True)
Traceback (most recent call last):
...
ValueError: odd order is not allowed for matching covered graphs

delete_vertices(vertices)

Delete specified vertices form self.

This method deletes the vertices from the iterable container vertices from self along with incident edges. An error is raised if the resulting graph is not matching covered.

Note

This method overwrites the delete_vertices() method to ensure that an odd order is forbidden in MatchingCoveredGraph.

INPUT:

• vertices – a list/ set of vertices that are to be deleted.

OUTPUT:

• Deleting a non-existent vertex will raise a ValueError exception, in which case none of the vertices in vertices is deleted.

• If all of the vertices in the list/ set provided exist in the graph, but the resulting graph after deletion of all of those is not matching covered, then a ValueError exception is raised without any alterations to the existing (matching covered) graph, otherwise the vertices are deleted and nothing is returned.

EXAMPLES:

Providing with an empty list of vertices:

Sage

sage: C = graphs.CycleGraph(6)
sage: G = MatchingCoveredGraph(C)
sage: G.delete_vertices([])
sage: G == C
True

Python

>>> from sage.all import *
>>> C = graphs.CycleGraph(Integer(6))
>>> G = MatchingCoveredGraph(C)
>>> G.delete_vertices([])
>>> G == C
True

Removing all the existent vertices:

Sage

sage: M = graphs.MoebiusLadderGraph(10)
sage: G = MatchingCoveredGraph(M)
sage: S = list(G.vertices())
sage: G.delete_vertices(S)
Traceback (most recent call last):
...
ValueError: the resulting graph after the removal of the vertices
is trivial, therefore is not matching covered

Python

>>> from sage.all import *
>>> M = graphs.MoebiusLadderGraph(Integer(10))
>>> G = MatchingCoveredGraph(M)
>>> S = list(G.vertices())
>>> G.delete_vertices(S)
Traceback (most recent call last):
...
ValueError: the resulting graph after the removal of the vertices
is trivial, therefore is not matching covered

Providing with a list of vertices with at least one non-existent vertex:

Sage

sage: S = graphs.StaircaseGraph(4)
sage: S
Staircase graph: Graph on 8 vertices
sage: G = MatchingCoveredGraph(S)
sage: G
Matching covered staircase graph: graph on 8 vertices
sage: T = list(range(5, 20, 2))
sage: G.delete_vertices(T)
Traceback (most recent call last):
...
ValueError: vertex (9) not in the graph

Python

>>> from sage.all import *
>>> S = graphs.StaircaseGraph(Integer(4))
>>> S
Staircase graph: Graph on 8 vertices
>>> G = MatchingCoveredGraph(S)
>>> G
Matching covered staircase graph: graph on 8 vertices
>>> T = list(range(Integer(5), Integer(20), Integer(2)))
>>> G.delete_vertices(T)
Traceback (most recent call last):
...
ValueError: vertex (9) not in the graph

Removing an odd no. of distinct vertices from a matching covered graph:

Sage

sage: P = graphs.PetersenGraph()
sage: G = MatchingCoveredGraph(P)
sage: S = [0, 1, 2, 10, 10, 100]
sage: G.delete_vertices(S)
Traceback (most recent call last):
...
ValueError: an odd no. of distinct vertices can not be
removed from a matching covered graph

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> G = MatchingCoveredGraph(P)
>>> S = [Integer(0), Integer(1), Integer(2), Integer(10), Integer(10), Integer(100)]
>>> G.delete_vertices(S)
Traceback (most recent call last):
...
ValueError: an odd no. of distinct vertices can not be
removed from a matching covered graph

Providing with a list of existent vertices whose deletion results in a graph which is not matching covered:

Sage

sage: S = graphs.StaircaseGraph(4)
sage: S
Staircase graph: Graph on 8 vertices
sage: G = MatchingCoveredGraph(S)
sage: G
Matching covered staircase graph: graph on 8 vertices
sage: T = [1, 4]
sage: G.delete_vertices(T)
Traceback (most recent call last):
...
ValueError: the resulting graph after the removal of
the vertices is not matching covered

Python

>>> from sage.all import *
>>> S = graphs.StaircaseGraph(Integer(4))
>>> S
Staircase graph: Graph on 8 vertices
>>> G = MatchingCoveredGraph(S)
>>> G
Matching covered staircase graph: graph on 8 vertices
>>> T = [Integer(1), Integer(4)]
>>> G.delete_vertices(T)
Traceback (most recent call last):
...
ValueError: the resulting graph after the removal of
the vertices is not matching covered

Providing with a list of existent vertices after the deletion of which the resulting graph is still matching covered; note that in the following example, after the deletion of two vertices from a staircase graph, the resulting graph is NOT a staircase graph (see Issue #38768):

Sage

sage: S = graphs.StaircaseGraph(4)
sage: S
Staircase graph: Graph on 8 vertices
sage: G = MatchingCoveredGraph(S)
sage: G
Matching covered staircase graph: graph on 8 vertices
sage: T = [6, 7]
sage: G.delete_vertices(T)
sage: G  # Matching covered graph on 6 vertices
Matching covered staircase graph: graph on 6 vertices

Python

>>> from sage.all import *
>>> S = graphs.StaircaseGraph(Integer(4))
>>> S
Staircase graph: Graph on 8 vertices
>>> G = MatchingCoveredGraph(S)
>>> G
Matching covered staircase graph: graph on 8 vertices
>>> T = [Integer(6), Integer(7)]
>>> G.delete_vertices(T)
>>> G  # Matching covered graph on 6 vertices
Matching covered staircase graph: graph on 6 vertices

get_matching()

Return an EdgesView of self._matching.

OUTPUT:

• This method returns EdgesView of the edges of a perfect matching of the (matching covered) graph.

EXAMPLES:

If one specifies a perfect matching while initializing the object, the value of self._matching is captures the same matching:

Sage

sage: P = graphs.PetersenGraph()
sage: M = [(0, 1), (2, 3), (4, 9), (5, 7), (6, 8)]
sage: G = MatchingCoveredGraph(P, M)
sage: sorted(G.get_matching())
[(0, 1), (2, 3), (4, 9), (5, 7), (6, 8)]
sage: M == sorted(G.get_matching())
True

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> M = [(Integer(0), Integer(1)), (Integer(2), Integer(3)), (Integer(4), Integer(9)), (Integer(5), Integer(7)), (Integer(6), Integer(8))]
>>> G = MatchingCoveredGraph(P, M)
>>> sorted(G.get_matching())
[(0, 1), (2, 3), (4, 9), (5, 7), (6, 8)]
>>> M == sorted(G.get_matching())
True

If no matching is specified while initilizing a matching covered graph, a perfect is computed matching() and that is captured as self._matching:

Sage

sage: P = graphs.PetersenGraph()
sage: M = P.matching()
sage: G = MatchingCoveredGraph(P)
sage: sorted(G.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]
sage: sorted(M) == sorted(G.get_matching())
True

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> M = P.matching()
>>> G = MatchingCoveredGraph(P)
>>> sorted(G.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]
>>> sorted(M) == sorted(G.get_matching())
True

has_loops()

Check whether there are loops in the (matching covered) graph.

Note

This method overwrites the has_loops() method in order to return False as matching covered graphs are always free of looped edges.

OUTPUT:

• A boolean False is returned since matching covered graphs, by definition, are free of self-loops.

EXAMPLES:

A matching covered graph, for instance the Petersen graph, is always free of loops:

Sage

sage: P = graphs.PetersenGraph()
sage: G = MatchingCoveredGraph(P)
sage: G
Matching covered petersen graph: graph on 10 vertices
sage: G.has_loops()
False
sage: G.allows_loops()
False
sage: G.add_edge(0, 0)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> G = MatchingCoveredGraph(P)
>>> G
Matching covered petersen graph: graph on 10 vertices
>>> G.has_loops()
False
>>> G.allows_loops()
False
>>> G.add_edge(Integer(0), Integer(0))
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs

A matching covered graph may support multiple edges, still no loops are allowed:

Sage

sage: K = graphs.CompleteGraph(2)
sage: G = MatchingCoveredGraph(K)
sage: G.allow_multiple_edges(True)
sage: G
Matching covered complete graph: multi-graph on 2 vertices
sage: G.add_edge(0, 1, 'label')
sage: G.add_edge(0, 0)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
sage: G.edges(sort=False)
[(0, 1, None), (0, 1, 'label')]
sage: G.allows_loops()
False
sage: G.has_loops()
False
sage: G.allow_loops(True)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs

Python

>>> from sage.all import *
>>> K = graphs.CompleteGraph(Integer(2))
>>> G = MatchingCoveredGraph(K)
>>> G.allow_multiple_edges(True)
>>> G
Matching covered complete graph: multi-graph on 2 vertices
>>> G.add_edge(Integer(0), Integer(1), 'label')
>>> G.add_edge(Integer(0), Integer(0))
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
>>> G.edges(sort=False)
[(0, 1, None), (0, 1, 'label')]
>>> G.allows_loops()
False
>>> G.has_loops()
False
>>> G.allow_loops(True)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs

See also

• allow_loops()

• allows_loops()

• loop_edges()

• loop_vertices()

• loops()

• number_of_loops()

• remove_loops()

has_perfect_matching(G, algorithm, solver='Edmonds', verbose=None, integrality_tolerance=0)

Check whether the graph has a perfect matching.

Note

This method overwrites the has_perfect_matching() method in order to return True (provided the input arguments are valid) as matching covered graphs always admit a perfect matching.

INPUT:

• algorithm – string (default: 'Edmonds')

  • 'Edmonds' uses Edmonds’ algorithm as implemented in NetworkX to find a matching of maximal cardinality, then check whether this cardinality is half the number of vertices of the graph.

  • 'LP_matching' uses a Linear Program to find a matching of maximal cardinality, then check whether this cardinality is half the number of vertices of the graph.

  • 'LP' uses a Linear Program formulation of the perfect matching problem: put a binary variable b[e] on each edge \(e\), and for each vertex \(v\), require that the sum of the values of the edges incident to \(v\) is 1.

• solver – string (default: None); specifies a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• verbose – integer (default: 0); sets the level of verbosity: set to 0 by default, which means quiet (only useful when algorithm == "LP_matching" or algorithm == "LP")

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

OUTPUT:

• If the input arguments are valid, a boolean (True) is returned as a maximum matching of a matching covered graph is always a perfect matching, otherwise a ValueError is raised.

EXAMPLES:

Note that regardless of the algorithm (as long as the input arguments are in valid format), the method always returns the boolean True:

Sage

sage: P = graphs.PetersenGraph()
sage: P.has_perfect_matching()  # Calls Graph.has_perfect_matching()
True
sage: G = MatchingCoveredGraph(P)
sage: G.has_perfect_matching()  # Calls MatchingCoveredGraph.has_perfect_matching()
True
sage: W = graphs.WheelGraph(6)
sage: H = MatchingCoveredGraph(W)
sage: H.has_perfect_matching(algorithm='LP_matching')
True

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> P.has_perfect_matching()  # Calls Graph.has_perfect_matching()
True
>>> G = MatchingCoveredGraph(P)
>>> G.has_perfect_matching()  # Calls MatchingCoveredGraph.has_perfect_matching()
True
>>> W = graphs.WheelGraph(Integer(6))
>>> H = MatchingCoveredGraph(W)
>>> H.has_perfect_matching(algorithm='LP_matching')
True

Providing with an algorithm, that is not one of 'Edmonds', 'LP_matching' or 'LP':

Sage

sage: S = graphs.StaircaseGraph(4)
sage: J = MatchingCoveredGraph(S)
sage: J.has_perfect_matching(algorithm='algorithm')
Traceback (most recent call last):
...
ValueError: algorithm must be set to 'Edmonds',
'LP_matching' or 'LP'

Python

>>> from sage.all import *
>>> S = graphs.StaircaseGraph(Integer(4))
>>> J = MatchingCoveredGraph(S)
>>> J.has_perfect_matching(algorithm='algorithm')
Traceback (most recent call last):
...
ValueError: algorithm must be set to 'Edmonds',
'LP_matching' or 'LP'

is_brace(coNP_certificate=False)

Check if the (matching covered) graph is a brace.

A matching covered graph which is free of nontrivial tight cuts is called a brace if it is bipartite. Let \(G := (A \cup B, E)\) be a bipartite matching covered graph on six or more vertices. The following statements are equivalent [LM2024]:

1. \(G\) is a brace (aka free of nontrivial tight cuts).

2. \(G - a_1 - a_2 - b_1 - b_2\) has a perfect matching for any two distinct vertices \(a_1\) and \(a_2\) in \(A\) and any two distinct vertices \(b_1\) and \(b_2\) in \(B\).

3. \(G\) is two extendable (any two nonadjacent distinct edges can be extended to some perfect matching of \(G\)).

4. \(|N(X)| \geq |X| + 2\), for all \(X ⊂ A\) such that \(0 < |X| < |A| - 1\), where \(N(S) := \{b \mid (a, b) \in E ∧ a \in S\}\) is called the neighboring set of \(S\).

5. \(G - a - b\) is matching covered, for some perfect matching \(M\) of \(G\) and for each edge \(ab\) in \(M\).

We shall be using the 5th characterization mentioned above in order to determine whether the provided bipartite matching covered graph is a brace or not using M-alternating tree search [LZ2001].

INPUT:

• coNP_certificate – boolean (default: False)

OUTPUT:

• If the input matching covered graph is not bipartite, a ValueError is returned.

• If the input bipartite matching covered graph is a brace, a boolean True is returned if coNP_certificate is set to False otherwise a 5-tuple (True, None, None, None, None) is returned.

• If the input bipartite matching covered graph is not a brace, a boolean False is returned if coNP_certificate is set to False otherwise a 5-tuple of

  1. a boolean False,

  2. a list of edges constituting a nontrivial tight cut (which is a nontrivial barrier cut)

  3. a set of vertices of one of the shores of the nontrivial tight cut

  4. a string ‘nontrivial tight cut’

  5. a set of vertices showing the respective barrier

  is returned.

EXAMPLES:

The complete graph on two vertices \(K_2\) is the smallest brace:

Sage

sage: K = graphs.CompleteGraph(2)
sage: G = MatchingCoveredGraph(K)
sage: G.is_brace()
True

Python

>>> from sage.all import *
>>> K = graphs.CompleteGraph(Integer(2))
>>> G = MatchingCoveredGraph(K)
>>> G.is_brace()
True

The cycle graph on four vertices \(C_4\) is a brace:

Sage

sage: C = graphs.CycleGraph(4)
sage: G = MatchingCoveredGraph(C)
sage: G.is_brace()
True

Python

>>> from sage.all import *
>>> C = graphs.CycleGraph(Integer(4))
>>> G = MatchingCoveredGraph(C)
>>> G.is_brace()
True

Each graph that is isomorphic to a biwheel is a brace:

Sage

sage: B = graphs.BiwheelGraph(15)
sage: G = MatchingCoveredGraph(B)
sage: G.is_brace()
True

Python

>>> from sage.all import *
>>> B = graphs.BiwheelGraph(Integer(15))
>>> G = MatchingCoveredGraph(B)
>>> G.is_brace()
True

A circular ladder graph of order eight or more on \(2n\) vertices for an even \(n\) is a brace:

Sage

sage: n = 10
sage: CL = graphs.CircularLadderGraph(n)
sage: G = MatchingCoveredGraph(CL)
sage: G.is_brace()
True

Python

>>> from sage.all import *
>>> n = Integer(10)
>>> CL = graphs.CircularLadderGraph(n)
>>> G = MatchingCoveredGraph(CL)
>>> G.is_brace()
True

A moebius ladder graph of order six or more on \(2n\) vertices for an odd \(n\) is a brace:

Sage

sage: n = 11
sage: ML = graphs.MoebiusLadderGraph(n)
sage: G = MatchingCoveredGraph(ML)
sage: G.is_brace()
True

Python

>>> from sage.all import *
>>> n = Integer(11)
>>> ML = graphs.MoebiusLadderGraph(n)
>>> G = MatchingCoveredGraph(ML)
>>> G.is_brace()
True

Note that the union of the above mentioned four families of braces, that are:

1. the biwheel graph BiwheelGraph(n),

2. the circular ladder graph CircularLadderGraph(n) for even n,

3. the moebius ladder graph MoebiusLadderGraph(n) for odd n,

is referred to as the McCuaig family of braces.

The only simple brace of order six is the complete graph of the same order, that is \(K_{3, 3}\):

Sage

sage: L = list(graphs(6,
....:          lambda G: G.size() <= 15 and
....:                    G.is_bipartite())
....: )
sage: L = list(G for G in L if G.is_connected() and
....:                          G.is_matching_covered()
....: )
sage: M = list(MatchingCoveredGraph(G) for G in L)
sage: B = list(G for G in M if G.is_brace())
sage: K = graphs.CompleteBipartiteGraph(3, 3)
sage: G = MatchingCoveredGraph(K)
sage: next(iter(B)).is_isomorphic(G)
True

Python

>>> from sage.all import *
>>> L = list(graphs(Integer(6),
...          lambda G: G.size() <= Integer(15) and
...                    G.is_bipartite())
... )
>>> L = list(G for G in L if G.is_connected() and
...                          G.is_matching_covered()
... )
>>> M = list(MatchingCoveredGraph(G) for G in L)
>>> B = list(G for G in M if G.is_brace())
>>> K = graphs.CompleteBipartiteGraph(Integer(3), Integer(3))
>>> G = MatchingCoveredGraph(K)
>>> next(iter(B)).is_isomorphic(G)
True

The nonplanar \(K_{3, 3}\)-free brace Heawood graph is the unique cubic graph of girth six with the fewest number of vertices (that is 14). Note that by \(K_{3, 3}\)-free, it shows that the Heawood graph does not contain a subgraph that is isomophic to a graph obtained by bisubdivision of \(K_{3, 3}\):

Sage

sage: K = graphs.CompleteBipartiteGraph(3, 3)
sage: J = graphs.HeawoodGraph()
sage: H = MatchingCoveredGraph(J)
sage: H.is_brace() and not H.is_planar() and \
....: H.is_regular(k=3) and H.girth() == 6
True

Python

>>> from sage.all import *
>>> K = graphs.CompleteBipartiteGraph(Integer(3), Integer(3))
>>> J = graphs.HeawoodGraph()
>>> H = MatchingCoveredGraph(J)
>>> H.is_brace() and not H.is_planar() and H.is_regular(k=Integer(3)) and H.girth() == Integer(6)
True

Braces of order six or more are 3-connected:

Sage

sage: H = graphs.HexahedralGraph()
sage: G = MatchingCoveredGraph(H)
sage: G.is_brace() and G.is_triconnected()
True

Python

>>> from sage.all import *
>>> H = graphs.HexahedralGraph()
>>> G = MatchingCoveredGraph(H)
>>> G.is_brace() and G.is_triconnected()
True

Braces of order four or more are 2-extendable:

Sage

sage: H = graphs.EllinghamHorton54Graph()
sage: G = MatchingCoveredGraph(H)
sage: G.is_brace()
True
sage: e = next(G.edge_iterator(labels=False)); f = None
sage: for f in G.edge_iterator(labels=False):
....:     if not (set(e) & set(f)):
....:          break
sage: S = [u for x in [e, f] for u in set(x)]
sage: J = H.copy(); J.delete_vertices(S)
sage: M = Graph(J.matching())
sage: M.add_edges([e, f])
sage: if all(d == 1 for d in M.degree()) and \
....:    G.order() == M.order() and \
....:    G.order() == 2*M.size():
....:      print(f'graph {G} is 2-extendable')
graph Ellingham-Horton 54-graph is 2-extendable

Python

>>> from sage.all import *
>>> H = graphs.EllinghamHorton54Graph()
>>> G = MatchingCoveredGraph(H)
>>> G.is_brace()
True
>>> e = next(G.edge_iterator(labels=False)); f = None
>>> for f in G.edge_iterator(labels=False):
...     if not (set(e) & set(f)):
...          break
>>> S = [u for x in [e, f] for u in set(x)]
>>> J = H.copy(); J.delete_vertices(S)
>>> M = Graph(J.matching())
>>> M.add_edges([e, f])
>>> if all(d == Integer(1) for d in M.degree()) and    G.order() == M.order() and    G.order() == Integer(2)*M.size():
...      print(f'graph {G} is 2-extendable')
graph Ellingham-Horton 54-graph is 2-extendable

Every edge in a brace of order at least six is removable:

Sage

sage: H = graphs.CircularLadderGraph(8)
sage: G = MatchingCoveredGraph(H)
sage: # len(G.removble_edges()) == G.size()
# True

Python

>>> from sage.all import *
>>> H = graphs.CircularLadderGraph(Integer(8))
>>> G = MatchingCoveredGraph(H)
>>> # len(G.removble_edges()) == G.size()
# True

Every brace of order eight has the hexahedral graph as a spanning subgraph:

Sage

sage: H = graphs.HexahedralGraph()
sage: L = list(graphs(8,
....:          lambda G: G.size() <= 28 and
....:                    G.is_bipartite())
....: )
sage: L = list(G for G in L if G.is_connected() and
....:                          G.is_matching_covered()
....: )
sage: M = list(MatchingCoveredGraph(G) for G in L)
sage: B = list(G for G in M if G.is_brace())
sage: C = list(G for G in M if Graph(G).subgraph_search(H) is not None)
sage: B == C
True

Python

>>> from sage.all import *
>>> H = graphs.HexahedralGraph()
>>> L = list(graphs(Integer(8),
...          lambda G: G.size() <= Integer(28) and
...                    G.is_bipartite())
... )
>>> L = list(G for G in L if G.is_connected() and
...                          G.is_matching_covered()
... )
>>> M = list(MatchingCoveredGraph(G) for G in L)
>>> B = list(G for G in M if G.is_brace())
>>> C = list(G for G in M if Graph(G).subgraph_search(H) is not None)
>>> B == C
True

For every brace \(G[A, B]\) of order at least six, the graph \(G - a_1 - a_2 - b_1 - b_2\) has a perfect matching for any two distinct vertices \(a_1\) and \(a_2\) in \(A\) and any two distinct vertices \(b_1\) and \(b_2\) in \(B\):

Sage

sage: H =  graphs.CompleteBipartiteGraph(10, 10)
sage: G = MatchingCoveredGraph(H)
sage: G.is_brace()
True
sage: S = [0, 1, 10, 12]
sage: G.delete_vertices(S)
sage: G.has_perfect_matching()
True

Python

>>> from sage.all import *
>>> H =  graphs.CompleteBipartiteGraph(Integer(10), Integer(10))
>>> G = MatchingCoveredGraph(H)
>>> G.is_brace()
True
>>> S = [Integer(0), Integer(1), Integer(10), Integer(12)]
>>> G.delete_vertices(S)
>>> G.has_perfect_matching()
True

For a brace \(G[A, B]\) of order six or more, \(|N(X)| \geq |X| + 2\), for all \(X \subset A\) such that \(0 < |X| <|A| - 1\), where \(N(S) := \{b | (a, b) \in E \^ a \in S\}\) is called the neighboring set of \(S\):

Sage

sage: H = graphs.MoebiusLadderGraph(15)
sage: G = MatchingCoveredGraph(H)
sage: G.is_brace()
True
sage: A, _ = G.bipartite_sets()
sage: # needs random
sage: X = random.sample(list(A), random.randint(1, len(A) - 1))
sage: N = {v for u in X for v in G.neighbor_iterator(u)}
sage: len(N) >= len(X) + 2
True

Python

>>> from sage.all import *
>>> H = graphs.MoebiusLadderGraph(Integer(15))
>>> G = MatchingCoveredGraph(H)
>>> G.is_brace()
True
>>> A, _ = G.bipartite_sets()
>>> # needs random
>>> X = random.sample(list(A), random.randint(Integer(1), len(A) - Integer(1)))
>>> N = {v for u in X for v in G.neighbor_iterator(u)}
>>> len(N) >= len(X) + Integer(2)
True

For a brace \(G\) of order four or more with a perfect matching \(M\), the graph \(G - a - b\) is matching covered for each edge \((a, b)\) in \(M\):

Sage

sage: H = graphs.HeawoodGraph()
sage: G = MatchingCoveredGraph(H)
sage: G.is_brace()
True
sage: M = G.get_matching()
sage: L = []
sage: for a, b, *_ in M:
....:     J = G.copy(); J.delete_vertices([a, b])
....:     if J.is_matching_covered():
....:          L.append(J)
sage: len(L) == len(M)
True

Python

>>> from sage.all import *
>>> H = graphs.HeawoodGraph()
>>> G = MatchingCoveredGraph(H)
>>> G.is_brace()
True
>>> M = G.get_matching()
>>> L = []
>>> for a, b, *_ in M:
...     J = G.copy(); J.delete_vertices([a, b])
...     if J.is_matching_covered():
...          L.append(J)
>>> len(L) == len(M)
True

A cycle graph of order six or more is a bipartite matching covered graph, but is not a brace:

Sage

sage: C = graphs.CycleGraph(10)
sage: G = MatchingCoveredGraph(C)
sage: G.is_brace()
False

Python

>>> from sage.all import *
>>> C = graphs.CycleGraph(Integer(10))
>>> G = MatchingCoveredGraph(C)
>>> G.is_brace()
False

A ladder graph of order six or more is a bipartite matching covered graph, that is not a brace. The tight cut decomposition of a ladder graph produces a list graphs the underlying graph of each of which is isomorphic to a 4-cycle:

Sage

sage: L = graphs.LadderGraph(10)
sage: G = MatchingCoveredGraph(L)
sage: G.is_brace()
False

Python

>>> from sage.all import *
>>> L = graphs.LadderGraph(Integer(10))
>>> G = MatchingCoveredGraph(L)
>>> G.is_brace()
False

One may set the coNP_certificate to be True:

Sage

sage: H = graphs.HexahedralGraph()
sage: G = MatchingCoveredGraph(H)
sage: G.is_brace(coNP_certificate=True)
(True, None, None, None, None)
sage: C = graphs.CycleGraph(6)
sage: D = MatchingCoveredGraph(C)
sage: is_brace, nontrivial_tight_cut, nontrivial_odd_component, \
....: nontrivial_tight_cut_variant, cut_identifier = \
....: D.is_brace(coNP_certificate=True)
sage: is_brace is False
True
sage: J = C.subgraph(vertices=nontrivial_odd_component)
sage: J.is_isomorphic(graphs.PathGraph(3))
True
sage: len(nontrivial_tight_cut) == 2
True
sage: nontrivial_tight_cut_variant
'nontrivial barrier cut'
sage: # Corresponding barrier
sage: cut_identifier == {a for u, v, *_ in nontrivial_tight_cut for a in [u, v] \
....: if a not in nontrivial_odd_component}
True
sage: for u, v, *_ in nontrivial_tight_cut:
....:     assert (u in nontrivial_odd_component and v not in nontrivial_odd_component)
sage: L = graphs.LadderGraph(3) # A ladder graph with two constituent braces
sage: G = MatchingCoveredGraph(L)
sage: is_brace, nontrivial_tight_cut, nontrivial_odd_component, cut_variant, cut_identifier = \
....: G.is_brace(coNP_certificate=True)
sage: is_brace is False
True
sage: G1 = L.copy()
sage: G1.merge_vertices(list(nontrivial_odd_component))
sage: G1.to_simple().is_isomorphic(graphs.CycleGraph(4))
True
sage: G2 = L.copy()
sage: G2.merge_vertices([v for v in G if v not in nontrivial_odd_component])
sage: G2.to_simple().is_isomorphic(graphs.CycleGraph(4))
True
sage: cut_variant
'nontrivial barrier cut'
sage: cut_identifier == {a for u, v, *_ in nontrivial_tight_cut for a in [u, v] \
....: if a not in nontrivial_odd_component}
True
sage: H = graphs.CompleteBipartiteGraph(3, 3)
sage: H.delete_edge(0, 3)
sage: G = MatchingCoveredGraph(H)
sage: G.is_brace(coNP_certificate=True)
(False,
 [(4, 1, None), (5, 1, None), (4, 2, None), (5, 2, None)],
 {0, 4, 5},
 'nontrivial barrier cut',
 {1, 2})

Python

>>> from sage.all import *
>>> H = graphs.HexahedralGraph()
>>> G = MatchingCoveredGraph(H)
>>> G.is_brace(coNP_certificate=True)
(True, None, None, None, None)
>>> C = graphs.CycleGraph(Integer(6))
>>> D = MatchingCoveredGraph(C)
>>> is_brace, nontrivial_tight_cut, nontrivial_odd_component, nontrivial_tight_cut_variant, cut_identifier = D.is_brace(coNP_certificate=True)
>>> is_brace is False
True
>>> J = C.subgraph(vertices=nontrivial_odd_component)
>>> J.is_isomorphic(graphs.PathGraph(Integer(3)))
True
>>> len(nontrivial_tight_cut) == Integer(2)
True
>>> nontrivial_tight_cut_variant
'nontrivial barrier cut'
>>> # Corresponding barrier
>>> cut_identifier == {a for u, v, *_ in nontrivial_tight_cut for a in [u, v] if a not in nontrivial_odd_component}
True
>>> for u, v, *_ in nontrivial_tight_cut:
...     assert (u in nontrivial_odd_component and v not in nontrivial_odd_component)
>>> L = graphs.LadderGraph(Integer(3)) # A ladder graph with two constituent braces
>>> G = MatchingCoveredGraph(L)
>>> is_brace, nontrivial_tight_cut, nontrivial_odd_component, cut_variant, cut_identifier = G.is_brace(coNP_certificate=True)
>>> is_brace is False
True
>>> G1 = L.copy()
>>> G1.merge_vertices(list(nontrivial_odd_component))
>>> G1.to_simple().is_isomorphic(graphs.CycleGraph(Integer(4)))
True
>>> G2 = L.copy()
>>> G2.merge_vertices([v for v in G if v not in nontrivial_odd_component])
>>> G2.to_simple().is_isomorphic(graphs.CycleGraph(Integer(4)))
True
>>> cut_variant
'nontrivial barrier cut'
>>> cut_identifier == {a for u, v, *_ in nontrivial_tight_cut for a in [u, v] if a not in nontrivial_odd_component}
True
>>> H = graphs.CompleteBipartiteGraph(Integer(3), Integer(3))
>>> H.delete_edge(Integer(0), Integer(3))
>>> G = MatchingCoveredGraph(H)
>>> G.is_brace(coNP_certificate=True)
(False,
 [(4, 1, None), (5, 1, None), (4, 2, None), (5, 2, None)],
 {0, 4, 5},
 'nontrivial barrier cut',
 {1, 2})

If the input matching covered graph is nonbipartite, a ValueError is thrown:

Sage

sage: K4 = graphs.CompleteGraph(4)
sage: G = MatchingCoveredGraph(K4)
sage: G.is_brace()
Traceback (most recent call last):
...
ValueError: the input graph is not bipartite
sage: P = graphs.PetersenGraph()
sage: H = MatchingCoveredGraph(P)
sage: H.is_brace(coNP_certificate=True)
Traceback (most recent call last):
...
ValueError: the input graph is not bipartite

Python

>>> from sage.all import *
>>> K4 = graphs.CompleteGraph(Integer(4))
>>> G = MatchingCoveredGraph(K4)
>>> G.is_brace()
Traceback (most recent call last):
...
ValueError: the input graph is not bipartite
>>> P = graphs.PetersenGraph()
>>> H = MatchingCoveredGraph(P)
>>> H.is_brace(coNP_certificate=True)
Traceback (most recent call last):
...
ValueError: the input graph is not bipartite

See also

• is_brick()

• bricks_and_braces()

• number_of_braces()

is_brick(coNP_certificate=False)

Check if the (matching covered) graph is a brick.

A matching covered graph which is free of nontrivial tight cuts is called a brick if it is nonbipartite. A nonbipartite matching covered graph is a brick if and only if it is 3-connected and bicritical [LM2024].

INPUT:

• coNP_certificate – boolean (default: False)

OUTPUT:

• If the input matching covered graph is bipartite, a ValueError is returned.

• If the input nonbipartite matching covered graph is a brick, a boolean True is returned if coNP_certificate is set to False, otherwise a 5-tuple (True, None, None, None, None) is returned.

• If the input nonbipartite matching covered graph is not a brick, a boolean False is returned if coNP_certificate is set to False.

• If coNP_certificate is set to True and the input nonbipartite graph is not a brick, a 5-tuple of

  1. a boolean False,

  2. a list of lists of edges, each list constituting a nontrivial tight cut collectively representing a laminar tight cut,

  3. a list of set of vertices of one of the shores of those respective nontrivial tight cuts:

     1. In case of nontrivial barrier cuts, each of the shores is a nontrivial odd component with respect to a nontrivial barrier, thus the returned list forms mutually exclusive collection of (odd) sets.

     2. Otherwise each of the nontrivial tight cuts is a 2-separation cut, each of the shores form a subset sequence, with the \(i\) th shore being a proper subset of the \(i + 1\) th shore.

  4. a string showing whether the nontrivial tight cuts are barrier cuts (if the string is ‘nontrivial barrier cut’), or 2-separation cuts (if the string is ‘nontrivial 2-separation cut’)

  5. a set of vertices showing the respective barrier if the nontrivial tight cuts are barrier cuts, or otherwise a set of two vertices constituting the corresponding two vertex cut (in this case the nontrivial tight cuts are 2-separation cuts)

  is returned.

EXAMPLES:

The complete graph on four vertices \(K_4\) is the smallest brick:

Sage

sage: K = graphs.CompleteGraph(4)
sage: G = MatchingCoveredGraph(K)
sage: G.is_brick()
True

Python

>>> from sage.all import *
>>> K = graphs.CompleteGraph(Integer(4))
>>> G = MatchingCoveredGraph(K)
>>> G.is_brick()
True

The triangular cicular ladder (a graph on six vertices), aka \(\overline{C_6}\) is a brick:

Sage

sage: C6Bar = graphs.CircularLadderGraph(3)
sage: G = MatchingCoveredGraph(C6Bar)
sage: G.is_brick()
True

Python

>>> from sage.all import *
>>> C6Bar = graphs.CircularLadderGraph(Integer(3))
>>> G = MatchingCoveredGraph(C6Bar)
>>> G.is_brick()
True

Each of Petersen graph, Bicorn graph, Tricorn graph, Cubeplex graph, Twinplex graph, Wagner graph is a brick:

Sage

sage: MatchingCoveredGraph(graphs.PetersenGraph()).is_brick() and \
....: MatchingCoveredGraph(graphs.StaircaseGraph(4)).is_brick() and \
....: MatchingCoveredGraph(graphs.TricornGraph()).is_brick() and \
....: MatchingCoveredGraph(graphs.CubeplexGraph()).is_brick() and \
....: MatchingCoveredGraph(graphs.TwinplexGraph()).is_brick() and \
....: MatchingCoveredGraph(graphs.WagnerGraph()).is_brick()
True

Python

>>> from sage.all import *
>>> MatchingCoveredGraph(graphs.PetersenGraph()).is_brick() and MatchingCoveredGraph(graphs.StaircaseGraph(Integer(4))).is_brick() and MatchingCoveredGraph(graphs.TricornGraph()).is_brick() and MatchingCoveredGraph(graphs.CubeplexGraph()).is_brick() and MatchingCoveredGraph(graphs.TwinplexGraph()).is_brick() and MatchingCoveredGraph(graphs.WagnerGraph()).is_brick()
True

The Murty graph is the smallest simple brick that is not odd-intercyclic:

Sage

sage: M = graphs.MurtyGraph()
sage: G = MatchingCoveredGraph(M)
sage: G.is_brick()
True

Python

>>> from sage.all import *
>>> M = graphs.MurtyGraph()
>>> G = MatchingCoveredGraph(M)
>>> G.is_brick()
True

A circular ladder graph of order six or more on \(2n\) vertices for an odd \(n\) is a brick:

Sage

sage: n = 11
sage: CL = graphs.CircularLadderGraph(n)
sage: G = MatchingCoveredGraph(CL)
sage: G.is_brick()
True

Python

>>> from sage.all import *
>>> n = Integer(11)
>>> CL = graphs.CircularLadderGraph(n)
>>> G = MatchingCoveredGraph(CL)
>>> G.is_brick()
True

A moebius ladder graph of order eight or more on \(2n\) vertices for an even \(n\) is a brick:

Sage

sage: n = 10
sage: ML = graphs.MoebiusLadderGraph(n)
sage: G = MatchingCoveredGraph(ML)
sage: G.is_brick()
True

Python

>>> from sage.all import *
>>> n = Integer(10)
>>> ML = graphs.MoebiusLadderGraph(n)
>>> G = MatchingCoveredGraph(ML)
>>> G.is_brick()
True

A wheel graph of an even order is a brick:

Sage

sage: W = graphs.WheelGraph(10)
sage: G = MatchingCoveredGraph(W)
sage: G.is_brick()
True

Python

>>> from sage.all import *
>>> W = graphs.WheelGraph(Integer(10))
>>> G = MatchingCoveredGraph(W)
>>> G.is_brick()
True

A graph that is isomorphic to a truncated biwheel graph is a brick:

Sage

sage: TB = graphs.TruncatedBiwheelGraph(15)
sage: G = MatchingCoveredGraph(TB)
sage: G.is_brick()
True

Python

>>> from sage.all import *
>>> TB = graphs.TruncatedBiwheelGraph(Integer(15))
>>> G = MatchingCoveredGraph(TB)
>>> G.is_brick()
True

Each of the graphs in the staircase graph family with order eight or more is a brick:

Sage

sage: ST = graphs.StaircaseGraph(9)
sage: G = MatchingCoveredGraph(ST)
sage: G.is_brick()
True

Python

>>> from sage.all import *
>>> ST = graphs.StaircaseGraph(Integer(9))
>>> G = MatchingCoveredGraph(ST)
>>> G.is_brick()
True

Bricks are 3-connected:

Sage

sage: P = graphs.PetersenGraph()
sage: G = MatchingCoveredGraph(P)
sage: G.is_brick()
True
sage: G.is_triconnected()
True

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> G = MatchingCoveredGraph(P)
>>> G.is_brick()
True
>>> G.is_triconnected()
True

Bricks are bicritical:

Sage

sage: P = graphs.PetersenGraph()
sage: G = MatchingCoveredGraph(P)
sage: G.is_brick()
True
sage: G.is_bicritical()
True

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> G = MatchingCoveredGraph(P)
>>> G.is_brick()
True
>>> G.is_bicritical()
True

Examples of nonbipartite matching covered graphs that are not bricks:

Sage

sage: H = Graph([
....:     (0, 3), (0, 4), (0, 7),
....:     (1, 3), (1, 5), (1, 7),
....:     (2, 3), (2, 6), (2, 7),
....:     (4, 5), (4, 6), (5, 6)
....: ])
sage: G = MatchingCoveredGraph(H)
sage: G.is_bipartite()
False
sage: G.is_bicritical()
False
sage: G.is_triconnected()
True
sage: G.is_brick()
False
sage: H = Graph([
....:     (0, 1), (0, 2), (0, 3), (0, 4), (1, 2),
....:     (1, 5), (2, 5), (3, 4), (3, 5), (4, 5)
....: ])
sage: G = MatchingCoveredGraph(H)
sage: G.is_bipartite()
False
sage: G.is_bicritical()
True
sage: G.is_triconnected()
False
sage: G.is_brick()
False

Python

>>> from sage.all import *
>>> H = Graph([
...     (Integer(0), Integer(3)), (Integer(0), Integer(4)), (Integer(0), Integer(7)),
...     (Integer(1), Integer(3)), (Integer(1), Integer(5)), (Integer(1), Integer(7)),
...     (Integer(2), Integer(3)), (Integer(2), Integer(6)), (Integer(2), Integer(7)),
...     (Integer(4), Integer(5)), (Integer(4), Integer(6)), (Integer(5), Integer(6))
... ])
>>> G = MatchingCoveredGraph(H)
>>> G.is_bipartite()
False
>>> G.is_bicritical()
False
>>> G.is_triconnected()
True
>>> G.is_brick()
False
>>> H = Graph([
...     (Integer(0), Integer(1)), (Integer(0), Integer(2)), (Integer(0), Integer(3)), (Integer(0), Integer(4)), (Integer(1), Integer(2)),
...     (Integer(1), Integer(5)), (Integer(2), Integer(5)), (Integer(3), Integer(4)), (Integer(3), Integer(5)), (Integer(4), Integer(5))
... ])
>>> G = MatchingCoveredGraph(H)
>>> G.is_bipartite()
False
>>> G.is_bicritical()
True
>>> G.is_triconnected()
False
>>> G.is_brick()
False

One may set the coNP_certificate to be True:

Sage

sage: K4 = graphs.CompleteGraph(4)
sage: G = MatchingCoveredGraph(K4)
sage: G.is_brick(coNP_certificate=True)
(True, None, None, None, None)
sage: # K(4) ⊙ K(3, 3) is nonbipartite but not a brick
sage: H = graphs.MurtyGraph(); H.delete_edge(0, 1)
sage: G = MatchingCoveredGraph(H)
sage: G.is_brick(coNP_certificate=True)
(False, [[(5, 2, None), (6, 3, None), (7, 4, None)]], [{5, 6, 7}],
 'nontrivial barrier cut', {2, 3, 4})
sage: H = Graph([
....:     (0, 12), (0, 13), (0, 15), (1, 4), (1, 13), (1, 14),
....:     (1, 19), (2, 4), (2, 13), (2, 14), (2, 17), (3, 9),
....:     (3, 13), (3, 16), (3, 21), (4, 6), (4, 7), (5, 7),
....:     (5, 8), (5, 12), (6, 8), (6, 11), (7, 10), (8, 9),
....:     (9, 10), (10, 11), (11, 12), (14, 15), (14, 16), (15, 16),
....:     (17, 18), (17, 21), (18, 19), (18, 20), (19, 20), (20, 21)
....: ])
sage: G = MatchingCoveredGraph(H)
sage: G.is_brick(coNP_certificate=True)
(False,
 [[(12, 0, None), (4, 1, None), (4, 2, None), (9, 3, None)],
  [(19, 1, None), (17, 2, None), (21, 3, None)],
  [(15, 0, None), (14, 1, None), (14, 2, None), (16, 3, None)]],
 [{4, 5, 6, 7, 8, 9, 10, 11, 12}, {17, 18, 19, 20, 21}, {14, 15, 16}],
 'nontrivial barrier cut', {0, 1, 2, 3})
sage: J = Graph([
....:     (0, 1), (0, 2), (0, 3), (0, 4), (0, 5),
....:     (0, 6), (0, 7), (0, 8), (0, 9), (0, 10),
....:     (1, 2), (1, 11), (2, 11), (3, 4), (3, 11),
....:     (4, 11), (5, 6), (5, 11), (6, 11), (7, 8),
....:     (7, 11), (8, 11), (9, 10), (9, 11), (10, 11)
....: ])
sage: G = MatchingCoveredGraph(J)
sage: G.is_brick(coNP_certificate=True)
(False,
 [[(0, 3, None),
   (0, 4, None),
   (0, 5, None),
   (0, 6, None),
   (0, 7, None),
   (0, 8, None),
   (0, 9, None),
   (0, 10, None),
   (1, 11, None),
   (2, 11, None)],
  [(0, 5, None),
   (0, 6, None),
   (0, 7, None),
   (0, 8, None),
   (0, 9, None),
   (0, 10, None),
   (1, 11, None),
   (2, 11, None),
   (3, 11, None),
   (4, 11, None)],
  [(0, 7, None),
   (0, 8, None),
   (0, 9, None),
   (0, 10, None),
   (1, 11, None),
   (2, 11, None),
   (3, 11, None),
   (4, 11, None),
   (5, 11, None),
   (6, 11, None)],
  [(0, 9, None),
   (0, 10, None),
   (1, 11, None),
   (2, 11, None),
   (3, 11, None),
   (4, 11, None),
   (5, 11, None),
   (6, 11, None),
   (7, 11, None),
   (8, 11, None)]],
 [{0, 1, 2},
  {0, 1, 2, 3, 4},
  {0, 1, 2, 3, 4, 5, 6},
  {0, 1, 2, 3, 4, 5, 6, 7, 8}],
 'nontrivial 2-separation cut',
 {0, 11})

Python

>>> from sage.all import *
>>> K4 = graphs.CompleteGraph(Integer(4))
>>> G = MatchingCoveredGraph(K4)
>>> G.is_brick(coNP_certificate=True)
(True, None, None, None, None)
>>> # K(4) ⊙ K(3, 3) is nonbipartite but not a brick
>>> H = graphs.MurtyGraph(); H.delete_edge(Integer(0), Integer(1))
>>> G = MatchingCoveredGraph(H)
>>> G.is_brick(coNP_certificate=True)
(False, [[(5, 2, None), (6, 3, None), (7, 4, None)]], [{5, 6, 7}],
 'nontrivial barrier cut', {2, 3, 4})
>>> H = Graph([
...     (Integer(0), Integer(12)), (Integer(0), Integer(13)), (Integer(0), Integer(15)), (Integer(1), Integer(4)), (Integer(1), Integer(13)), (Integer(1), Integer(14)),
...     (Integer(1), Integer(19)), (Integer(2), Integer(4)), (Integer(2), Integer(13)), (Integer(2), Integer(14)), (Integer(2), Integer(17)), (Integer(3), Integer(9)),
...     (Integer(3), Integer(13)), (Integer(3), Integer(16)), (Integer(3), Integer(21)), (Integer(4), Integer(6)), (Integer(4), Integer(7)), (Integer(5), Integer(7)),
...     (Integer(5), Integer(8)), (Integer(5), Integer(12)), (Integer(6), Integer(8)), (Integer(6), Integer(11)), (Integer(7), Integer(10)), (Integer(8), Integer(9)),
...     (Integer(9), Integer(10)), (Integer(10), Integer(11)), (Integer(11), Integer(12)), (Integer(14), Integer(15)), (Integer(14), Integer(16)), (Integer(15), Integer(16)),
...     (Integer(17), Integer(18)), (Integer(17), Integer(21)), (Integer(18), Integer(19)), (Integer(18), Integer(20)), (Integer(19), Integer(20)), (Integer(20), Integer(21))
... ])
>>> G = MatchingCoveredGraph(H)
>>> G.is_brick(coNP_certificate=True)
(False,
 [[(12, 0, None), (4, 1, None), (4, 2, None), (9, 3, None)],
  [(19, 1, None), (17, 2, None), (21, 3, None)],
  [(15, 0, None), (14, 1, None), (14, 2, None), (16, 3, None)]],
 [{4, 5, 6, 7, 8, 9, 10, 11, 12}, {17, 18, 19, 20, 21}, {14, 15, 16}],
 'nontrivial barrier cut', {0, 1, 2, 3})
>>> J = Graph([
...     (Integer(0), Integer(1)), (Integer(0), Integer(2)), (Integer(0), Integer(3)), (Integer(0), Integer(4)), (Integer(0), Integer(5)),
...     (Integer(0), Integer(6)), (Integer(0), Integer(7)), (Integer(0), Integer(8)), (Integer(0), Integer(9)), (Integer(0), Integer(10)),
...     (Integer(1), Integer(2)), (Integer(1), Integer(11)), (Integer(2), Integer(11)), (Integer(3), Integer(4)), (Integer(3), Integer(11)),
...     (Integer(4), Integer(11)), (Integer(5), Integer(6)), (Integer(5), Integer(11)), (Integer(6), Integer(11)), (Integer(7), Integer(8)),
...     (Integer(7), Integer(11)), (Integer(8), Integer(11)), (Integer(9), Integer(10)), (Integer(9), Integer(11)), (Integer(10), Integer(11))
... ])
>>> G = MatchingCoveredGraph(J)
>>> G.is_brick(coNP_certificate=True)
(False,
 [[(0, 3, None),
   (0, 4, None),
   (0, 5, None),
   (0, 6, None),
   (0, 7, None),
   (0, 8, None),
   (0, 9, None),
   (0, 10, None),
   (1, 11, None),
   (2, 11, None)],
  [(0, 5, None),
   (0, 6, None),
   (0, 7, None),
   (0, 8, None),
   (0, 9, None),
   (0, 10, None),
   (1, 11, None),
   (2, 11, None),
   (3, 11, None),
   (4, 11, None)],
  [(0, 7, None),
   (0, 8, None),
   (0, 9, None),
   (0, 10, None),
   (1, 11, None),
   (2, 11, None),
   (3, 11, None),
   (4, 11, None),
   (5, 11, None),
   (6, 11, None)],
  [(0, 9, None),
   (0, 10, None),
   (1, 11, None),
   (2, 11, None),
   (3, 11, None),
   (4, 11, None),
   (5, 11, None),
   (6, 11, None),
   (7, 11, None),
   (8, 11, None)]],
 [{0, 1, 2},
  {0, 1, 2, 3, 4},
  {0, 1, 2, 3, 4, 5, 6},
  {0, 1, 2, 3, 4, 5, 6, 7, 8}],
 'nontrivial 2-separation cut',
 {0, 11})

If the input matching covered graph is bipartite, a ValueError is thrown:

Sage

sage: H = graphs.HexahedralGraph()
sage: G = MatchingCoveredGraph(H)
sage: G.is_brick()
Traceback (most recent call last):
...
ValueError: the input graph is bipartite
sage: J = graphs.HeawoodGraph()
sage: G = MatchingCoveredGraph(J)
sage: G.is_brick(coNP_certificate=True)
Traceback (most recent call last):
...
ValueError: the input graph is bipartite

Python

>>> from sage.all import *
>>> H = graphs.HexahedralGraph()
>>> G = MatchingCoveredGraph(H)
>>> G.is_brick()
Traceback (most recent call last):
...
ValueError: the input graph is bipartite
>>> J = graphs.HeawoodGraph()
>>> G = MatchingCoveredGraph(J)
>>> G.is_brick(coNP_certificate=True)
Traceback (most recent call last):
...
ValueError: the input graph is bipartite

See also

• is_bicritical()

• is_brace()

• bricks_and_braces()

• number_of_bricks()

• number_of_petersen_bricks()

loop_edges(labels=True)

Return a list of all loops in the (matching covered) graph.

Note

This method overwrites the loop_edges() method in order to return an empty list as matching covered graphs are free of looped edges.

INPUT:

• labels – boolean (default: True); whether returned edges have labels ((u,v,l)) or not ((u,v)).

OUTPUT:

• A list capturing the edges that are loops in the matching covered graph; note that, the list is empty since matching covered graphs do not contain any looped edges.

EXAMPLES:

A matching covered graph, for instance the Heawood graph, by definition, is always free of loops:

Sage

sage: H = graphs.HeawoodGraph()
sage: G = MatchingCoveredGraph(H)
sage: G
Matching covered heawood graph: graph on 14 vertices
sage: G.add_edge(0, 0)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
sage: G.loops()
[]
sage: G.loop_edges()
[]

Python

>>> from sage.all import *
>>> H = graphs.HeawoodGraph()
>>> G = MatchingCoveredGraph(H)
>>> G
Matching covered heawood graph: graph on 14 vertices
>>> G.add_edge(Integer(0), Integer(0))
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
>>> G.loops()
[]
>>> G.loop_edges()
[]

A matching covered graph may support multiple edges, still no loops are allowed:

Sage

sage: C = graphs.CycleGraph(4)
sage: G = MatchingCoveredGraph(C)
sage: G.allow_multiple_edges(True)
sage: G
Matching covered cycle graph: multi-graph on 4 vertices
sage: G.add_edge(0, 1, 'label')
sage: G.add_edge(0, 0)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
sage: G.edges(sort=False)
[(0, 1, None), (0, 1, 'label'), (0, 3, None), (1, 2, None), (2, 3, None)]
sage: G.loops()
[]
sage: G.loop_edges()
[]

Python

>>> from sage.all import *
>>> C = graphs.CycleGraph(Integer(4))
>>> G = MatchingCoveredGraph(C)
>>> G.allow_multiple_edges(True)
>>> G
Matching covered cycle graph: multi-graph on 4 vertices
>>> G.add_edge(Integer(0), Integer(1), 'label')
>>> G.add_edge(Integer(0), Integer(0))
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
>>> G.edges(sort=False)
[(0, 1, None), (0, 1, 'label'), (0, 3, None), (1, 2, None), (2, 3, None)]
>>> G.loops()
[]
>>> G.loop_edges()
[]

One may set the label to either True or False:

Sage

sage: G.loop_edges(labels=False)
[]
sage: G.loops(labels=True)
[]

Python

>>> from sage.all import *
>>> G.loop_edges(labels=False)
[]
>>> G.loops(labels=True)
[]

See also

• allow_loops()

• allows_loops()

• has_loops()

• loop_vertices()

• loops()

• number_of_loops()

• remove_loops()

loop_vertices()

Return a list of vertices with loops.

Note

This method overwrites the loop_vertices() method in order to return an empty list as matching covered graphs are free of vertices that have looped edges.

OUTPUT:

• A list capturing the vertices that have loops in the matching covered graph; note that, the list is empty since matching covered graphs do not contain any looped edges.

EXAMPLES:

A matching covered graph, for instance the Möbius graph of order 8, by definition, is always free of loops:

Sage

sage: M = graphs.MoebiusLadderGraph(4)
sage: G = MatchingCoveredGraph(M)
sage: G
Matching covered moebius ladder graph: graph on 8 vertices
sage: G.add_edge(0, 0)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
sage: G.loop_vertices()
[]

Python

>>> from sage.all import *
>>> M = graphs.MoebiusLadderGraph(Integer(4))
>>> G = MatchingCoveredGraph(M)
>>> G
Matching covered moebius ladder graph: graph on 8 vertices
>>> G.add_edge(Integer(0), Integer(0))
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
>>> G.loop_vertices()
[]

A matching covered graph may support multiple edges, still no loops are allowed:

Sage

sage: S = graphs.StaircaseGraph(4)
sage: G = MatchingCoveredGraph(S)
sage: G.allow_multiple_edges(True)
sage: G
Matching covered staircase graph: multi-graph on 8 vertices
sage: G.add_edge(0, 1, 'label')
sage: G.add_edge(0, 0)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
sage: G.edges(sort=False)
[(0, 1, None), (0, 1, 'label'), (0, 3, None), (0, 6, None),
 (1, 2, None), (1, 4, None), (2, 5, None), (2, 7, None),
 (3, 4, None), (3, 6, None), (4, 5, None), (5, 7, None),
 (6, 7, None)]
sage: G.loop_vertices()
[]

Python

>>> from sage.all import *
>>> S = graphs.StaircaseGraph(Integer(4))
>>> G = MatchingCoveredGraph(S)
>>> G.allow_multiple_edges(True)
>>> G
Matching covered staircase graph: multi-graph on 8 vertices
>>> G.add_edge(Integer(0), Integer(1), 'label')
>>> G.add_edge(Integer(0), Integer(0))
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
>>> G.edges(sort=False)
[(0, 1, None), (0, 1, 'label'), (0, 3, None), (0, 6, None),
 (1, 2, None), (1, 4, None), (2, 5, None), (2, 7, None),
 (3, 4, None), (3, 6, None), (4, 5, None), (5, 7, None),
 (6, 7, None)]
>>> G.loop_vertices()
[]

See also

• allow_loops()

• allows_loops()

• has_loops()

• loop_edges()

• loops()

• number_of_loops()

• remove_loops()

loops(labels=True)

Return a list of all loops in the (matching covered) graph.

Note

This method overwrites the loop_edges() method in order to return an empty list as matching covered graphs are free of looped edges.

INPUT:

• labels – boolean (default: True); whether returned edges have labels ((u,v,l)) or not ((u,v)).

OUTPUT:

• A list capturing the edges that are loops in the matching covered graph; note that, the list is empty since matching covered graphs do not contain any looped edges.

EXAMPLES:

A matching covered graph, for instance the Heawood graph, by definition, is always free of loops:

Sage

sage: H = graphs.HeawoodGraph()
sage: G = MatchingCoveredGraph(H)
sage: G
Matching covered heawood graph: graph on 14 vertices
sage: G.add_edge(0, 0)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
sage: G.loops()
[]
sage: G.loop_edges()
[]

Python

>>> from sage.all import *
>>> H = graphs.HeawoodGraph()
>>> G = MatchingCoveredGraph(H)
>>> G
Matching covered heawood graph: graph on 14 vertices
>>> G.add_edge(Integer(0), Integer(0))
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
>>> G.loops()
[]
>>> G.loop_edges()
[]

A matching covered graph may support multiple edges, still no loops are allowed:

Sage

sage: C = graphs.CycleGraph(4)
sage: G = MatchingCoveredGraph(C)
sage: G.allow_multiple_edges(True)
sage: G
Matching covered cycle graph: multi-graph on 4 vertices
sage: G.add_edge(0, 1, 'label')
sage: G.add_edge(0, 0)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
sage: G.edges(sort=False)
[(0, 1, None), (0, 1, 'label'), (0, 3, None), (1, 2, None), (2, 3, None)]
sage: G.loops()
[]
sage: G.loop_edges()
[]

Python

>>> from sage.all import *
>>> C = graphs.CycleGraph(Integer(4))
>>> G = MatchingCoveredGraph(C)
>>> G.allow_multiple_edges(True)
>>> G
Matching covered cycle graph: multi-graph on 4 vertices
>>> G.add_edge(Integer(0), Integer(1), 'label')
>>> G.add_edge(Integer(0), Integer(0))
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
>>> G.edges(sort=False)
[(0, 1, None), (0, 1, 'label'), (0, 3, None), (1, 2, None), (2, 3, None)]
>>> G.loops()
[]
>>> G.loop_edges()
[]

One may set the label to either True or False:

Sage

sage: G.loop_edges(labels=False)
[]
sage: G.loops(labels=True)
[]

Python

>>> from sage.all import *
>>> G.loop_edges(labels=False)
[]
>>> G.loops(labels=True)
[]

See also

• allow_loops()

• allows_loops()

• has_loops()

• loop_vertices()

• loops()

• number_of_loops()

• remove_loops()

maximal_barrier(vertex)

Return the (unique) maximal barrier containing the vertex.

For a matching covered graph \(G\), a subset \(B\) of the vertex set \(V\) is a barrier if \(|B| = o(G - B)\), where \(|B|\) denotes the cardinality of the set \(B\) and \(o(G - B)\) denotes the number of odd components in the graph \(G - B\). And a barrier \(B\) is a maximal barrier if \(C\) is not a barrier for each \(C\) such that \(B \subset C \subseteq V\).

In a matching covered graph, each vertex belongs to a unique maximal barrier, which is a consequence of the following theorem.

Theorem [LM2024]:

Let \(u\) and \(v\) be any two vertices in a matchable graph \(G\). Then the graph \(G - u - v\) is matchable if and only if there is no barrier of \(G\) which contains both \(u\) and \(v\).

And in order to find the vertices that do not lie in the maximal barrier containing the provided vertex in linear time we take inspiration of the \(M\) alternating tree seach method [LR2004].

INPUT:

• vertex – a vertex of the graph

OUTPUT:

• A ValueError is returned if vertex is not a vertex of the graph, otherwise a set of vertices that constitute the (unique) maximal barrier containing the vertex is returned.

EXAMPLES:

The graph \(K_4 \odot K_{3, 3}\) is matching covered. Show the set of vertices in the (unique) maximal barrier containing the vertex \(2\):

Sage

sage: G = Graph([
....:    (0, 2), (0, 3), (0, 4), (1, 2),
....:    (1, 3), (1, 4), (2, 5), (3, 6),
....:    (4, 7), (5, 6), (5, 7), (6, 7)
....: ])
sage: H = MatchingCoveredGraph(G)
sage: B = H.maximal_barrier(2)
sage: B
{2, 3, 4}

Python

>>> from sage.all import *
>>> G = Graph([
...    (Integer(0), Integer(2)), (Integer(0), Integer(3)), (Integer(0), Integer(4)), (Integer(1), Integer(2)),
...    (Integer(1), Integer(3)), (Integer(1), Integer(4)), (Integer(2), Integer(5)), (Integer(3), Integer(6)),
...    (Integer(4), Integer(7)), (Integer(5), Integer(6)), (Integer(5), Integer(7)), (Integer(6), Integer(7))
... ])
>>> H = MatchingCoveredGraph(G)
>>> B = H.maximal_barrier(Integer(2))
>>> B
{2, 3, 4}

Let \(B\) be a maximal barrier of a matching covered graph \(G\) (which is, of course, a matchable graph). The graph, \(J := G - B\) has no even component:

Sage

sage: J = G.copy()
sage: J.delete_vertices(B)
sage: all(len(K)%2 != 0 for K in J.connected_components(sort=True))
True

Python

>>> from sage.all import *
>>> J = G.copy()
>>> J.delete_vertices(B)
>>> all(len(K)%Integer(2) != Integer(0) for K in J.connected_components(sort=True))
True

Let \(B\) be a maximal barrier in a matching covered graph \(G\) and let \(M\) be a perfect matching of \(G\). If \(K\) is an odd component of \(J := G - B\), then \(M \cap \partial_G(K)\) has precisely one edge and if \(v\) is the end of that edge in \(V(K)\), then \(M \cap E(K)\) is a perfect matching of \(K - v\):

Sage

sage: K = J.subgraph(vertices=(J.connected_components(sort=True))[0])
sage: # Let F := \partial_G(K) and T := M \cap F
sage: F = [edge for edge in G.edge_iterator()
....:      if (edge[0] in K and edge[1] not in K)
....:      or (edge[0] not in K and edge[1] in K)
....: ]
sage: M = H.get_matching()
sage: T = [edge for edge in F if edge in M]
sage: len(T) == 1
True
sage: v = T[0][0] if T[0][0] in K else T[0][1]
sage: # Let N := M \cap E(K) and L := K - v
sage: N = Graph([edge for edge in K.edge_iterator() if edge in M])
sage: L = K.copy()
sage: L.delete_vertex(v)
sage: # Check if N is a perfect matching of L
sage: L.order() == 2*N.size()
True

Python

>>> from sage.all import *
>>> K = J.subgraph(vertices=(J.connected_components(sort=True))[Integer(0)])
>>> # Let F := \partial_G(K) and T := M \cap F
>>> F = [edge for edge in G.edge_iterator()
...      if (edge[Integer(0)] in K and edge[Integer(1)] not in K)
...      or (edge[Integer(0)] not in K and edge[Integer(1)] in K)
... ]
>>> M = H.get_matching()
>>> T = [edge for edge in F if edge in M]
>>> len(T) == Integer(1)
True
>>> v = T[Integer(0)][Integer(0)] if T[Integer(0)][Integer(0)] in K else T[Integer(0)][Integer(1)]
>>> # Let N := M \cap E(K) and L := K - v
>>> N = Graph([edge for edge in K.edge_iterator() if edge in M])
>>> L = K.copy()
>>> L.delete_vertex(v)
>>> # Check if N is a perfect matching of L
>>> L.order() == Integer(2)*N.size()
True

Let \(B\) be a maximal barrier of a matching covered graph \(G\) (which is, of course, a matchable graph). The graph induced by each component of \(G - B\) is factor critical:

Sage

sage: all((K.subgraph(vertices=connected_component)).is_factor_critical()
....:     for connected_component in K.connected_components(sort=True)
....: )
True

Python

>>> from sage.all import *
>>> all((K.subgraph(vertices=connected_component)).is_factor_critical()
...     for connected_component in K.connected_components(sort=True)
... )
True

For a bicritical graph (for instance, the Petersen graph), for each vertex the maximal barrier is a singleton set containing only that vertex:

Sage

sage: P = graphs.PetersenGraph()
sage: G = MatchingCoveredGraph(P)
sage: u = 0
sage: set([u]) == G.maximal_barrier(u)
True

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> G = MatchingCoveredGraph(P)
>>> u = Integer(0)
>>> set([u]) == G.maximal_barrier(u)
True

In a bipartite matching covered graph (for instance, the Hexahedral graph), for a vertex, the maximal barrier is the set of vertices of the color class that the particular vertex belongs to. In other words, there are precisely two maximal barriers in a bipartite matching covered graph, that is, the vertex sets of the individual color class:

Sage

sage: G = graphs.HexahedralGraph()
sage: H = MatchingCoveredGraph(G)
sage: A, _ = H.bipartite_sets()
sage: # needs random
sage: import random
sage: a = random.choice(list(A))
sage: A == H.maximal_barrier(a)
True

Python

>>> from sage.all import *
>>> G = graphs.HexahedralGraph()
>>> H = MatchingCoveredGraph(G)
>>> A, _ = H.bipartite_sets()
>>> # needs random
>>> import random
>>> a = random.choice(list(A))
>>> A == H.maximal_barrier(a)
True

Maximal barriers of matching covered graph constitute a partition of its vertex set:

Sage

sage: S = set()
sage: for v in H:
....:     B = tuple(sorted(list(H.maximal_barrier(v))))
....:     S.add(B)
sage: S = list(S)
sage: # Check that S is a partition of the vertex set of H
sage: # Part 1: Check if S spans the vertex set of H
sage: sorted([u for B in S for u in B]) == sorted(list(H))
True
sage: # Part 2: Check if each maximal barrier in S is disjoint
sage: is_disjoint = True
sage: for i in range(len(S)):
....:     for j in range(i+1, len(S)):
....:         c = [v for v in S[i] if v in S[j]]
....:         is_disjoint = (len(c) == 0)
sage: is_disjoint
True

Python

>>> from sage.all import *
>>> S = set()
>>> for v in H:
...     B = tuple(sorted(list(H.maximal_barrier(v))))
...     S.add(B)
>>> S = list(S)
>>> # Check that S is a partition of the vertex set of H
>>> # Part 1: Check if S spans the vertex set of H
>>> sorted([u for B in S for u in B]) == sorted(list(H))
True
>>> # Part 2: Check if each maximal barrier in S is disjoint
>>> is_disjoint = True
>>> for i in range(len(S)):
...     for j in range(i+Integer(1), len(S)):
...         c = [v for v in S[i] if v in S[j]]
...         is_disjoint = (len(c) == Integer(0))
>>> is_disjoint
True

REFERENCES:

• [LZ2004]

• [LM2024]

See also

• is_bicritical()

• is_matching_covered()

• canonical_partition()

number_of_loops()

Return the number of edges that are loops.

Note

This method overwrites the number_of_loops() method in order to return 0 as matching covered graphs are free of looped edges.

OUTPUT:

• An integer, 0 is returned, since matching covered graphs do not contain zero loops.

EXAMPLES:

A matching covered graph, for instance the Truncated biwheel graph, by definition, is always free of loops:

Sage

sage: T = graphs.TruncatedBiwheelGraph(5)
sage: G = MatchingCoveredGraph(T)
sage: G
Matching covered truncated biwheel graph: graph on 10 vertices
sage: G.add_edge(0, 0)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
sage: G.loop_vertices()
[]
sage: G.number_of_loops()
0

Python

>>> from sage.all import *
>>> T = graphs.TruncatedBiwheelGraph(Integer(5))
>>> G = MatchingCoveredGraph(T)
>>> G
Matching covered truncated biwheel graph: graph on 10 vertices
>>> G.add_edge(Integer(0), Integer(0))
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
>>> G.loop_vertices()
[]
>>> G.number_of_loops()
0

A matching covered graph may support multiple edges, still no loops are allowed:

Sage

sage: B = graphs.BiwheelGraph(4)
sage: G = MatchingCoveredGraph(B)
sage: G.allow_multiple_edges(True)
sage: G
Matching covered biwheel graph: multi-graph on 8 vertices
sage: G.add_edge(0, 1, 'label')
sage: G.add_edge(0, 0)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
sage: G.edges(sort=False)
[(0, 1, None), (0, 1, 'label'), (0, 5, None), (0, 7, None),
 (1, 2, None), (1, 6, None), (2, 3, None), (2, 7, None),
 (3, 4, None), (3, 6, None), (4, 5, None), (4, 7, None),
 (5, 6, None)]
sage: G.loop_vertices()
[]
sage: G.number_of_loops()
0

Python

>>> from sage.all import *
>>> B = graphs.BiwheelGraph(Integer(4))
>>> G = MatchingCoveredGraph(B)
>>> G.allow_multiple_edges(True)
>>> G
Matching covered biwheel graph: multi-graph on 8 vertices
>>> G.add_edge(Integer(0), Integer(1), 'label')
>>> G.add_edge(Integer(0), Integer(0))
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
>>> G.edges(sort=False)
[(0, 1, None), (0, 1, 'label'), (0, 5, None), (0, 7, None),
 (1, 2, None), (1, 6, None), (2, 3, None), (2, 7, None),
 (3, 4, None), (3, 6, None), (4, 5, None), (4, 7, None),
 (5, 6, None)]
>>> G.loop_vertices()
[]
>>> G.number_of_loops()
0

See also

• allow_loops()

• allows_loops()

• has_loops()

• loop_edges()

• loop_vertices()

• loops()

• remove_loops()

remove_loops(vertices=None)

Remove loops on vertices in vertices.

Note

This method overwrites the remove_loops() method in order to return without any alteration as matching covered graphs are free of looped edges.

INPUT:

• vertices – (default: None) iterator container of vertex labels corresponding to which the looped edges are to be removed. If vertices is None, remove all loops.

OUTPUT:

• Nothing is returned, as a matching covered graph is already devoid of any loops.

EXAMPLES:

A matching covered graph, for instance the Wheel graph of order six, is always free of loops:

Sage

sage: W = graphs.WheelGraph(6)
sage: G = MatchingCoveredGraph(W)
sage: G
Matching covered wheel graph: graph on 6 vertices
sage: G.add_edge(0, 0)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
sage: G.remove_loops()
sage: G.edges(sort=True)
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 5, None), (2, 3, None),
 (3, 4, None), (4, 5, None)]

Python

>>> from sage.all import *
>>> W = graphs.WheelGraph(Integer(6))
>>> G = MatchingCoveredGraph(W)
>>> G
Matching covered wheel graph: graph on 6 vertices
>>> G.add_edge(Integer(0), Integer(0))
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
>>> G.remove_loops()
>>> G.edges(sort=True)
[(0, 1, None), (0, 2, None), (0, 3, None), (0, 4, None),
 (0, 5, None), (1, 2, None), (1, 5, None), (2, 3, None),
 (3, 4, None), (4, 5, None)]

A matching covered graph may support multiple edges, still no loops are allowed:

Sage

sage: K = graphs.CompleteGraph(2)
sage: G = MatchingCoveredGraph(K)
sage: G.allow_multiple_edges(True)
sage: G
Matching covered complete graph: multi-graph on 2 vertices
sage: G.add_edge(0, 1, 'label')
sage: G.add_edge(0, 0)
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
sage: G.edges(sort=False)
[(0, 1, None), (0, 1, 'label')]
sage: G.remove_loops(vertices=[0, 1])
sage: G.edges(sort=False)
[(0, 1, None), (0, 1, 'label')]
sage: G.remove_loops(vertices=[0..100])

Python

>>> from sage.all import *
>>> K = graphs.CompleteGraph(Integer(2))
>>> G = MatchingCoveredGraph(K)
>>> G.allow_multiple_edges(True)
>>> G
Matching covered complete graph: multi-graph on 2 vertices
>>> G.add_edge(Integer(0), Integer(1), 'label')
>>> G.add_edge(Integer(0), Integer(0))
Traceback (most recent call last):
...
ValueError: loops are not allowed in matching covered graphs
>>> G.edges(sort=False)
[(0, 1, None), (0, 1, 'label')]
>>> G.remove_loops(vertices=[Integer(0), Integer(1)])
>>> G.edges(sort=False)
[(0, 1, None), (0, 1, 'label')]
>>> G.remove_loops(vertices=(ellipsis_range(Integer(0),Ellipsis,Integer(100))))

Note that the parameter vertices must be either None or an iterable:

Sage

sage: G.remove_loops(vertices='')
sage: G.edges(sort=False)
[(0, 1, None), (0, 1, 'label')]
sage: G.remove_loops(vertices=None)
sage: G.edges(sort=False)
[(0, 1, None), (0, 1, 'label')]
sage: G.remove_loops(vertices=0)
Traceback (most recent call last):
...
TypeError: 'Integer' object is not iterable
sage: G.remove_loops(vertices=False)
Traceback (most recent call last):
...
TypeError: 'bool' object is not iterable

Python

>>> from sage.all import *
>>> G.remove_loops(vertices='')
>>> G.edges(sort=False)
[(0, 1, None), (0, 1, 'label')]
>>> G.remove_loops(vertices=None)
>>> G.edges(sort=False)
[(0, 1, None), (0, 1, 'label')]
>>> G.remove_loops(vertices=Integer(0))
Traceback (most recent call last):
...
TypeError: 'Integer' object is not iterable
>>> G.remove_loops(vertices=False)
Traceback (most recent call last):
...
TypeError: 'bool' object is not iterable

See also

• allow_loops()

• allows_loops()

• has_loops()

• loop_edges()

• loop_vertices()

• loops()

• number_of_loops()

update_matching(matching)

Update the perfect matching captured in self._matching.

INPUT:

• matching – a perfect matching of the graph, that can be given using any valid input format of Graph.

OUTPUT:

• If matching is a valid perfect matching of the graph, then self._matching gets updated to this provided matching, or otherwise an exception is returned without any alterations to self._matching.

EXAMPLES:

Providing with a valid perfect matching of the graph:

Sage

sage: P = graphs.PetersenGraph()
sage: G = MatchingCoveredGraph(P)
sage: sorted(G.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]
sage: M = [(0, 1), (2, 3), (4, 9), (5, 7), (6, 8)]
sage: G.update_matching(M)
sage: sorted(G.get_matching())
[(0, 1, None), (2, 3, None), (4, 9, None), (5, 7, None), (6, 8, None)]

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> G = MatchingCoveredGraph(P)
>>> sorted(G.get_matching())
[(0, 5, None), (1, 6, None), (2, 7, None), (3, 8, None), (4, 9, None)]
>>> M = [(Integer(0), Integer(1)), (Integer(2), Integer(3)), (Integer(4), Integer(9)), (Integer(5), Integer(7)), (Integer(6), Integer(8))]
>>> G.update_matching(M)
>>> sorted(G.get_matching())
[(0, 1, None), (2, 3, None), (4, 9, None), (5, 7, None), (6, 8, None)]