Contents lists available atScienceDirect
Discrete Applied Mathematics
journal homepage:www.elsevier.com/locate/dam
Triangle-free projective-planar graphs with diameter two:
Domination and characterization
✩Dibyayan Chakraborty
a, Sandip Das
b, Srijit Mukherjee
b, Uma kant Sahoo
b, Sagnik Sen
c,∗aIndian Institute of Science, Bengaluru, India
bIndian Statistical Institute, Kolkata, India
cIndian Institute of Technology Dharwad, India
a r t i c l e i n f o
Article history:
Received 4 February 2020
Received in revised form 8 December 2022 Accepted 3 January 2023
Available online xxxx Keywords:
Projective-planar
Forbidden minor characterization Domination number
a b s t r a c t
In 1975, Plesník characterized all triangle-free planar graphs as having a diameter 2. We characterize all triangle-free projective-planar graphs having a diameter 2 and discuss some applications. In particular, the main result is applied to calculate the analogue of clique numbers for graphs, namely, colored mixed graphs, having different types of arcs and edges.
©2023 Elsevier B.V. All rights reserved.
1. Introduction and main results
In 1975, Plesník [19] characterized all triangle-free planar graphs1having diameter 2 by proving the following result.
Theorem 1(Plesník 1975 [19]).A triangle-free planar graph G has a diameter2if and only if it is isomorphic to one of the following graphs:
(i) K1,nfor n
≥
2, (ii) K2,nfor n≥
2,(iii) the graph C5(m
,
n)obtained by adding(m+
n)degree-2vertices to the5-cycle C5= v
1v
2v
3v
4v
5v
1, for m,
n≥
0, in such a way that m of the vertices are adjacent tov
1, v
3and n of the vertices are adjacent tov
1, v
4.We prove the analogue of Plesník’s result for projective-planar graphs, that is, graphs that can be embedded on the non-orientable surface of Euler genus one (also known as the real projective plane) without their edges crossing each other except, maybe, on the vertices. For convenience, let us refer to the graphs listed inTheorem 1asPlesník graphs.
Theorem 2. A triangle-free projective-planar graph G has diameter2if and only if it is isomorphic to one of the following:
(i) a Plesník graph, (ii) K3,3or K3,4,
✩ This work is partially supported by the IFCAM project Applications of graph homomorphisms (MA/IFCAM/18/39).
∗ Corresponding author.
E-mail address: sen007isi@gmail.com(S. Sen).
1 In this article, we use the notation and terminology of ‘‘Introduction to Graph Theory’’ by D. B. West [22].
https://doi.org/10.1016/j.dam.2023.01.001 0166-218X/©2023 Elsevier B.V. All rights reserved.
Fig. 1.(i) The Petersen graphP10, (ii) The Wagner graphW8, (iii) The graphW8+, (iv) The Grötzsch graphM11, (v) The graphM11−, (vi) The graph M11=, (vii) The graphK3∗,4.
(iii) the graph K3,3(n)obtained by adding(n
−
1)parallel edges e2,
e3, . . . ,
ento one of the edges e1of K3,3and subdividing each ei exactly once for n≥
1,(iv) the graph K3,4(n)obtained by adding(n
−
1)parallel edges e2,
e3, . . . ,
ento one of the edges e1of K3,4and subdividing each ei exactly once for n≥
1,(v) one of the seven graphs depicted inFig.1.
Let us now discuss a few more results regarding properties of graphs having small diameters that can be embedded on a given surfaceSto place our work into context. SinceShas an Euler characteristic, it follows from the Euler’s formula [16]
that any graph embedded inShas a bounded minimum degree. This implies that if we consider such a graph with diameter 2, then its domination number is at most its minimum degree.
In 1996, MacGillivray and Seyffarth [14] proved that planar graphs with diameter 2 have domination numbers at most 3. In 2002, Goddard and Henning [9] showed that there is exactly one planar graph having diameter 2 that has a domination number equal to 3. They also proved that for each surface (orientable or non-orientable)S, there are finitely many graphs having diameter 2 and domination number at least 3 that can be embedded inS. A natural question to ask in this context is the following.
Question 1. Given a surfaceS, can you find the list of all graphs having diameter2and domination number at least3that can be embedded onS?
As we just mentioned, Goddard and Henning [9] answered Question 1when S is the sphere (or equivalently, the Euclidean plane). However, it seems that the question can be very difficult to answer in general as the tight upper bounds on the domination number for a family of graphs that can be embedded on a surface, other than the sphere, is yet to be found. Therefore, it makes sense to ask the following natural restriction instead.
Question 2. Given a surfaceS, can you find the list of all triangle-free graphs having a diameter2and domination number at least3that can be embedded onS?
Notice that, Plesník’s characterization implies that the answer forQuestion 2is the empty list whenSis the sphere.
On the other hand, the following immediate corollary ofTheorem 2answers the question whenSis the projective plane, along with implying that the domination number of triangle-free projective-planar graphs having diameter 2 is at most three (following our earlier discussions on Euler’s characteristic). Note that the domination number of graphs shown in Fig. 1is three.
Theorem 3. Let G be a triangle-free projective-planar graph having a diameter2. Then (a) The domination number
γ
(G)of G is at most3.(b) If
γ
(G)=
3, then G is isomorphic to one of the seven graphs depicted inFig.1.AsTheorem 3follows directly from Theorem 2, we will focus on proving Theorem 2. This is done in Section2. In Section3, we provide some direct implications of our results in determining the absolute clique number of the families of triangle-free projective-planar graphs, which is an important parameter in the theory of homomorphisms of colored mixed graphs.2
2. Proof ofTheorem 2
It is known, due to Euler’s formula [16] for projective-planar graphs, that any triangle-free projective-planar graphG has minimum degree
δ
(G)≤
3. Therefore, any triangle-free projective-planar graph having a diameter 2 has a domination number at most 3.Notice that as the family of projective-planar graphs is minor-closed, due to The Graph Minor Theorem [20], there exists a finite setSof graphs such that a graphGis projective-planar if and only ifGdoes not contain a minor fromS. Actually, an explicit description of the setSis provided in [2] (see [16]) and it contains 35 graphs. However, we will not need the full list for our proof — to be precise, we will use only three graphs from that list: (1)K3,5, (2)K4−,4, i.e., the graph obtained fromK4,4by deleting exactly one edge, and (3) the graphF0depicted inFig. 2.
2 The related definitions are deferred to Section3.
12
Fig. 2. The graphs (a)F0, (b)F1, (c)F2, and (d)F3form the graph familyD′.
Observation 1([2]; see [16]).The graphs K3,5, K4−,4, and F0are not projective-planar.
Thus any graph containing K3,5,K4−,4, or F0 as a minor is not projective-planar as well. Even though the previous statement is obvious, we will present it as another observation as it will be frequently used in our proofs.
Observation 2([2]; see [16]).If G contains K3,5, K4−,4, or F0as a minor, then G is not a projective-planar graph.
Now we get into the more technical part of our proof. First of all, for convenience, let us denote the family of all triangle-free projective-planar graphs having diameter 2 byPP2. Therefore, what we are trying to do here is to provide a list of all graphs inPP2. We already know that ifG
∈
PP2, then its minimum degreeδ
(G) is at most 3. We will use this as the basis of our case analysis. Observe that anyG∈
PP2is connected. Therefore, the logical first step is to handle the graphs having a degree one vertex.2.1. Characterizing graphs inPP2having minimum degree at most2
Lemma 1. If
δ
(G)=
1for a graph G∈
PP2, then G is isomorphic to K1,nfor some n≥
2.Proof. Let
v
be a degree-1 vertex inGhavingv
1as its only neighbor. AsGhas diameter 2,v
1must be adjacent to all the vertices inV(G)\ { v, v
1}
. Moreover, asGis triangle-free, the set of all neighborsN(v
1) ofv
1is an independent set. □The next natural step is to consider the graphs having minimum degree equal to 2.
Lemma 2. If
δ
(G)=
2for a graph G∈
PP2, then G is isomorphic to K2,n+2, C5(m,
n), K3,4(n), or K3,3(n)for some m,
n≥
0.Proof. Let
v
be a degree-2 vertex havingN(v
)= { v
1, v
2}
. Let C=
(N(v
1)∩
N(v
2))\ { v }
andSi=
N(v
i)\
(C∪ { v }
) fori∈ {
1,
2}
.S1
∪
S2induces a complete bipartite graph (else the end vertices of any non-edge would be at a distance greater than 2, a contradiction) and asδ
(G)≥
2, both sets are nonempty.If
|
S1| ≥ |
S2| ≥
3, then we find aK4−,4by taking the graph induced byS1∪
S2∪ { v
1, v
2}
. This is a contradiction due to Observation 2. Thus we must have|
S2| ≤
2.If
|
S2| =
2, then|
S1| ≤
3 as otherwise we can contract the edgevv
1to find aK3,5induced byS1∪
S2∪ { v
1, v
2}
. This is a contradiction due toObservation 2.Now observe that
|
S1| =
3 and|
S2| =
2 impliesGis isomorphic toK3,4(n), wheren= |
C| +
1. Similarly,|
S1| =
2 and|
S2| =
2 impliesGis isomorphic toK3,3(n), wheren= |
C| +
1.If
|
S2| =
1,|
S1|
can have any value greater than or equal to 1. In this case,Gis isomorphic toC5(m,
n), wherem= |
C|
andn= |
S1| −
1. □2.2. Characterizing graphs inPP2that are3-regular
This leaves us with the final case: considering the graphs having minimum degree equal to 3. We break this case into two parts, namely, whenGis 3-regular and whenGis not 3-regular, and tackle them separately. Also we will use some new terminologies.
A vertex u reachesa vertex
v
if they are adjacent or they have a common neighbor. In particular, ifw
is a common neighbor ofuandv
, then we use the termureachesv
viaw
.Lemma 3. If a3-regular graph G
∈
PP2, then G is isomorphic to either K3,3or W8or P10.13
Proof. Let
v ∈
V(G) be any vertex having neighbors{ v
1, v
2, v
3}
. Moreover, letSidenote the set of vertices inG\ { v }
which are adjacent to exactlyivertices among{ v
1, v
2, v
3}
. Note that, asGhas diameter 2, every vertex inG\{ v, v
1, v
2, v
3}
belongs to exactly one ofS1,
S2, andS3.Observe that asGis 3-regular, we must have
|
S3| ≤
2. Moreover, if|
S3| =
2, thenGis isomorphic toK3,3.If
|
S3| =
1, then note that we must have|
S2| ≤
1 as otherwise, it will force one of the vertices among{ v
1, v
2, v
3}
to have at least two neighbors inS2, and hence have at least four neighbors inG, contradicting the 3-regularity ofG.Furthermore, if
|
S3| = |
S2| =
1, then without loss of generality we may assume thatS2= {
u} ⊆
N(v
1)∩
N(v
2). Thus umust reachv
3via some vertexu′∈
S1∩
N(v
3). Now each vertex among{ v
1, v
2, v
3}
already has three neighbors and thus there cannot be any other vertex inG. Also all vertices exceptu′have degree 3 at present. Thus the 3-regularity of Gforces us to include a new vertex adjacent tou′in the graph, a contradiction. Therefore,Gcannot have|
S3| = |
S2| =
1.Thus if
|
S3| =
1, then we must haveS2= ∅
. However, due to the 3-regularity ofG, each vertex among{ v
1, v
2, v
3}
has exactly one neighbor inS1. Let us assume that the neighbors ofv
1, v
2, andv
3inS1arew
1, w
2, andw
3, respectively. Now, as each vertex among{ v
1, v
2, v
3}
already has three neighbors, there cannot be any other vertex inG. In fact, each vertex ofGother thanw
1, w
2, andw
3has degree 3 already. Thusw
1, w
2, andw
3must reach all ofv
1, v
2, andv
3either directly or via themselves. That forcesw
1, w
2, andw
3to create a triangle, contradicting the triangle-free property ofG. Therefore, Gcannot have|
S3| =
1.Now let us consider the situation where
|
S3| =
0. First observe that|
S2| ≤
3 in this case, as otherwise one vertex among{ v
1, v
2, v
3}
has degree at least 4.If
|
S2| =
3, then without loss of generality, we may assume thatS2= {
u1,
u2,
u3}
whereui∈
S2\
N(v
i) for alli∈ {
1,
2,
3}
. Now, as every vertex among{ v
1, v
2, v
3}
already has three neighbors each, there cannot be any other vertex inG. Hence S1= ∅
. Thus, in particular, the vertexu1must reachv
1via some vertex ofS2. That will create a triangle, a contradiction.So
|
S2| ≤
2.If
|
S2| =
2 withS2= {
u1,
u2}
, then without loss of generality, assume thatv
3 is a common neighbor ofu1 andu2. Moreover, the sum of the degrees ofv
1, v
2, andv
3 at the moment is 7 and therefore we must have exactly two more vertices inG. Thus,|
S1| =
2 and we may assume thatS1= { w
1, w
2}
. Observe thatu1 and u2 must have exactly one neighbor each inS1as they cannot be adjacent to each other in order to avoid creating a triangle. This implies that there are exactly two edges between the setsS1andS2. Thus at least one vertex ofS1does not have degree 3 unlessw
1andw
2are adjacents. Hence
w
1andw
2must be adjacent. This implies thatw
1andw
2do not have a common neighbor. Therefore, without loss of generality, we may assume thatw
i andui are adjacent tov
i for alli∈ {
1,
2}
. Hence the edgesu1w
2and u2w
1are inG. Observe thatGis isomorphic toW8in this case.We have a total of nine vertices, not possible for a 3-regular graph (as nine is an odd number).
If
|
S2| =
0, then eachv
ihas exactly two neighborsw
i andw
′i inS1for alli∈ {
1,
2,
3}
. Without loss of generality,w
1reaches
v
2andv
3viaw
2andw
3, respectively. Asw
1already has three neighbors,w
′2andw
′3must reachv
1viaw
′1. Note that,w
2cannot reachv
3viaw
3in order to avoid a triangle. Therefore,w
2reachesv
3viaw
3′. Similarly,w
3reachesv
2viaw
′2. This implies thatGis isomorphic toP10. □2.3. Characterizing not regular graphs inPP2having minimum degree3
Finally, the case where
δ
(G)=
3 and∆(G)≥
4 is handled. The proof ofLemma 4is lengthy; in order to make the proof easier to follow, we have divided it into several claims and lemmas and presented it in a separate subsection.Lemma 4. If
δ
(G)=
3and∆(G)≥
4for a graph G∈
PP2, then G is isomorphic to K3,4, K3+,4, W8+, M11, M11−, or M11=. We will begin by presenting some basic conventions to be used throughout this section.2.3.1. Conventions used in the proof ofLemma4
Let
v ∈
V(G) be a vertex with maximum degree and letN(v
)= { v
1, v
2, v
3, v
4} ∪
Xwhere Xmay or may not be∅
. Moreover, letSi denote the set of vertices inG\ { v }
which are adjacent to exactlyivertices among{ v
1, v
2, v
3, v
4}
(see Fig. 3). Furthermore, letm2be the cardinality of a maximum matching inS2.2.3.2. Basic structural properties
The proof ofLemma 4runs via a series of claims and lemmas. In the case of the claims, we always assume that
δ
(G)=
3 andd(v
)=
∆(G)≥
4 for a graphG∈
PP2.This brings us to our first two observations.
Claim 1. A vertex in S3
∪
S4is not adjacent to a vertex in S2∪
S3∪
S4.Proof. Any vertex inS4
∪
S3has at least one neighbor in common with any vertex inS2∪
S3∪
S4. Hence, any edge between S4∪
S3andS2∪
S3∪
S4will create a triangle. □Claim 2. The value of
|
S4| + |
S3| +
m2is at most2.14
Fig. 3. Illustrations of our convention.
Proof. Observe that each vertex ofS3reaches three of the four vertices among
{ v
1, v
2, v
3, v
4}
directly and one of them via a vertex ofS1(byClaim 1). Therefore, if we contract all the edges between{ v
1, v
2, v
3, v
4}
andS1, then each vertex of S3becomes adjacent to every vertex of{ v
1, v
2, v
3, v
4}
. Moreover, suppose there is an edge having both its end vertices inS2, then these end vertices cannot have a common neighbor, else a triangle is induced. Contracting this edge, the new resulting vertex will correspond to a vertex adjacent to each of{ v
1, v
2, v
3, v
4}
. Therefore, if|
S4| + |
S3| +
m2≥
3, thenG will contain aK4,4-minor. □Therefore, in particular, the above claim implies that
|
S4| + |
S3| ≤
2. This bound will be the basis of our case study.2.3.3. Case:
|
S4| + |
S3| =
2Claim 3. If
|
S4| + |
S3| =
2, then S2= ∅
.Proof. Recall that each vertex ofS3reaches three of the four vertices among
{ v
1, v
2, v
3, v
4}
directly and one of them via a vertex ofS1(byClaim 1). If|
S4| + |
S3| =
2, thenm2=
0 (byClaim 2). Now ifS2̸= ∅
, then each vertex ofS2reaches two of the four vertices among{ v
1, v
2, v
3, v
4}
directly and two of them via vertices ofS1. This is implied byClaim 1and the following: any vertex inS2cannot reach the two non-adjacent vertices in{ v
1, v
2, v
3, v
4}
via a vertex inS2(asm2=
0).Hence, contract all edges betweenS1and
{ v
1, v
2, v
3, v
4}
to obtain aK4,4, a contradiction. □Claim 4. If S4
∪
S3= {
u1,
u2}
andv
i is a common neighbor of u1and u2for some i∈ {
1,
2,
3,
4}
, then no vertexw ∈
S1is adjacent tov
i.Proof. By Claim 3, we know that S2
= ∅
. Therefore, each vertex in S4∪
S3 would reach non-adjacent vertices in{ v
1, v
2, v
3, v
4}
via some vertices inS1. If there exists a vertexw ∈
S1∩
N(v
i), wherev
iis as defined in the lemma statement, thenw
cannot be adjacent to any of{
u1,
u2}
(else a triangle is induced). SinceS2= ∅
(byClaim 3), the vertexw
reaches vertices in{ v
1, v
2, v
3, v
4} \ { v
i}
via vertices inS1. Contract all the edges betweenS1and{ v
1, v
2, v
3, v
4}
exceptwv
ito obtain aK4,4, a contradiction. □Claim 5. If
|
S4| + |
S3| =
2, then X= ∅
.Proof. Assume thatS4
∪
S3= {
u1,
u2}
and there exists anx∈
X.If
|
S4| =
2, thenxreachesu1andu2directly or via some other vertices not adjacent to{ v
1, v
2, v
3, v
4}
(else a triangle is induced). Contract the edges betweenxand those vertices (if they exist) via whichxreachesu1,
u2to obtain aK3,5, a contradiction.If
|
S4| =
1 and without loss of generalityu1∈
S4andu2∈
S3, thenxreachesu1directly or via some other vertexw
1not adjacent to
{ v
1, v
2, v
3, v
4}
(else a triangle is induced). Contract the edgexw
1if it exists. Observe thatu2is adjacent to some vertexw
2∈
S1in order to reach all of{ v
1, v
2, v
3, v
4}
. Contractu2w
2. Note thatxreachesu2directly, or viaw
2or via some other vertexw
3which is not adjacent to{ v
1, v
2, v
3, v
4}
. Contractxw
3, if it exists, to obtain aK3,5, a contradiction.If
|
S4| =
0 and thusu1,
u2∈
S3, thenu1andu2may be non-adjacent to the same or different vertices in{ v
1, v
2, v
3, v
4}
. Case 1. If they are non-adjacent to different vertices of{ v
1, v
2, v
3, v
4}
, then without loss of generality assume thatui is not adjacent tov
i fori∈ {
1,
2}
. In this case,uimust reachv
ivia somew
i∈
S1(byClaim 1) andxmust reachui directly or viaw
i or via somew
′i∈
S1withw
i′̸∈ { w
1, w
2}
. Contract the edgesuiw
i andxw
′i (if they exist) for all i∈ {
1,
2}
to obtain aK3,5, a contradiction.Case 2. If they are non-adjacent to the same vertex, without loss of generality say,
v
4 of{ v
1, v
2, v
3, v
4}
, thenv
4 must have at least two neighborsw
1, w
2as the degree ofv
4 is at least three. Alsow
1, w
2∈
S1 (byClaim 1). Due to Claims 3and4, we know that the only way forw
ito reachv
1is viau1oru2. Moreover, for eachi∈ {
1,
2}
,uimust reachv
4 via some vertex ofS1(byClaim 1). Therefore, we must have a perfect matching between{
u1,
u2}
and{ w
1, w
2}
. Without loss of generality, assume that perfect matching be{
u1w
1,
u2w
2}
. Furthermore, observe that if xis adjacent to any one ofu1oru2, we can rename the vertices ofN(v
) to reduce this to a case where|
S4| ≥
1, which we have already handled earlier in the proof of this lemma. Therefore,xmust reachuiviaw
i or via some15
vertex
w
i′̸∈ {
u1,
u2, w
1, w
2}
for alli∈ {
1,
2}
. Contract the edgesuiw
i andxw
′i (if they exist) for alli∈ {
1,
2}
to obtain aK3,5, a contradiction.This concludes the proof. □
Now that we have shown the setX
= ∅
when|
S4| + |
S3| =
2, we can try to characterize the graphs for this case.Lemma 5. If
δ
(G)=
3and d(v
)=
∆(G)≥
4for a graph G∈
PP2, then the following holds: if|
S4| =
2, then G is isomorphic to K3,4.Proof. If
|
S4| =
2, then X=
S3=
S2=
S1= ∅
due to Claims 2–5. The only vertices in the graphs other than{ v, v
1, v
2, v
3, v
4}
are the two vertices inS4. ThusGis isomorphic toK3,4. □Claim 6. It is not possible to have
|
S4| = |
S3| =
1.Proof. If
|
S4| = |
S3| =
1, then without loss of generality assume thatu1∈
S4,u2∈
S3\
N(v
4). Observe thatX=
S3=
S2= ∅
due toClaims 2,3and5. Moreover, all the vertices inS1are adjacent tov
4due toClaim 4. Asu2must reachv
4via some vertex ofS1, the setS1is not empty. However, any vertex ofS1has exactly two neighbors, namelyv
4andu2, contradictingδ
(G)=
3. □Lemma 6. If
δ
(G)=
3and d(v
)=
∆(G)≥
4for a graph G∈
PP2, then the following holds: if|
S3| =
2, then G is isomorphic to W8+.Proof. Assume thatS3
= {
u1,
u2}
. ThusX=
S4=
S2= ∅
due toClaims 2,3and5. Observe that it is enough to consider the following two cases: (i)u1andu2are both non-adjacent tov
4, and (ii)uiis non-adjacent tov
i fori∈ {
1,
2}
.Case (i). Ifu1andu2are both non-adjacent to
v
4, then all the vertices inS1are adjacent tov
4due toClaim 4. The verticesv, v
1, v
2, v
3, v
4,
u1, andu2and the vertices belonging toS1are all of the vertices ofG. Asδ
(G)=
3, each vertex ofS1must be adjacent to bothu1andu2. Furthermore,S1must have at least two vertices, sayw
1andw
2, asδ
(G)=
3. Now contractvv
4to obtain aK3,5induced by{
u1,
u2,
(vv
4)} ⊔ { v
1, v
2, v
3, w
1, w
2}
where (vv
4) denotes the new vertex obtained by contracting the edgevv
4. Thus this case is not possible sinceK3,5is not projective planar.Case (ii). Ifuiis non-adjacent to
v
ifori∈ {
1,
2}
, then all the vertices inS1are adjacent to eitherv
1orv
2due toClaim 4.Therefore, the vertices
v, v
1, v
2, v
3, v
4,
u1, andu2 and the vertices belonging to S1 are all of the vertices of G. Suppose thatS1= { w
1, w
2, . . . , w
k, w
′1, w
′2, . . . , w
′r}
wherew
is are adjacent tov
1andw
′js are adjacent tov
2 where (i,
j)∈ {
1,
2, . . . ,
k} × {
1,
2, . . . ,
r}
. Eachw
i reachesv
3viau1and eachw
j′is reachesv
3 viau2 for all (i,
j)∈ {
1,
2, . . . ,
k} × {
1,
2, . . . ,
r}
. Furthermore asδ
(G)=
3, eachw
i must be adjacent to somew
′jand eachw
p′ must be adjacent to somew
q. Without loss of generality and due to symmetry, we may assume that 1≤
r≤
k. Ifk≥
2, then contract the edges u2w
′j for allj∈ {
1,
2, . . . ,
r}
to obtain the new vertex (u2w
′j), and contract the edgevv
1to obtain the new vertex (vv
1). Observe that, in this contracted graph, the vertices{
u1,
(vv
1),
(u2w
′j)} ⊔ { w
1, w
2, v
2, v
3, v
4}
induce aK3,5subgraph, a contradiction. Therefore,k=
r=
1. ThusGis isomorphic toW8+.This ends the proof of the lemma. □
This concludes the case when we have
|
S4| + |
S3| =
2. We will present the summary of it in the following lemma.Lemma 7. If
δ
(G)=
3and d(v
)=
∆(G)≥
4for a graph G∈
PP2, then the following holds: if|
S4| + |
S3| =
2, then G is isomorphic to K3,4or W8+.Proof. Follows directly fromLemma 5,Claim 6, andLemma 6. □
It remains to analyze the situations when
|
S4| + |
S3| ≤
1. The first case is when|
S4| + |
S3| =
1.2.3.4. Case:
|
S4| + |
S3| =
1Claim 7. If
|
S4| + |
S3| =
1, then S2̸= ∅
.Proof. Let us assume the contrary and suppose thatS2
= ∅
. Furthermore, assume thatS4∪
S3= {
u1}
and thatu1 is adjacent to{ v
1, v
2, v
3}
. First we will show that it is not possible for anyv
i, fori∈ {
1,
2,
3}
, to have two neighbors inS1.Hence without loss of generality assume that
v
1is adjacent tow
1, w
2∈
S1. Observe that bothw
1andw
2must reachv
2, v
3, andv
4via some vertices fromS1\ { w
1, w
2}
andu1 must reachv
4 via some vertex fromS1\ { w
1, w
2}
(all due to16
Claim 1). Now contract all the edges between
{ v
2, v
3, v
4}
andS1\ { w
1, w
2}
to obtain aK4,4-minor, a contradiction. Thus eachv
is, fori∈ {
1,
2,
3}
, can have at most one neighbor inS1.However,
δ
(G)=
3 implies that eachv
imust be adjacent to exactly one vertex (say)w
i fromS1fori∈ {
1,
2,
3}
. Now note thatw
1must reachv
2andv
3viaw
2andw
3, respectively andw
2must reachv
3viaw
3. This creates a triangle induced by{ w
1, w
2, w
3}
inG, a contradiction. □Claim 8. If
|
S4| =
1and|
S3| =
0, then X= ∅
.Proof. LetS4
= {
u1}
and letx∈
X.Claim 7implies the existence of a vertexw
1∈
S2. Without loss of generality assume thatw
1is adjacent tov
1andv
2.Note thatxreachesu1directly or via some vertexa(say) not adjacent to any of
{ v
1, v
2, v
3, v
4}
in order to avoid creating a triangle inG. Moreover,w
1reachesx, v
3, andv
4via some vertices not adjacent to any of{ v
1, v
2}
. LetAdenote the set of vertices via whichw
1reachesx, v
3, andv
4. Contract the edges betweenA\ {
a}
andw
1and the edgexa. The vertices{ v, w
1,
u1} ⊔ {
x, v
1, v
2, v
3, v
4}
form the partition of aK3,5-minor, a contradiction. □Claim 9. If
|
S4| =
1and|
S3| =
0, then m2=
1.Proof. ByClaim 2,m2
≤
1. Next, suppose thatS4= {
u1}
andm2=
0. That means every vertex ofS2(which is non-empty byClaim 7) must reach its non-adjacentv
is via vertices ofS1 (byClaim 1 and m2=
0). Therefore, if|
S2| ≥
2, then contracting the edges betweenS1and{ v
1, v
2, v
3, v
4}
will create aK4,4-minor.Thus, we have
|
S2| =
1. Without loss of generality assume thatS2= { w }
and thatw
is adjacent tov
1andv
2. Notice thatw
must reachv
3andv
4viaw
3, w
4∈
S1, respectively (byClaim 1andm2=
0). Thus to avoid creating a triangle,w
3must reachv
4viaw
4′∈
S1. Moreover, to avoid creating a triangle,w
4′ must reachv
1via somew
1∈
S1.Notice that,
w
1 reachesv
2, v
3, andv
4 via some elements ofS1. Thus, if we contract all the edges betweenS1 and{ v
2, v
3, v
4}
, we will create aK4,4-minor.Therefore,m2
≥
1. Sincem2≤
1 byClaim 2, we havem2=
1. □Lemma 8. If
δ
(G)=
3and∆(G)≥
4for a graph G∈
PP2, then the following holds: if|
S4| =
1and|
S3| =
0, then G is isomorphic to K3∗,4.Proof. LetS4
= {
u1}
and, thus, byClaim 9we know thatm2=
1. Then without loss of generality we may assume the existence of an edgew
1w
2such thatw
1, w
2∈
S2,w
1is adjacent tov
1 andv
2, andw
2is adjacent tov
3 andv
4. If there are no other vertex or edge inG, thenGis isomorphic toK3∗,4.However, if there is another vertex
w
3∈
S2and ifw
3reaches{ v
1, v
2, v
3, v
4}
directly or via some vertices exceptw
1and
w
2, then contract the edgew
1w
2. Also contract the edges betweenw
3and the vertices via whichw
3reachesv
is, for i∈ {
1,
2,
3,
4}
. This will result in aK4,4-minor.On the other hand, if there is a
w
3∈
S2 and ifw
3 reaches{ v
1, v
2, v
3, v
4}
directly or viaw
i for somei∈ {
1,
2}
, then Gis the graphF1 (depicted inFig. 2(b)) that contains the graphF0 (depicted inFig. 2(a)) as a subgraph, and thus as a minor. □So far we were dealing with the case when Gis a graph with
|
S4| =
1 and|
S3| =
0. Now we turn our attention towards the case whenG is a graph with|
S4| =
0 and|
S3| =
1. Initially, we will observe some properties that this condition implies. However, finally, the satisfaction of those properties will turn out to be impossible, thereby proving that there are no required graphs with|
S4| =
0 and|
S3| =
1.Claim 10. If
|
S4| =
0and|
S3| =
1, then X= ∅
.Proof. Suppose that X
̸= ∅
andx∈
X. LetS3= {
u1}
and without loss of generality letu1 be adjacent tov
1, v
2, v
3. Therefore,u1must reachv
4viaw
4∈
S1(byClaim 1). We know thatS2̸= ∅
due toClaim 7. Also letu2∈
S2.Ifu2reaches
v
4directly or via any vertex other thanw
4, then contract the edgeu1w
4, all the edges connectingu2to its neighbors via whichu2reachesv
1, v
2, v
3orv
4, and all the edges connectingxto its neighbors via whichxreachesu1 andu2, in order to obtain aK3,5-minor (see the vertices in the partition{ v,
u1,
u2} ⊔ {
x, v
1, v
2, v
3, v
4}
).Thus u2reaches
v
4viaw
4 and nothing else. Hence without loss of generality, we may assume thatu2is adjacent tov
1 andv
2 and thatu2reachesv
3 viaw
3∈
S1(ifw
3∈
S2, thenw
3must be adjacent tov
3, v
4and by similar arguments as the previous case existenceK3,5 minor can be shown). Moreover, asδ
(G)=
3, there must be aw
4′∈
S1 adjacent tov
4. On the other hand,v
1 cannot have a neighbor inS1, as otherwise we may contract all the edges betweenS1 and{ v
2, v
3, v
4}
to obtain aK4,4-minor. Therefore,w
4′ must reachv
1 via u1 (ifw
4′ reachesv
1 viau2, then a K3,5-minor is formed: see the vertices in the partition{ v,
u1,
u2} ⊔ {
x, v
1, v
2, v
3, v
4}
). Now contract the edgesu1w
′4,
u2w
3,
u2w
4, and all the edges connectingx to its neighbors via which x reaches u1,
u2. Ifx is adjacent tow
4, then also contract the edge connectingxto its neighbor via whichx reachesw
′4. This creates aK3,5-minor (see the vertices in the partition{ v,
u1,
u2} ⊔ {
x, v
1, v
2, v
3, v
4}
). □17