EuroComb 2005 DMTCS proc.AE, 2005, 135–138
A characterization of extremal graphs with no matching-cut
Paul Bonsma
Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, Netherlands
A graph is called (matching-)immune if it has no edge cut that is also a matching. Farley and Proskurowski proved that for all immune graphsG= (V, E),|E| ≥ d3(|V| −1)/2e, and constructed a large class of immune graphs that attain this lower bound for every value of|V(G)|, called ABC graphs. They conjectured that every immune graph that attains this lower bound is an ABC graph. We present a proof of this conjecture.
Keywords:matching-cut, matching immune, extremal graphs
1 Introduction
All graphs in this paper are allowed to be multi-graphs. For a graphG = (V, E), an edge cut[S, S]
withS ⊂V is called amatching-cutif[S, S]is a matching. If a graph has no matching-cut, it is called (matching-)immune. Farley and Proskurowski [Farley and Proskurowski(1984)] proved the following ex- tremal result on immune graphs:
Theorem 1 (Farley and Proskurowski) IfG= (V, E)is immune, then
|E| ≥ d3(|V| −1)/2e.
In addition, they constructed a class of multi-graphs calledABC graphsthat have the following properties:
• ABC graphs are immune.
• IfG= (V, E)is an ABC graph, then|E|=d3(|V| −1)/2e.
The definition of ABC graphs is based on the following three operations:
• AnA operationon vertexuintroduces verticesvandwand edgesuv,uwandvw.
• AB operationon edgeuvintroduces verticeswandxand edgesuw,vw,uxandvx, and removes edgeuv.
• AC operationon verticesuandv(u=vis allowed) introduces vertexwand edgesuwandvw.
Note that the C operation is the only operation that can introduce parallel edges.
1365–8050 c2005 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France
136 Paul Bonsma
C3:
P2:
C4:
C2:
Fig. 1:The four reduction operations
Definition 1 AnABC graphis a graph that can be obtained fromK1with a sequence of A and B opera- tions andat most oneC operation.
A sequence of these operations that constructs a graphGfrom a graphHis called adecompositionofG fromH, or simply a decomposition ofGifH =K1. For every integern≥1, an ABC graph exists. For every integern≥1,n6= 2, a simple ABC graph exists. This shows that the lower bound from Theorem 1 is tight. This inspires the following definition:
Definition 2 A graphG= (V, E)is calledextremal immuneif|E|=d3(|V| −1)/2eandGis immune.
Farley and Proskurowski stated the following conjecture:
Conjecture 2 (Farley and Proskurowski) If a graphGis extremal immune, thenGis ABC.
In this paper, we sketch our proof of this conjecture, and show some of the techniques that are used. First we will go into more detail on Farley and Proskurowski’s proof of Theorem 1.
2 Contraction operations
To prove Theorem 1, Farley and Proskurowski [Farley and Proskurowski(1984)] introduce four graph operations, named after the structure they reduce. These operations are explained in Figure 1. Below are formal definitions, which show that all of these operations can be expressed with edge deletions and contractions.C2stands for the cycle of length two, which is a multi-graph.
C2 Let verticesuandvinduce aC2in graphG. The C2 operation consists of deleting one of the edges of thisC2and contracting the other.
C3 Let verticesu,vandwinduce aC3inG. The C3 operation consists of deletinguvand contracting vwandwu.
C4 Let verticesu,v,wandxinduce a C4 inGsuch thatuw 6∈ E(G). The C4 operation consists of deleting uvand contracting uxandvw. Note that for one inducedC4 the C4 operation can be applied in two different ways.
P2 Let verticesuandvbe neighbors inGwithd(u) = 3andd(v) = 2. Letv have another neighbor z 6= u, and letuhave another neighborx 6= v. The P2 operation consists of deletinguv and contractinguxandvz.
A characterization of extremal graphs with no matching-cut 137 It can be checked that these four operations have the following properties:
Lemma 3 (Farley and Proskurowski) SupposeG0can be obtained fromGby a C2, C3, C4 or P2 oper- ation. Then:
• IfGis immune, thenG0is immune.
• If|E(G)|=d3(|V(G)| −1)/2e, then|E(G0)| ≤ d3(|V(G0)| −1)/2e. This inequality is always an equality for the C3, C4 and P2 operation.
To prove Theorem 1, the following lemma was used:
Lemma 4 (Farley and Proskurowski) IfGis an extremal immune graph not equal toK1, then one of the operations C2, C3, C4 or P2 can be applied toG.
On this lemma our proof of Conjecture 2 is based.
3 Overview of the proof
The proof of Conjecture 2 is by contradiction, so first we assume an extremal immune graph exists that is not an ABC graph. Then we consider a graph with minimum number of vertices among all such graphs.
This explains the following definition:
Definition 3 A graphGis aminimum counterexampleif it is extremal immune, it is not an ABC graph, and has minimum number of vertices among all such graphs.
We first consider the case that a minimum counterexampleGcontains a C2, so a C2 operation can be applied, resulting in vertexv. After applying this C2 operation, another extremal indecomposable graph G0is obtained (Lemma 3, Theorem 1). By our choice ofG,G0 must be an ABC graph. We consider a number of cases forG0, for the choice ofv∈V(G0)and for the possible graphsGthat can correspond to this, and in every case we obtain one of the following contradictions:Ghas a matching-cut,Gis also an ABC graph, or a smaller counterexample exists.
If a minimum counterexampleGcontains a triangle, we can apply operation C3 and find a contradiction in a similar way, and ifGcontains aC4, applying a C4 operation leads to a contradiction. Finally, we can show that if a P2 operation can be applied resulting in the ABC graphG0, then there is always a triangle orC4inG0 that corresponds to a triangle orC4inG, so the previous cases can be applied. Since every operation leads to a contradiction, Lemma 4 shows that no counterexamples for the conjecture can exist.
4 The structure of ABC graphs
Definition 4 A graphGthat can be obtained from a graphH using only B operations is called anH- component.
These graphs will often be used forHin this case:
K2 AK2-componentGis also called anedge component. IfGcan be constructed from aK2on vertices uandv, thenGis called an edge componentbetweenuandv.
C3 AC3-component is also called atriangle component.
138 Paul Bonsma We can partition the edges of ABC graphs into edge induced components that are allH-components for H =C3,C2 orP3, whereC3-components correspond to A operations in the decomposition, and the C operation corresponds to aC2orP3-component:
Observation 5 For any decomposition of ABC graphGusingkA operations, we can partition the edges ofGinto setsA1, . . . , Akand at most one setCsuch that for everyi,G[Ai]is a triangle component, and G[C]is aC2orP3-component.
Observation 6 For any decomposition of anH-componentG, we can partitionE(G)into sets{Euv : uv∈E(H)}such thatG[Euv]is an edge component betweenuandv.uandvare the only vertices of G[Euv]that can be incident with other edges inG.
Lemma 7 For every edge componentGbetweenuandv, and every edgee∈E(G), a matching-cutM exists that separatesufromvwithe∈M.
Lemma 8 Ifuis a vertex in a triangle componentT, then a decomposition ofTexists that starts onu.
5 An example case
Consider the case that minimum counterexampleGcontains a triangle on verticesu1,u2andu3, and a C3 operation on this triangle yields ABC graphG0 that consists of a single triangle component. Vertex u∈V(G0)corresponds to the contracted triangle.
Edges ofG0correspond to edges ofG, since the C3 operation consists of contraction and edge deletion operations.G[M]denotes the graph induced by the edges ofGthat correspond toM ⊂E(G0)this way.
IfG[E(G0)]is isomorphic toG0, then all edges incident withu∈V(G0)must w.l.o.g. be incident with u1 ∈V(G). In this case,Gcan be obtained fromG0 with a single A operation onuintroducingu2and u3, and renaminguasu1. SoGis an ABC graph in this case, a contradiction.
Now suppose G[E(G0)] is not isomorphic toG0. By Lemma 8, we know that a decomposition of G0 exists that starts with vertexu. Suppose the first A operation introduces verticesv andw. Now the edges ofG0 can be partitioned into edge componentsFuv,Fuw andFvw that correspond to the edges introduced in this first A operation (Observation 6). SinceG[E(G0)]is not isomorphic toG0, it follows that there are edgese∈E(Fuv)andf ∈E(Fuw)that are both incident withuinG0, but that correspond w.l.o.g. to edges incident withu1resp.u2inG. SinceG0is a simple graph,eandf therefore correspond to non-adjacent edges inG. Now consider a matching-cut M1 inFuv that separatesu fromv, such thate ∈ M1, and a matching-cutM2inFuwthat separatesufromw, such thatf ∈ M2 (Lemma 7).
Using Observation 6, it can be checked thatM1∪M2 corresponds to a matching-cut inG, which is a contradiction.
Acknowledgements
The author would like to thank Andrzej Proskurowski and Hajo Broersma for their suggestions and the discussions on this subject.
References
[Farley and Proskurowski(1984)] A. M. Farley and A. Proskurowski. Extremal graphs with no discon- necting matching. In Proceedings of the second West Coast conference on combinatorics, graph theory, and computing (Eugene, Ore., 1983), volume 41, pages 153–165, 1984.
