Cycles of length 3 and 4 in edge-colored complete graphs with restrictions in
the color transitions111Research supported by grants CONACYT FORDECYT-
PRONACES/39570/2020 and UNAM-DGAPA-PAPIIT IN102320 (H. Galeana-Sánchez), and
CONACYT scholarship for postgraduate studies 782604 (F. Hernández-Lorenzana)

$\text{Hortensia Galeana-Sánchez}^{\text{a}},\text{Felipe Hernández-
Lorenzana}^{\text{a,}},\text{Rocío Sánchez-López}^{\text{b}}$222Corresponding
author

aInstituto de Matemáticas, Universidad Nacional Autónoma de México, Área de la
investigación científica, Circuito Exterior, Ciudad Universitaria, 04510
Coyoacán, CDMX, Mexico
bFacultad de Ciencias, Universidad Nacional Autónoma de México, Ciudad
Universitaria, Circuito Exterior s/n, 04510 Coyoacán, CDMX, Mexico 000Email
adresses<EMAIL_ADDRESS>(H. Galeana-Sánchez),
<EMAIL_ADDRESS>(F. Hernández-Lorenzana),
<EMAIL_ADDRESS>(R. Sánchez-López)

###### Abstract

Let $G$ be an edge-colored graph, a walk in $G$ is said to be a properly
colored walk iff each pair of consecutive edges have different colors,
including the first and the last edges in case that the walk be closed. Let
$H$ be a graph possible with loops. We will say that a graph $G$ is an
$H$-colored graph iff there exists a function $c:E(G)\longrightarrow V(H)$. A
path $(v_{1},\cdots,v_{k})$ in $G$ is an $H$-path whenever
$(c(v_{1}v_{2}),\cdots,$ $c(v_{k-1}v_{k}))$ is a walk in $H$, in particular, a
cycle $(v_{1},\cdots,v_{k},v_{1})$ is an $H$-cycle iff
$(c(v_{1}v_{2}),\cdots,c(v_{k-1}v_{k}),$ $c(v_{k}v_{1}),c(v_{1}v_{2}))$ is a
walk in $H$. Hence, $H$ decide which color transitions are allowed in a walk,
in order to be an $H$-walk. Whenever $H$ is a complete graph without loops, an
$H$-walk is a properly colored walk, so $H$-walk is a more general concept. In
this paper, we work with $H$-colored complete graphs, with restrictions given
by an auxiliary graph. The main theorems give conditions implying that every
vertex in an $H$-colored complete graph, is contained in an $H$-cycle of
length 3 and in an $H$-cycle of length 4. As a consequence of the main
results, we obtain some well-known theorems in the theory of properly colored
walks.

Keywords: Edge-colored graph, $H$-cycle, Properly colored walk

##  1 Introduction

We assume that the reader is familiar with the standard terminology on graph
theory, and for further notation and terminology not defined here, we refer
the reader to [5]. In this paper we work with simple finite graphs. Whenever
$G$ is a graph, $V(G)$ will denote the set of vertices and $E(G)$ the set of
edges of $G$. The order of the graph $G$ is its number of vertices $|V(G)|$.

A graph $G$ of order $n$ is said to be pancyclic iff it contains a cycle of
length $l$ for every $l$ in $\\{3,\cdots,n\\}$, and $G$ is called vertex-
pancyclic whenever each vertex of $G$ belongs to a cycle of length $l$ for
each $l$ in $\\{3,\cdots,n\\}$. The pancyclicity and the vertex-pancyclicity
in graphs have been deeply studied since 1971, when Bondy conjectured in [6]
that almost every non-trivial condition implying that a graph $G$ is
hamiltonian, also implies that $G$ is pancyclic. At least 127 papers have been
published in these topics, see for example [2], [7] and [8]. Bondy’s
metaconjecture has been verified by adding some extra conditions, and since
vertex-pancyclicity implies pancyclicity and pancyclicity implies
hamiltonicity, this motivates the research of conditions implying the vertex-
pancyclicity in a graph. In [20], Ming-Chu Li et al. proved that determining
wheter a graph is pancyclic (or vertex-pancyclic) is an $NP$-complete problem,
even for 3-connected cubic planar graph.

We can think in the following application: a travel agency has offices in $n$
cities, between some of which it is possible to travel directly (avoiding any
other city). To offer a large variety of trips, the tourism agency want to
determine if for every $k$ in $\\{3,\cdots,n\\}$ there exists a tour starting
and ending in the same city, and passing by each of $k$ cities exactly once in
some order. Moreover, they want to determine if this is possible to do it
regardless the departure city. Therefore, in terms of Graph Theory, we want to
determine whether the graph associated with the problem is pancyclic or
vertex-pancyclic.

Now we can consider the following application in relation to the means of
transportation: for each two consecutive cities on a given tour, there exists
several ways to travel (say bus, plane, train, boat, and so on), and according
to the customer’s preferences, there will be some transport transitions that
should be avoided, and some others that will be needed. For example, if from
city $A$ to city $B$ the customer traveled by plane, then from city $B$ to
city $C$ the travel must be done by train, or another possibility is that the
customer prefers to do the tour exclusively by bus. We can represent this
situation with an edge-colored multigraph, where each vertex represents a
city, and in order to make more visual the representation of this problem, we
will have an edge with color $i$ between two different vertices $A$ and $B$,
whenever we can travel from the city $A$ to the city $B$ directly by the
$i$-th means of transportation. In this modify problem, it does not suffices
to find a cycle of length $k$ for every $k$ in $\\{3,\cdots,n\\}$, but now we
have to find a cycle (tour) of length $k$ according to the restrictions given
by the color transitions in the obtained edge-colored multigraph (customer).

In this paper, we work in an edge-colored simple graph $G$ and we deal with
the problem of finding conditions implying that, for each vertex $x$ of $G$
there exists an edge-colored cycle of length 3 (respectively 4) containing $x$
with some constraints given in the coloring of the graph.

A walk in an edge-colored graph is a properly colored walk, iff every two
consecutive edges have different colors, including the first and last edges
when the walk is closed. The theory of properly colored walks has relevance in
Graph Theory and Algorithms [18] and [29]. The study of applications on
properly colored structures starts in 1891, with the remarkable paper by
Petersen (see[23]). Properly colored walks have shown to be an effective way
to model some real applications in different fields, as we can mention Genetic
and Molecular biology [10], [11], [24], Social Sciences [9], Engineering and
Computer Science [1], [26], [28], and Management Science [30], [31]. There
exist some classical results in the theory of properly colored walks, we have
for example Kotzig’s Theorem [19], which provides a characterization of edge-
colored multigraphs, having properly colored closed Euler trails. As closed
trails contain cycles, we can ask whether a properly colored trails contain
properly colored cycles, and in general, ask for conditions implying the
existence of properly colored cycles. Solving this question, in 1983 Grossman
and Häggksvit [16] proved Theorem 1.1 when $c=2$, and later Yeo proved it for
every $c\geq 2$. Although the problem of determining the existence of properly
hamiltonian cycles, in 2-edge-colored graphs is $NP$-complete (see [4]), we
can check whether an $c$-edge-colored graph have a properly colored cycle in
polynomial time, using a recursive algorithm provided by Yeo’s Theorem.
Moreover, in [17] the authors proved that a shortest properly colored cycle
can be found in polynomial time. For a classical survey in this topic, see
chapter 16 in [4], and a more recent survey can be found in [3] and [21].

######  Theorem 1.1 (Yeo, [32]).

Let $G$ be a $c$-edge-colored graph, $c\geq 2$, with no properly colored
cycle. Then, $G$ has a vertex $z$ in $V(G)$, such that no connected component
of $G-z$ is joined to $z$, with edges of more than one color.

In view of these theorems, it is natural to ask for conditions implying the
existence of colored walks, with restrictions in the color transitions. In
[27], Szachniuk et al. introduced what they called the Orderly Colored Longest
Path problem (OCLE), that is: if $G$ is an edge-colored graph with colors in
$C$, $P=(v_{1},\cdots,v_{n})$ is a path in $G$, and $O=\langle
c_{1},\cdots,c_{k}\rangle$ is a fixed sequence of colors for some colors
$c_{1},\cdots,c_{k}$ in $C$, then $P$ is an orderly colored path, if the
colors of consecutive edges in $P$ follow the color sequence defined by $O$.
Notice that, if $P$ is an orderly colored path following the color sequence
$O$, and the length of $O$ equals 2 with the two colors of $O$ different, then
$P$ is a properly colored path. For other applications motivating the study of
colored paths with constraints in the color sequence, see [27].

The following concepts, which are more general than the previous one, were
introduced in a work developed by Linek and Sands in [22], in the context of
kernels in arc-colored directed graphs.

Let $H$ be a graph possibly with loops and $G$ be a graph. We say that $G$ is
an $H$-colored graph whenever there exists a function $c:E(G)\rightarrow
V(H)$. A path $(v_{1},\cdots,v_{n})$ in an $H$-colored graph $G$ is an
$H$-path iff $(c(v_{1}v_{2}),c(v_{2}v_{3}),\cdots,$ $c(v_{n-1}v_{n}))$ is a
walk in the graph $H$, in particular, a cycle $(v_{1},\cdots,v_{n},v_{1})$ is
an $H$-cycle whenever
$(c(v_{1}v_{2}),c(v_{2}v_{3}),\cdots,c(v_{n-1}v_{n}),c(v_{n}v_{1}),c(v_{1}v_{2}))$
is a walk in $H$. Notice that, if $H$ is the complete graph without loops,
then an $H$-path is a properly colored path. Moreover, the concept of $H$-path
generalizes the concept of orderly colored path, because if $O=\langle
c_{1},\cdots,c_{k}\rangle$ is the sequence of colors given, then it is enough
to consider any graph $H$ such that $\\{c_{1},\cdots,c_{k}\\}\subseteq V(H)$
and $(c_{1},\cdots,c_{k},c_{1})$ is a walk in $H$, to color the edges of $G$.

The study of the existence of certain $H$-walks in $H$-colored graphs, began
in [14] in a work entitled “Some Conditions for the Existence of Euler
$H$-trails”. In [15], the authors extended Theorem 1.1 in the context of
$H$-coloring, so they found structural conditions implying the existence of
$H$-cycles in an $H$-colored graph, although no information about the length
of such a cycles was provided. In [13], the authors gave conditions implying
the existence of an $H$-cycle of length at least
$\left\lceil\frac{|V(G)|}{3}\right\rceil+1$ in an $H$-colored graph $G$. An
interesting auxiliary graph in working with $H$-colorings was defined by
Kotzig in [19] and proved be cumbersome, in [13], [14] and [15]:

######  Definition 1.1 ([19]).

Let $H$ be a graph possibly with loops and $G$ be an $H$-colored graph with a
fixed $H$-coloring $c:E(G)\longrightarrow V(H)$. For each non-isolated vertex
$x$ of $G$, we denote by $G_{x}$ the graph defined as follows:

  1. (i)

$V(G_{x})=\\{e\in E(G):e\ \mbox{is incident with}\ x\\}$.

  2. (ii)

For two different vertices $a$ and $b$ in $V(G_{x})$, $ab\in E(G_{x})$ if and
only if $c(a)c(b)\in E(H)$.

Notice that for every non-isolated vertex $x$ in $V(G)$, $G_{x}$ is a simple
graph.

Let $H$ be a graph possibly with loops, $G$ an $H$-colored graph,
$U=(x_{1},\cdots,$ $x_{n})$ a walk in $G$ and $i$ in $\\{2,\cdots,n-1\\}$. We
say that $x_{i}$ is an obstruction of $U$ whenever
$c(x_{i-1}x_{i})c(x_{i}x_{i+1})\notin E(H)$. When
$W=(x_{1},\cdots,x_{n-1},x_{1})$ is a closed walk, $x_{1}$ is an obstruction
of $W$ iff $c(x_{n-1}x_{1})c(x_{1}x_{2})\notin E(H)$. The interest of defining
obstruction of a walk and the auxiliary graph $G_{x}$, is established in the
following observation.

######  Observation 1.1.

Let $H$ be a graph possibly with loops, and $G$ be an $H$-colored graph, such
that for every $x$ in $V(G)$, $G_{x}$ is a complete $k_{x}$-partite graph for
some $k_{x}$ in $\mathbb{N}$. Suppose that $\\{ux,vx\\}$ is a subset of
$E(G)$. The following statements are equivalent:

  1. 1.

$ux$ and $vx$ are in different parts of the $k_{x}$-partition of $V(G_{x})$.

  2. 2.

$ux$ and $vx$ are adjacent in $G_{x}$.

  3. 3.

$c(ux)c(vx)\in E(H)$.

  4. 4.

$x$ is not an obstruction of the path $(u,x,v)$.

  5. 5.

$(u,x,v)$ is an $H$-path in $G$.

As a direct consequence of Observation 1.1 and the definition of $H$-cycle, we
have the following result.

######  Observation 1.2.

Let $H$ be a graph possibly with loops, and $G$ be an $H$-colored graph, such
that for every $x$ in $V(G)$, $G_{x}$ is a complete $k_{x}$-partite graph for
some $k_{x}$ in $\mathbb{N}$. Suppose that
$C=(u_{1},\cdots,u_{n-1},u_{n},u_{1})$ is a cycle in $G$. The following
statements are equivalent:

  1. 1.

$C$ is an $H$-cycle in $G$.

  2. 2.

$(c(u_{1}u_{2}),\cdots,c(u_{n-1}u_{n}),c(u_{n}u_{1}),c(u_{1}u_{2}))$ is a walk
in $H$.

  3. 3.

$u_{1},\cdots,u_{n}$ are not obstructions of the cycle $C$.

  4. 4.

$u_{i-1}u_{i}$ and $u_{i+1}u_{i}$ are in different parts of the
$k_{u_{i}}$-partition of $V(G_{u_{i}})$ for every $i$ in $\\{1,\cdots,n\\}$
(the subindices are taken modulo $n$).

In [15] was proved that, given any graphs $H$ and $G$, there exists an
$H$-coloring of $G$ such that, for every $x$ in $V(G)$, either $G_{x}$ is a
complete bipartite graph or $E(G_{x})=\emptyset$.

In this paper, we work with $H$-colored complete graphs with restrictions
given by the auxiliary graph $G_{x}$. The main results are the following:

######  Theorem 1.2.

Let $H$ be a graph possibly with loops and $G$ be an $H$-colored complete
graph of order $n$, with $n\geq 3$, such that for every $x$ in $V(G)$, $G_{x}$
is a complete $k_{x}$-partite graph for some $k_{x}$ in $\mathbb{N}$. Suppose
that

  1. 1.

For every $x$ in $V(G)$, $k_{x}\geq\frac{n+1}{2}$,

  2. 2.

$G$ does not contain a cycle of length 4 with exactly 3 obstructions.

Then each vertex of $G$ is contained in an $H$-cycle of length 3.

######  Theorem 1.3.

Let $H$ be a graph possibly with loops and $G$ be an $H$-colored complete
graph of order $n$, with $4\leq n<9$, such that for every $x$ in $V(G)$,
$G_{x}$ is a complete $k_{x}$-partite graph for some $k_{x}$ in $\mathbb{N}$.
Suppose that

  1. 1.

For every $x$ in $V(G)$, $k_{x}\geq\frac{n+1}{2}$, and

  2. 2.

$G$ does not contain a cycle of length 4 with exactly 3 obstructions.

Then each vertex of $G$ is contained in an $H$-cycle of length 4.

######  Theorem 1.4.

Let $H$ be a graph possibly with loops and $G$ be an $H$-colored complete
graph of order $n$, with $n\geq 9$, such that for every $x$ in $V(G)$, $G_{x}$
is a complete $k_{x}$-partite graph for some $k_{x}$ in $\mathbb{N}$. Suppose
that

  1. 1.

For every $x$ in $V(G)$, $k_{x}\geq\frac{n+1}{2}$,

  2. 2.

$G$ does not contain a cycle of length 3 with exactly 2 obstructions, and

  3. 3.

$G$ does not contain a cycle of length 4 with exactly 3 obstructions.

Then each vertex of $G$ is contained in an $H$-cycle of length 4.

As a consequence of Theorems 1.3 and 1.4 we have the following corollary.

######  Corollary 1.1.

Let $H$ be a graph possibly with loops and $G$ be an $H$-colored complete
graph of order $n$, with $n\geq 4$, such that for every $x$ in $V(G)$, $G_{x}$
is a complete $k_{x}$-partite graph for some $k_{x}$ in $\mathbb{N}$. Suppose
that

  1. 1.

For every $x$ in $V(G)$, $k_{x}\geq\frac{n+1}{2}$,

  2. 2.

$G$ does not contain a cycle of length 3 with exactly 2 obstructions, and

  3. 3.

$G$ does not contain a cycle of length 4 with exactly 3 obstructions.

Then each vertex of $G$ is contained in an $H$-cycle of length 4.

Let $H$ be a graph possibly with loops and $G$ be an $H$-colored graph. We say
that $G$ is $H$-pancyclic iff it contains an $H$-cycle of length $l$ for each
$l$ in $\\{3,\cdots,n\\}$, and $G$ is said to be $H$-vertex pancyclic whenever
each vertex of $G$ is contained in an $H$-cycle of length $l$ for every $l$ in
$\\{3,\cdots,n\\}$.

The main contribution of this paper is to begin the study of $H$-vertex-
pancyclicity for $H$-colored graphs. Although we are considering small cycle
lengths in $H$-colored complete graphs, our investigations have underlined
that these results are not easy to proof. As a matter of fact, several authors
agree that, in the investigation of vertex-pancyclicity of a graph, the
consideration of small cycle lengths is the most difficult part (see [25]).
Moreover, these are the first essential steps in order to obtain a result
implying the $H$-vertex-pancyclicity in an $H$-colored graph.

This paper is organized as follows: in section 2, we show the basic concepts
and notation which will be useful in the developing of this work. In section
3, we exhibit some structural properties on the graph $G_{x}$, and we
introduce the $H$-dependency property in an $H$-colored graph, which will be
essential in order to prove the main results. In section 4, we prove the main
theorems, and we exhibit explicit examples showing that the hypotheses of the
first main theorem are tight. Finally, as a direct consequence of the main
results, we obtain some classical theorems about the existence of properly
colored cycles.

Given a digraph $D$ and a vertex $v$ in $V(D)$, we denote by $\delta^{+}(v)$
the out-degree of the vertex $v$, and by $\Delta^{+}(D)$ the maximum out-
degree of $D$.

We need the following result.

######  Proposition 1.1 ([4]).

If $T$ is a tournament of order $n$, with $n\geq 1$, then
$\Delta^{+}(T)\geq\frac{n-1}{2}$.

##  2 Terminology and Notation

Let $G$ be a graph. In the rest of paper we will denote by: $N_{G}(u)$ the
neighborhood and of $v$, $\delta_{G}(v)$ the degree of $v$, for $X\subseteq
V(G)$, $G[X]$ the subgraph of $G$ induced by $X$, $G-X$ the subgraph of $G$
induced by $V(G)-X$, and if $X=\\{a\\}$, we write $G-a$ instead of
$G-\\{a\\}$. If the graph $G$ is understood, we omit the subindex $G$.

A walk is a sequence $W=(v_{0},v_{1},\cdots,v_{k})$ such that $v_{i}v_{i+1}\in
E(G)$ for every $i$ in $\\{0,1,\cdots,k-1\\}$. The number $k$ is the length of
$W$, denoted by $\ell(W)$. If $v_{0}=v_{k}$, then we say that $W$ is a closed
walk. We say that the walk $W$ is a path iff $v_{i}\neq v_{j}$ for every
$\\{i,j\\}$ subset of $\\{0,1,\cdots,k\\}$. A closed walk
$(v_{0},v_{1},\cdots,v_{k},v_{0})$ is a cycle iff $k\geq 2$ and
$(v_{0},v_{1},\cdots,v_{k})$ is a path.

A subset $I$ of $V(G)$ is independent iff the subgraph $G[I]$ has no edges.
For a fixed positive integer $k$, we say that a graph $G$ is a $k$-partite
graph iff there exists a partition $\\{V_{1},\cdots,V_{k}\\}$ of $V(G)$ where
each $V_{i}$ is an independent set. Moreover, a $k$-partite graph with
$\\{V_{1},\cdots,V_{k}\\}$ a partition of $V(G)$ into independent sets, is
said to be a complete $k$-partite graph iff for every $x$ in $A_{i}$ and for
every $y$ in $A_{j}$, $x$ and $y$ are adjacent in $G$, for every $\\{i,j\\}$
subset of $\\{1,\cdots,k\\}$, with $i\neq j$.

##  3 Previous results

In order to make feasible the proof of the main theorems, we show some
structural properties on the graph $G_{x}$ and we introduce some extra
notation.

######  Observation 3.1.

Let $H$ be a graph possibly with loops, $G$ be an $H$-colored graph without
isolated vertices, and $D$ an induced (by $V(D)$) subgraph of $G$. If for
every $x$ in $V(G)$, $G_{x}$ is a complete $k_{x}$-partite graph for some
$k_{x}$ in $\mathbb{N}$, then for every $x$ in $V(D)$, $D_{x}$ is a complete
$l_{x}$-partite graph for some $l_{x}$ in $\mathbb{N}$. Moreover, if
$\\{P_{1}^{x},P_{2}^{x},\cdots,P_{k_{x}}^{x}\\}$ is the $k_{x}$-partition of
$V(G_{x})$ into independent sets, then $\\{P_{i}^{x}\cap
V(D_{x}):P_{i}^{x}\cap V(D_{x})\neq\emptyset,i\in\\{1,2,\cdots,k_{x}\\}\\}$ is
the $l_{x}$-partition of $V(D_{x})$ into independent sets.

######  Notation 3.1.

If $D$ is an induced subgraph of $G$ without isolated vertices, then for every
$x$ in $V(D)$ we write $l_{x}^{D}$ instead of $l_{x}$, where $l_{x}$ is the
one referred in Observation 3.1.

From now on, $H$ is a, possibly with loops, graph and $G$ is an $H$-colored
complete graph with $c:E(G)\longrightarrow V(H)$ a predetermined $H$-coloring
of $G$.

######  Notation 3.2.

Whenever $G_{x}$ is a complete $k_{x}$-partite graph for some $k_{x}$ in
$\mathbb{N}$, we will denote by
$\\{P_{1}^{x},P_{2}^{x},\cdots,P_{k_{x}}^{x}\\}$ the $k_{x}$-partition of
$V(G_{x})$ into independent sets.

Let $A$ be a subset of $V(G)$ and $v$ be a vertex in $V(G)-A$. We say that $A$
has the $H$-dependence property with respect to the vertex $v$ iff for every
$\\{a,a^{\prime}\\}$ subset of $A$, $a$ is an obstruction of the walk
$(v,a,a^{\prime})$, or $a^{\prime}$ is an obstruction of the walk
$(a,a^{\prime},v)$. The following lemma follows directly from this definition.

######  Lemma 3.1.

Let $A$ be a subset of $V(G)$, $A^{\prime}$ a subset of $A$ and $v\in V(G)-A$.
If $A$ has the $H$-dependence property with respect to the vertex $v$, then
$A^{\prime}$ has the $H$-dependence property with respect to the vertex $v$.

######  Proposition 3.1.

Suppose that for every $x$ in $V(G)$, $G_{x}$ is a complete $k_{x}$-partite
graph for some $k_{x}$ in $\mathbb{N}$. Let $A$ be a subset of $V(G)$ and $v$
be a vertex in $V(G)-A$. If $A$ has the $H$-dependence property with respect
to the vertex $v$, then there exists some vertex $a$ in $A$ such that

  1. 1.

$l_{a}^{D}\leq\frac{|A|+1}{2}$, where $D=G[A]$, and

  2. 2.

if $|A|\geq 2$, then $a$ is an obstruction of the walk $(v,a,a^{\prime})$ for
some $a^{\prime}$ in $N_{D}(a)$.

###### Proof.

(1)

Suppose that $|A|=m$ for some $m$ in $\mathbb{N}$, and give an orientation of
$E(D)$ as follows: for every $\\{x,y\\}$ subset of $A$, if $x$ is an
obstruction of the walk $(v,x,y)$, then orient the edge from $x$ to $y$. If
$x$ is an obstruction of $(v,x,y)$ and $y$ is an obstruction of the walk
$(v,y,x)$, then orient the edge $xy$ arbitrarily. This orientation of the
graph $D$ is well-defined since $A$ has the $H$-dependence property with
respect to the vertex $v$. Let $D^{\prime}$ be such orientation of the graph
$D$. Notice that $D^{\prime}$ is a tournament of order $m$, hence by
Proposition 1.1, $\Delta^{+}(D^{\prime})\geq\frac{m-1}{2}$, that is, there
exists a vertex $u$ in $A$ such that
$\delta^{+}(u)=\Delta^{+}(D^{\prime})\geq\frac{m-1}{2}$. Suppose that
$N^{+}_{{}_{D^{\prime}}}(u)=\\{x_{1},x_{2},\cdots,x_{s}\\}$, where
$s\geq\frac{m-1}{2}$. By the construction of the tournament $D^{\prime}$, we
have that for every $i$ in $\\{1,2,\cdots,s\\}$, $u$ is an obstruction of the
walk $(v,u,x_{i})$, which implies by Observation 1.1 that $ux_{i}$ and $uv$
are in the same set of the $k_{u}$-partition of $V(G_{u})$. Hence, by
Observation 3.1, $ux_{1},ux_{2},\cdots,ux_{s}$ are in the same set of the
$l_{u}^{D}$-partition of $V(D_{u})$, where $s\geq\frac{m-1}{2}$.
Finally, as $\delta_{{}_{D}}(u)=m-1$, and

$m-1-s+1\leq m-1-\frac{m-1}{2}+1=\frac{2m-m+1}{2}=\frac{m+1}{2},$

we have that there exists at most $\frac{m+1}{2}$ parts in the
$l_{u}^{D}$-partition of $V(D_{u})$. Therefore
$l_{u}^{D}\leq\frac{m+1}{2}=\frac{|A|+1}{2}$.

(2)

Let $A$ be a subset of $V(G)$ and $v$ be in $V(G)-A$. We want to prove that,
if $A$ has the $H$-dependence property with respect to the vertex $v$, then
there exists a vertex $a$ in $A$ such that $l_{a}^{D}\leq\frac{|A|+1}{2}$,
where $D=G[A]$, and moreover, if $|A|\geq 2$, then $a$ is an obstruction of
$(v,a,a^{\prime})$ for some $a^{\prime}$ in $N_{D}(a)$. We proceed by
induction on $|A|$, with $|A|\geq 2$.
First suppose that $|A|=2$, say $A=\\{x,y\\}$. Since $A$ has the
$H$-dependence property with respect to the vertex $v$, hence $x$ is an
obstruction of the walk $(v,x,y)$ or $y$ is an obstruction of the walk
$(v,y,x)$. Suppose without loss of generality that $x$ is an obstruction of
the walk $(v,x,y)$, thus $x$ is the desired vertex, since
$l_{x}^{D}=1\leq\frac{3}{2}=\frac{|A|+1}{2}$, where $D=G[A]$.

Now suppose that, if $A^{\prime}$ is a subset of $V(G)$ and $v$ is a vertex in
$V(G)-A^{\prime}$, such that $A^{\prime}$ has the $H$-dependency property with
respect to the vertex $v$ and $|A^{\prime}|\leq m-1$, then there exists a
vertex $a^{\prime}$ in $A^{\prime}$ such that
$l_{a^{\prime}}^{D^{\prime}}\leq\frac{|A^{\prime}|+1}{2}$, where
$D^{\prime}=G[A^{\prime}]$, and moreover, if $|A^{\prime}|\geq 2$, then
$a^{\prime}$ is an obstruction of the walk $(v,a^{\prime},b)$ for some $b$ in
$N_{D^{\prime}}(a^{\prime})$.

Now take a set $A$ having the $H$-dependency property with respect to the
vertex $v$ and $|A|=m$, with $m>2$. By the proof of the part (1), we have that
there exists a vertex $a$ in $A$ such that $l_{a}^{D}\leq\frac{|A|+1}{2}$,
where $D=G[A]$. If $a$ is an obstruction of the walk $(v,a,a^{\prime})$ for
some $a^{\prime}$ in $N_{D}(a)$, then $a$ is the desired vertex. Suppose now
that $a$ is not an obstruction of the walk $(v,a,a^{\prime})$ for every
$a^{\prime}$ in $N_{D}(a)$.
Let $A^{\prime}=A\setminus\\{a\\}$ be. By Lemma 3.1, $A^{\prime}$ has the
$H$-dependency property with respect to the vertex $v$. Moreover, given that
$|A^{\prime}|=m-1\geq 2$, the inductive hypothesis implies that there exists a
vertex $a^{\prime}$ in $A^{\prime}$ such that
$l_{a^{\prime}}^{D^{\prime}}\leq\frac{|A^{\prime}|+1}{2}=\frac{m}{2}$, where
$D^{\prime}=G[A^{\prime}]$ and such that $a^{\prime}$ is an obstruction of the
walk $(v,a^{\prime},b)$ for some $b$ in $N_{D^{\prime}}(a^{\prime})$. Since
$a^{\prime}$ is an obstruction of the walk $(v,a^{\prime},b)$, we have by
Observation 1.1 that $va^{\prime}$ and $a^{\prime}b$ are in the same part of
the $k_{a^{\prime}}$-partition of $V(G_{a^{\prime}})$. Now, as $A$ has the
$H$-dependency property with respect to the vertex $v$ and
$\\{a,a^{\prime}\\}$ is a subset of $A$, it follows that $a$ is an obstruction
of $(v,a,a^{\prime})$ or $a^{\prime}$ is an obstruction of $(a,a^{\prime},v)$.
However, by our assumption about $a$, we have that $a^{\prime}$ is an
obstruction of the walk $(a,a^{\prime},v)$, which implies by Observation 1.1
that $aa^{\prime}$ and $va^{\prime}$ are in the same part of the
$k_{a^{\prime}}$-partition of $V(G_{a^{\prime}})$. Thus, $aa^{\prime}$ and
$a^{\prime}b$ are in the same part of the $k_{a^{\prime}}$-partition of
$V(G_{a^{\prime}})$, in particular, by Observation 3.1 we have that
$aa^{\prime}$ and $a^{\prime}b$ are in the same part of the
$l_{a^{\prime}}^{D}$-partition of $V(D_{a^{\prime}})$. In addition, we have
that $l_{a^{\prime}}^{D^{\prime}}\leq\frac{|A^{\prime}|+1}{2}=\frac{m}{2}$, so
$l_{a^{\prime}}^{D}=l_{a^{\prime}}^{D^{\prime}}\leq\frac{m}{2}\leq\frac{m+1}{2}=\frac{|A|+1}{2}$,
and therefore $a^{\prime}$ is the desired vertex.

∎

##  4 Main Results

Proof of Theorem 1.2.

Proceeding by contradiction, suppose that there exists a vertex $v$ in $V(G)$
such that $v$ is not contained in an $H$-cycle of length 3 in $G$. As $G_{v}$
is a complete $k_{v}$-partite graph for some $k_{v}$ in $\mathbb{N}$, by
Notation 3.2, $\\{P_{1}^{v},P_{2}^{v},\cdots,P_{k_{v}}^{v}\\}$ is the
$k_{v}$-partition of $V(G_{v})$ into independent sets. Now, for every $i$ in
$\\{1,2,\cdots,k_{v}\\}$, we define $N_{i}^{v}=\\{u\in N_{G}(v):uv\in
P_{i}^{v}\\}$.

######  Observation 4.1.

For every $\\{i,j\\}$ subset of $\\{1,2,\cdots,k_{v}\\}$, for each $x$ in
$N_{i}^{v}$ and for any $y$ in $N_{j}^{v}$, we have that:

(1)

$v$ is not an obstruction of the cycle $(v,x,y,v)$, and

(2)

$x$ is an obstruction of the walk $(v,x,y)$ or $y$ is an obstruction of the
walk $(v,y,x)$.

###### Proof.

(1)

By construction of the sets $N_{i}^{v}$ and $N_{j}^{v}$, it follows that $vx$
and $vy$ are in different parts of the $k_{v}$-partition of $V(G_{v})$, which
implies by Observation 1.1 that $v$ is not an obstruction of the path
$(x,v,y)$, that is, $v$ is not an obstruction of the cycle $(v,x,y,v)$.

(2)

Proceeding by contradiction, it follows directly from Observations 1.2 and
4.1(1) that $(v,x,y,v)$ is an $H$-cycle of length 3 in $G$ containing $v$,
which is impossible by our assumption.

∎

Renaming (if necessary) we can assume that
$|N_{1}^{v}|=|N_{2}^{v}|=\cdots=|N_{r}^{v}|=1$ and
$2\leq|N_{r+1}^{v}|\leq\cdots\leq|N_{k_{v}}^{v}|$ for some nonnegative integer
$r$.

Claim 1. $r\geq 2$.

###### Proof.

Otherwise, if $r\leq 1$, then

$n-1=|N_{1}^{v}|+\cdots+|N_{r}^{v}|+|N_{r+1}^{v}|+\cdots+|N_{k_{v}}^{v}|\geq
r+2(k_{v}-r)=2k_{v}-r\geq 2k_{v}-1$

which implies that $k_{v}\leq\frac{n}{2}$. This is impossible since by
hypothesis $k_{v}\geq\frac{n+1}{2}$. ∎

Consider $D=G[N_{1}^{v}\cup N_{2}^{v}\cup\cdots\cup N_{r}^{v}]$,
$D^{\prime}=G[N_{r+1}^{v}\cup\cdots\cup N_{k_{v}}^{v}]$ and $s=k_{v}-r$.

Given that $|N_{1}^{v}|=|N_{2}^{v}|=\cdots=|N_{r}^{v}|=1$, it follows directly
from Observation 4.1(2) the following claim.

Claim 2. $V(D)$ has the $H$-dependency property with respect to the vertex
$v$.

Now the $H$-dependency property of $V(D)$ (with respect to the vertex $v$) and
Proposition 3.1, imply that there exists a vertex $a$ in $V(D)$ such that
$l_{a}^{D}\leq\frac{|V(D)|+1}{2}=\frac{r+1}{2}$, and moreover, since $r\geq
2$, it follows that $a$ is an obstruction of the walk $(v,a,a^{\prime})$ for
some $a^{\prime}$ in $N_{D}(a)$. By construction, we know that
$N_{i}^{v}=\\{a\\}$ for some $i$ in $\\{1,2,\cdots,r\\}$.

Claim 3. $k_{a}\leq l_{a}^{D}+s$ (see Notation 3.1).

###### Proof.

Recall that $G_{a}$ is a complete $k_{a}$-partite graph for some $k_{a}$ in
$\mathbb{N}$, and $\mathcal{P}=\\{P_{1}^{a},P_{2}^{a},\cdots,P_{k_{a}}^{a}\\}$
is the $k_{a}$-partition of $V(G_{a})$ into independent sets. By the
Observation 3.1 and given that $D$ is an induced subgraph of $G$, it follows
that $\mathcal{Q}=\\{P_{i}^{a}\cap V(D_{a}):P_{i}^{a}\cap
V(D_{a})\neq\emptyset\,i\in\\{1,2,\cdots,k_{a}\\}\\}$ is the
$l_{a}^{D}$-partition of $V(D_{a})$ into independent sets, where
$V(D_{a})=\\{e\in E(D):e\ \mbox{is incident with}\ a\\}$. Renaming, if
necessary, we say that $\mathcal{Q}=\\{P_{1}^{a}\cap V(D_{a}),P_{2}^{a}\cap
V(D_{a}),\cdots,P_{l_{a}^{D}}^{a}\cap V(D_{a})\\}$ is the
$l_{a}^{D}$-partition of $V(D_{a})$ into nonempty independent sets.
Now, in order to prove this upper bound of $k_{a}=k_{a}^{G}$ in terms of
$l_{a}^{D}$, consider the edges incident with $a$ that are not vertices in
$D_{a}$, that is, $V(G_{a})-V(D_{a})=\\{va\\}\cup\\{az:z\in
N_{i}^{v},i\in\\{r+1,\cdots,k_{v}\\}\\}$. Since $a$ is an obstruction of the
walk $(v,a,a^{\prime})$ for some $a^{\prime}$ in $N_{D}(a)$, thus $va$ and
$aa^{\prime}$ are in the same part of the $k_{a}$-partition of $V(G_{a})$ by
the Observation 1.1. Moreover, as $aa^{\prime}$ is in $V(D_{a})$, it follows
that there exists $\alpha$ in $\\{1,2,\cdots,l_{a}^{D}\\}$ such that
$aa^{\prime}\in P_{\alpha}^{a}$, so $\\{aa^{\prime},va\\}\subseteq
P_{\alpha}^{a}$, where $P_{\alpha}^{a}$ is already considered in the first
$l_{a}^{D}$ parts of $\mathcal{P}$. Hence, when we consider the edge $va$, we
add no extra part in the $k_{a}$-partition of $V(G_{a})$ with respect to the
number of parts of the $l_{a}^{D}$-partition of $V(D_{a})$.
Next, we will prove that for every $j$ in $\\{r+1,\cdots,k_{v}\\}$, we add at
most one part in $\mathcal{P}$ with respect to the number of parts in
$\mathcal{Q}$.

Let $j$ be an element of $\\{r+1,\cdots,k_{v}\\}$ and $x$ be a vertex in
$N_{j}^{v}$.

Case 1.

$a$ is an obstruction of the walk $(v,a,x)$.
If $a$ is an obstruction of the walk $(v,a,x)$, then by Observation 1.1, $va$
and $ax$ are in the same set of the $k_{a}$-partition of $V(G_{a})$, and given
that $va$ is in $P_{\alpha}^{a}$, thus $ax\in P_{\alpha}^{a}$, where
$P_{\alpha}^{a}$ is already counted in the first $l_{a}^{D}$ parts of
$\mathcal{P}$. Therefore, in this case we add no extra part in $\mathcal{P}$
with respect to the number of parts in $\mathcal{Q}$.

Case 2.

$a$ is not an obstruction of the walk $(v,a,x)$.
If $a$ is not an obstruction of the walk $(v,a,x)$, then $x$ is an obstruction
of the walk $(v,x,a)$, by Observation 4.1. Moreover, if $a$ is not an
obstruction of the walk $(v,a,x)$, then by Observation 1.1, $va$ and $ax$ are
in different sets of the $k_{a}$-partition of $V(G_{a})$, with $va\in
P_{\alpha}^{a}$. We can assume that $ax$ is in $P_{\beta}^{a}$ for some
$\beta$ in $\\{l_{a}^{D}+1,\cdots,k_{a}\\}$, otherwise, when we consider the
edge $ax$, it is already counted in the first $l_{a}^{D}$ parts of
$\mathcal{P}$.

Claim 3.1. For every $y$ in $N_{j}^{v}$, $ay\in P_{\alpha}^{a}$ or $ay\in
P_{\beta}^{a}$.

###### Proof.

Let $y$ be in $N_{j}^{v}$, with $y\neq x$.

Subcase 2.1

$a$ is an obstruction of the walk $(v,a,y)$.
Proceeding in a similar way as in Case 1, we can prove that $va$ and $ay$ are
in the same set of the $k_{a}$-partition of $V(G_{a})$, and given that $va$ is
in $P_{\alpha}^{a}$, we have that $ay\in P_{\alpha}^{a}$, as desired.

Subase 2.2

$a$ is not an obstruction of the walk $(v,a,y)$.
Since $a$ is not an obstruction of the walk $(v,a,y)$, it follows that $y$ is
an obstruction of the walk $(v,y,a)$ by Observation 4.1, and recall that $x$
is an obstruction of the walk $(v,x,a)$. On the other hand, given that
$\\{vx,vy\\}$ is a subset of $N_{j}^{v}$, we have by construction of the set
$N_{j}^{v}$ that $vx$ and $vy$ are in the same part of the $k_{v}$-partition
of $V(G_{v})$, which implies that $v$ is an obstruction of the walk $(x,v,y)$,
by Observation 1.1. Hence, $y$, $x$ and $v$ are obstructions of the cycle
$C=(v,x,a,y,v)$, with $\ell(C)=4$, so it follows by the hypothesis 2 of
Theorem 1.2 that $a$ is also an obstruction of the cycle $C$. Since $a$ is an
obstruction of the cycle $C$, we have by Observation 1.1 that $ay$ and $ax$
are in the same part of the $k_{a}$-partition of $V(G_{a})$, and given that
$ax\in P_{\beta}^{a}$, thus $ay\in P_{\beta}^{a}$, as desired.

So Claim 3.1 is proved. ∎

Since for every $y$ in $N_{j}^{v}$, $ay\in P_{\alpha}^{a}$ with $\alpha$ in
$\\{1,2,\cdots,l_{a}^{D}\\}$, or $ay\in P_{\beta}^{a}$ with $\beta$ in
$\\{l_{a}^{D}+1,\cdots,k_{a}\\}$, we have that for every $j$ in
$\\{r+1,\cdots,k_{v}\\}$ we add at most one part in $\mathcal{P}$ with respect
to the number of parts in $\mathcal{Q}$ (namely $P_{\beta}^{a}$), where
$|\mathcal{P}|=|\\{P_{1}^{a},P_{2}^{a},\cdots,P_{k_{a}}^{a}\\}|=k_{a}$,
$|\mathcal{Q}|=|\\{P_{1}^{a}\cap V(D_{a}),P_{2}^{a}\cap
V(D_{a}),\cdots,P_{l_{a}^{D}}^{a}\cap V(D_{a})\\}|=l_{a}^{D}$ and $s=k_{v}-r$.

Therefore $k_{a}\leq l_{a}^{D}+s$. ∎

Now, $|V(D^{\prime})|=|N_{r+1}^{v}|+\cdots+|N_{k_{v}}^{v}|\geq 2(k_{v}-r)=2s$,
so $s\leq\frac{|V(D^{\prime})|}{2}$. Hence,

$k_{a}\leq
l_{a}^{D}+s\leq\frac{r+1}{2}+\frac{|V(D^{\prime})|}{2}=\frac{(|V(D)|+1)+|V(D^{\prime})|}{2}=\frac{n}{2},$

which is impossible since the hypothesis 1 of Theorem 1.2 establishes that
$k_{a}\geq\frac{n+1}{2}$.

Therefore $v$ is contained in an $H$-cycle of length 3 in $G$. $\square$

The two following observations show examples of $H$-colored complete graphs,
showing that the hypotheses of Theorem 1.2 are tight.

######  Observation 4.2.

The hypothesis 1 of Theorem 1.2 cannot be dropped. Notice that in the
$H$-colored complete graph $G$ of the Figure 1, we have that for every $x$ in
$V(G)$, $G_{x}$ is a complete 2-partite graph, where $2<\frac{|V(G)|+1}{2}$,
thus the hypothesis 1 of Theorem 1.2 is not fulfilled. Also, the cycle
$(a,b,c,d,a)$ has no obstructions, the cycle $(a,b,d,c,a)$ has 2 obstructions
(namely $a$ and $c$), and the cycle $(a,d,b,c,a)$ has 2 obstructions (namely
$b$ and $d$), therefore the hypothesis 2 of Theorem 1.2 is satisfied.
Nevertheless, the vertex $a$ in $V(G)$ is not in an $H$-cycle of length 3 in
$G$, since $a$ is an obstruction of the cycle $(a,b,c,a)$, $c$ is an
obstruction of the cycle $(a,c,d,a)$, and $d$ is an obstruction of the cycle
$(a,b,d,a)$.

Figure 1: The hypothesis 1 of Theorem 1.2 cannot be dropped.

######  Observation 4.3.

The hypothesis 2 of Theorem 1.2 cannot be dropped as the $H$-colored complete
graph in the Figure 2 shows. Notice that for every $a$ in $V(G)$, $G_{a}$ is a
complete 4-partite graph, that is, the hypothesis 1 of Theorem 1.2 is
fulfilled; and the vertex $r$ in $V(G)$ is not contained in an $H$-cycle of
length 3, since each one of the 15 cycles of length 3 containing $r$ has the
indicated obstruction: $(r,x,w,r)$, obstruction in vertex $w$; $(r,x,v,r)$,
obstruction in vertex $x$; $(r,x,u,r)$, obstruction in vertex $x$;
$(r,x,t,r)$, obstruction in vertex $t$; $(r,x,s,r)$, obstruction in vertex
$s$; $(r,w,v,r)$, obstruction in vertex $w$; $(r,w,u,r)$, obstruction in
vertex $u$; $(r,w,t,r)$, obstruction in vertex $t$; $(r,w,s,r)$, obstruction
in vertex $s$; $(r,w,u,r)$, obstruction in vertex $u$; $(r,v,u,r)$,
obstruction in vertex $u$; $(r,v,t,r)$, obstruction in vertex $v$;
$(r,v,s,r)$, obstruction in vertex $v$; $(r,u,t,r)$ obstruction in vertex $r$;
$(r,u,s,r)$ obstruction in vertex $r$; $(r,t,s,r)$, obstruction in vertex $r$.
However, the hypothesis 2 of Theorem 1.2 is not satisfied because
$(r,s,x,t,r)$ is a cycle of length 4 in $G$, with exactly 3 obstructions
(namely $r,s$ and $t$).

Figure 2: The hypothesis 2 of Theorem 1.2 cannot be dropped.

Proof of Theorem 1.3

If $n=4$, then for every $x$ in $V(G)$ we have that $k_{x}\geq\frac{5}{2}$,
and $k_{x}\leq\delta(x)=3$, so $k_{x}=3$. And hence, for every two edges $a$
and $b$ incident with $x$, we have that $a$ and $b$ are in different parts of
the $k_{x}$-partition of $V(G_{x})$.

If $n=5$, then for every $x$ in $V(G)$ we have that $k_{x}\geq 3$, and
$k_{x}\leq\delta(x)=4$, so $k_{x}=3$ or $k_{x}=4$. Then, for every vertex $x$
in $V(G)$, at most 2 edges incident with $x$ are in the same part of the
$k_{x}$-partition of $V(G_{x})$. As a consequence, for each vertex $x$ in
$V(G)$, we know that there are at most two cycles of length 4 in $G$ passing
through $x$ that are not $H$-cycles. And we are done.

The case $n=6$, can be easily carried as a consequence of the case $n=5$,
because for each $x$ in $V(G)$, $G-x$ satisfies the hypotheses of Theorem 1.3.

If $n=7$, then for every $x$ in $V(G)$, we have that $k_{x}\geq 4$. Proceeding
by contradiction, suppose there exists a vertex $v$ in $V(G)$ such that $v$ is
not contained in an $H$-cycle of length 4 in $G$. It follows by Theorem 1.2
that there exists an $H$-cycle of length 3 containing $v$, say $(v,x,y,v)$.
Thus, by Observation 1.1, we have that $yv$ and $xy$ are in different parts of
the $k_{v}$-partition of $V(G_{v})$, $vx$ and $yx$ are in different parts of
the $k_{x}$-partition of $V(G_{x})$, and $vy$ and $xy$ are in different parts
of the $k_{y}$-partition of $V(G_{y})$. Without loss of generality, suppose
that $xv\in P_{1}^{v}$ and $yv\in P_{2}^{v}$, $vx\in P_{1}^{x}$ and $yx\in
P_{2}^{x}$, and $vy\in P_{1}^{y}$ and $xy\in P_{2}^{y}$. As for every $a$ in
$V(G)$, $k_{a}\geq 4$, we have that for every $t$ in $\\{v,x,y\\}$, there
exists at least two different parts of the $k_{t}$-partition of $V(G_{t})$,
other than the two already mentioned. Since there are only 4 vertices in
$V(G)-\\{v,x,y\\}$, it follows that there is a vertex $w$ such that, without
loss of generality, $wx\in P_{3}^{x}$ and $wy\in P_{3}^{y}$, and suppose that
$xw\in P_{1}^{w}$.
Claim 1. $\\{vw,xw,yw\\}$ is a subset of $P_{1}^{w}$, and for every $t$ in
$V(G)-\\{v,w,x,y\\}$, $tw\notin P_{1}^{w}$.

###### Proof.

First we prove that $yw$ is in $P_{1}^{w}$. Proceeding by contradiction,
suppose that $yw\notin P_{1}^{w}$, then by Observation 1.2, $(v,y,w,x,v)$ is
an $H$-cycle of length 4 in $G$ containing $v$ (since $vy\in P_{2}^{v}\cap
P_{1}^{y}$, $yw\in P_{3}^{y}-P_{1}^{w}$, $wx\in P_{3}^{y}\cap P_{1}^{w}$ and
$xv\in P_{1}^{v}\cap P_{1}^{x}$), which is impossible by our assumption.
Therefore $yw\in P_{1}^{w}$.
Now, we prove that $vw\in P_{1}^{w}$. Proceeding by contradiction, suppose
that $vw\notin P_{1}^{w}$.
When $wv\in P_{1}^{v}$, we have that by Observation 1.2, $(y,v,w,x,y)$ is an
$H$-cycle of length 4 in $G$ containing $v$ (as $yv\in P_{2}^{v}\cap
P_{1}^{y}$, $vw\in P_{1}^{v}-P_{1}^{w}$, $wx\in P_{3}^{x}\cap P_{1}^{w}$ and
$xy\in P_{2}^{y}\cap P_{2}^{x}$), a contradiction.
When $wv\notin P_{1}^{v}$, the previous observation implies that $(y,w,v,x,y)$
is an $H$-cycle of length 4 in $G$ containing $v$ (notice that $yw\in
P_{3}^{y}\cap P_{1}^{w}$, $wv\notin P_{1}^{w}\cup P_{1}^{v}$, $vx\in
P_{1}^{v}\cap P_{1}^{x}$ and $xy\in P_{2}^{y}\cap P_{2}^{x}$), which is
impossible.
We conclude that $vw\in P_{1}^{w}$.
Therefore $\\{vw,xw,yw\\}\subseteq P_{1}^{w}$, and moreover, as $G_{w}$ is a
complete $k_{w}$-partite graph, with $k_{w}\geq 4$, it follows that for each
$t$ in $V(G)-\\{v,w,x,y\\}$, $tw\notin P_{1}^{w}$. ∎

To conclude the proof when $n=7$, we consider the two following cases. Both
cases lead us to a contradiction.

Case 1.

$wv\notin P_{1}^{v}\cup P_{2}^{v}$.
Without loss of generality, suppose that $wv\in P_{3}^{v}$. Given that $G_{v}$
is a complete $k_{v}$-partite graph, with $k_{v}\geq 4$, consider $u$ in
$V(G)-\\{v,w,x,y\\}$ such that $vu\in P_{4}^{v}$; and since $u\in
V(G)-\\{v,x,y,w\\}$, it follows by Claim 1 that $uw\notin P_{1}^{w}$. Suppose
that $wu\in P_{1}^{u}$.
Claim 2. $\\{vu,wu,xu,yu\\}\subseteq P_{1}^{u}$.

###### Proof.

As $wu\in P_{1}^{u}$, there remains to prove that $\\{vu,xu,yu\\}\subseteq
P_{1}^{u}$.
First we prove that $vu\in P_{1}^{u}$. Proceeding by contradiction, suppose
that $vu\notin P_{1}^{u}$, hence by Observation 1.2, $(x,v,u,w,x)$ is an
$H$-cycle of length 4 in $G$ containing $v$ (since $xv\in P_{1}^{v}\cap
P_{1}^{x}$, $vu\in P_{4}^{v}-P_{1}^{u}$, $uw\in P_{1}^{u}-P_{1}^{w}$ and
$wx\in P_{3}^{x}\cap P_{1}^{w}$), which is impossible by our assumption.
Therefore $vu\in P_{1}^{u}$.

Next, we prove that $xu\in P_{1}^{u}$. Proceeding by contradiction, suppose
that $xu\notin P_{1}^{u}$.
When $ux\in P_{2}^{x}$, Observation 1.2, $wv\in P_{1}^{w}\cap P_{3}^{v}$,
$vx\in P_{1}^{v}\cap P_{1}^{x}$, $xu\in P_{2}^{x}-P_{1}^{u}$ and $uw\in
P_{1}^{u}-P_{1}^{w}$ imply that $(w,v,x,u,w)$ is an $H$-cycle of length 4 in
$G$ containing $v$, which is impossible.
When $ux\notin P_{2}^{x}$, the previous argument implies that $(v,y,x,u,v)$ is
an $H$-cycle of length 4 in $G$ containing $v$ (since $vy\in P_{2}^{v}\cap
P_{1}^{y}$, $yx\in P_{2}^{y}\cap P_{2}^{x}$, $xu\notin P_{2}^{x}\cup
P_{1}^{u}$ and $uv\in P_{1}^{u}\cap P_{4}^{v}$), a contradiction.
We conclude that $xu\in P_{1}^{u}$.

Now, we prove that $yu\in P_{1}^{u}$. Proceeding by contradiction, suppose
that $yu\notin P_{1}^{u}$.
When $uy\in P_{2}^{y}$, Observation 1.2, $wv\in P_{1}^{w}\cap P_{3}^{v}$,
$vy\in P_{2}^{v}\cap P_{1}^{y}$, $yu\in P_{2}^{y}-P_{1}^{u}$ and $uw\in
P_{1}^{u}-P_{1}^{w}$ imply that $(w,v,y,u,w)$ is an $H$-cycle of length 4 in
$G$ containing $v$, which is impossible.
When $uy\notin P_{2}^{y}$, it follows from the previous observation that
$(v,x,y,u,v)$ is an $H$-cycle of length 4 in $G$ containing $v$ (as $vx\in
P_{1}^{v}\cap P_{1}^{x}$, $xy\in P_{2}^{y}\cap P_{2}^{x}$, $yu\notin
P_{2}^{y}\cup P_{1}^{u}$ and $uv\in P_{1}^{u}\cap P_{4}^{v}$), a
contradiction.
We conclude that $yu\in P_{1}^{u}$.

This concludes the proof of Claim 2. Hence, $\\{vu,wu,xu,yu\\}\subseteq
P_{1}^{u}$. ∎

Finally, as $\\{vu,wu,xu,yu\\}$ is a subset of $P_{1}^{u}$ and
$\delta_{G}(u)=6$, we have that $k_{u}\leq 3$, which is impossible since by
hypothesis $k_{u}\geq 4$.

Case 2.

$wv\in P_{1}^{v}\cup P_{2}^{v}$.
By symmetry, suppose without loss of generality that $wv\in P_{1}^{v}$, and
since $G_{v}$ is a complete $k_{v}$-partite graph, with $k_{v}\geq 4$, we can
consider a subset $\\{u,s\\}$ of $V(G)-\\{v,w,x,y\\}$ such that $vu\in
P_{3}^{v}$ and $vs\in P_{4}^{v}$. Given that $\\{u,s\\}$ is a subset of
$V(G)-\\{v,x,y,w\\}$, it follows from Claim 1 that $uw\notin P_{1}^{w}$ and
$sw\notin P_{1}^{w}$. Suppose without loss of generality that $wu\in
P_{1}^{u}$ and $ws\in P_{1}^{s}$.
Claim 3. $\\{vu,wu,yu\\}\subseteq P_{1}^{u}$.

###### Proof.

Since $wu\in P_{1}^{u}$, it suffices to prove that $\\{vu,yu\\}\subseteq
P_{1}^{u}$.
First, we prove that $vu\in P_{1}^{u}$. Proceeding by contradiction, suppose
that $vu\notin P_{1}^{u}$, thus by Observation 1.2 and given that $yv\in
P_{2}^{v}\cap P_{1}^{y}$, $vu\in P_{3}^{v}-P_{1}^{u}$, $uw\in
P_{1}^{u}-P_{1}^{w}$ y $wy\in P_{1}^{w}\cap P_{3}^{y}$, we have that
$(y,v,u,w,y)$ is an $H$-cycle of length 4 in $G$ containing $v$, which is
impossible. Therefore $vu\in P_{1}^{u}$.

Now, we prove that $yu\in P_{1}^{u}$. Proceeding by contradiction, suppose
that $yu\notin P_{1}^{u}$.
When $uy\in P_{2}^{y}$, Observation 1.2, $vy\in P_{2}^{v}\cap P_{1}^{y}$,
$yu\in P_{2}^{y}-P_{1}^{u}$, $uw\in P_{1}^{u}-P_{1}^{w}$ and $wv\in
P_{1}^{v}\cap P_{1}^{w}$ imply that $(v,y,u,w,v)$ is an $H$-cycle of length 4
in $G$ containing $v$, a contradiction.
When $uy\notin P_{2}^{y}$, we have from the previous observation that
$(v,u,y,x,v)$ is an $H$-cycle of length 4 in $G$ containing $v$ (as $vu\in
P_{1}^{u}\cap P_{3}^{v}$, $uy\notin P_{1}^{u}\cup P_{2}^{y}$, $yx\in
P_{2}^{y}\cap P_{2}^{x}$ and $xv\in P_{1}^{v}\cap P_{1}^{x}$), which is
impossible.
We conclude that $xu\in P_{1}^{u}$. ∎

Proceeding in a very similar way to the proof of Claim 3 (taking $s$ instead
of $u$), we can prove that:

Claim 4. $\\{vs,ws,ys\\}\subseteq P_{1}^{s}$.

Claim 5. $us\in P_{1}^{u}$ or $us\in P_{1}^{s}$.

###### Proof.

Otherwise, if $us\notin P_{1}^{u}$ and $us\notin P_{1}^{s}$, then by
Observation 1.2 and given that $wu\in P_{1}^{u}-P_{1}^{w}$, $us\notin
P_{1}^{u}\cup P_{1}^{s}$, $sv\in P_{1}^{s}\cap P_{4}^{v}$ and $vw\in
P_{1}^{v}\cap P_{1}^{w}$, we have that $(w,u,s,v,w)$ is an $H$-cycle in $G$ of
length 4 containing $v$, which is impossible. ∎

By Claim 5, we have that $us\in P_{1}^{u}$ or $us\in P_{1}^{s}$.
When $us\in P_{1}^{u}$, we have by Claim 3 that $\\{vu,wu,xu,su\\}\subseteq
P_{1}^{u}$. Moreover, $\delta_{G}(u)=6$, so $k_{u}\leq 3$, which is
impossible.
When $us\in P_{1}^{s}$, Claim 4 implies that $\\{vs,ws,xs,us\\}\subseteq
P_{1}^{s}$. Since $\delta_{G}(s)=6$, it follows that $k_{s}\leq 3$, a
contradiction.

Therefore every vertex in $G$ is contained in an $H$-cycle of length 4,
whenever $|V(G)|=7$.

The case $n=8$, can be easily carried as a consequence of the case $n=7$,
since for each $x$ in $V(G)$, $G-x$ satisfies the hypotheses of Theorem 1.3.

This concludes the proof of Theorem 1.3. $\square$

Proof of Theorem 1.4

Let $G$ and $H$ be graphs as in the hypotheses, thus for every $x$ en $V(G)$,
$k_{x}\geq 5$. Proceeding by contradiction, suppose that there exists a vertex
$v$ in $V(G)$ such that $v$ is not contained in an $H$-cycle of length 4.
It follows by Theorem 1.2 that there exists an $H$-cycle of length 3
containing $v$, say $T=(u,v,w,u)$. By Observation 1.1, we have that $uv$ and
$vw$ are in different parts of the $k_{v}$-partition of $V(G_{v})$, $vw$ and
$wu$ are in different parts of the $k_{w}$-partition of $V(G_{w})$, and $wu$
and $uv$ are in different part of the $k_{u}$-partition of $V(G_{u})$. Without
loss of generality, suppose that $uv\in P_{1}^{v}$ and $vw\in P_{2}^{v}$,
$vw\in P_{2}^{w}$ and $wu\in P_{1}^{w}$, and $wu\in P_{2}^{u}$ and $uv\in
P_{1}^{u}$.

The proof of Theorem 1.4 is divided into two cases, depending on whether there
exists a vertex $x$ fulfilling certain properties or not. In each case, a
series of claims is proven, which will lead us to a contradiction.

Case 1. There exists a vertex $x$ in $V(G)-\\{u,v,w\\}$ such that

  * •

$xu\in P_{2}^{u}$, $xw\in P_{1}^{w}$,

  * •

$ux$ and $wx$ are in the same part of the $k_{x}$-partition of $V(G_{x})$,

  * •

$vx$ and $ux$ are in different part of the $k_{x}$-partition of $V(G_{x})$,

  * •

$xv\notin P_{1}^{v}\cup P_{2}^{v}$.

Suppose without loss of generality that $\\{ux,wx\\}\subseteq P_{1}^{x}$,
$vx\in P_{2}^{x}$ and $xv\in P_{3}^{v}$.

Claim 1. For every $y$ in $V(G)-\\{u,v,w,x\\}$, if $yw\notin P_{1}^{w}\cup
P_{2}^{w}$, then

(1) $uy$, $vy$, $wy$ and $xy$ are in the same part of the $k_{y}$-partition of
$V(G_{y})$,

(2) $uy\notin P_{2}^{u}$, $xy\notin P_{1}^{x}$, and $vy\notin P_{2}^{v}$.

###### Proof.

Let $y$ be a vertex in $V(G)-\\{u,v,w,x\\}$ such that $yw\notin P_{1}^{w}\cup
P_{2}^{w}$. Suppose that $wy\in P_{1}^{y}$, thus the item (1) can be rewritten
as follows: $\\{uy,vy,wy,xy\\}\subseteq P_{1}^{y}$.

First, proceeding by contradiction, we prove that $vy\in P_{1}^{y}$.
If $vy\in P_{1}^{v}$, then by Observation 1.2 and given that $wx\in
P_{1}^{w}\cap P_{1}^{x}$, $xv\in P_{2}^{x}\cap P_{3}^{v}$, $vy\in
P_{1}^{v}-P_{1}^{y}$ and $yw\in P_{1}^{y}-P_{1}^{w}$, we have that
$(w,x,v,y,w)$ is an $H$-cycle of length 4 in $G$ containing $v$. A
contradiction.
If $vy\notin P_{1}^{v}$, then by Observation 1.2 with $wu\in P_{1}^{w}\cap
P_{2}^{u}$, $uv\in P_{1}^{v}\cap P_{1}^{u}$, $vy\notin P_{1}^{v}\cup
P_{1}^{y}$ and $yw\in P_{1}^{y}-P_{1}^{w}$, we have that $(w,u,v,y,w)$ is an
$H$-cycle of length 4 in $G$ containing $v$, which is impossible.
We conclude that $vy\in P_{1}^{y}$.

Again, proceeding by contradiction, we will prove that $vy\notin P_{2}^{v}$.
It follows from Observation 1.1 that $v$ is an obstruction of the cycle
$C=(y,v,w,y)$, since $vw\in P_{2}^{v}$. By the same observation, we have that
$y$ is an obstruction of the cycle $C$ (as $\\{vy,wy\\}\subseteq P_{1}^{y}$),
and $w$ is not an obstruction of the cycle $C$ (recall that $vw\in P_{2}^{w}$
and $yw\notin P_{2}^{w}$). Thus, the cycle $C$ has exactly 2 obstructions
(namely $v$ and $y$), with $\ell(C)=3$, which is impossible because of the
hypothesis 3 of Theorem 1.4. Therefore $vy\notin P_{2}^{v}$.

Proceeding by contradiction, we will prove that $xy\in P_{1}^{y}$.
Notice that, under our assumption $xy\in P_{2}^{x}$. Otherwise, if $xy\notin
P_{2}^{x}$, then by Observation 1.2 and given that $wv\in P_{2}^{v}\cap
P_{2}^{w}$, $vx\in P_{2}^{x}\cap P_{3}^{v}$, $xy\notin P_{1}^{y}\cup
P_{2}^{x}$ and $yw\in P_{1}^{y}-P_{2}^{w}$, we have that $(w,v,x,y,w)$ is an
$H$-cycle of length 4 in $G$ containing $v$, which is impossible. Hence, by
Observation 1.2, $(x,y,v,w,x)$ is an $H$-cycle of length 4 in $G$ containing
$v$ (as $xy\in P_{2}^{x}-P_{1}^{y}$, $yv\in P_{1}^{y}-P_{2}^{v}$, $vw\in
P_{2}^{v}\cap P_{2}^{w}$ and $wx\in P_{1}^{w}\cap P_{1}^{x}$), a
contradiction. Therefore $xy\in P_{1}^{y}$.

Proceeding by contradiction, we will prove that $xy\notin P_{1}^{x}$.
By Observation 1.1, we have the following assertions: $x$ is an obstruction of
the cycle $C^{\prime}=(y,x,w,y)$ (because $wx\in P_{1}^{x}$), $y$ is an
obstruction of the cycle $C^{\prime}$ (as $\\{xy,wy\\}\subseteq P_{1}^{y}$),
and $w$ is not an obstruction of the cycle $C^{\prime}$ (recall that $xw\in
P_{1}^{w}$ and $yw\notin P_{1}^{w}$). Hence, the cycle $C^{\prime}$ has
exactly two obstructions (namely $x$ and $y$), with $\ell(C^{\prime})=3$,
contradicting the hypothesis 3 of Theorem 1.4. Therefore $xy\notin P_{1}^{x}$.

Proceeding by contradiction, we will see that $uy\in P_{1}^{y}$.
Observe that, under our assumption, $uy\in P_{1}^{u}$. Otherwise, if $uy\notin
P_{1}^{u}$, then by Observation 1.2, we have that $(w,v,u,y,w)$ is an
$H$-cycle of length 4 in $G$ containing $v$ (recall that $wv\in P_{2}^{v}\cap
P_{2}^{w}$, $vu\in P_{1}^{v}\cap P_{1}^{u}$, $uy\notin P_{1}^{u}\cup
P_{1}^{y}$ and $yw\in P_{1}^{y}-P_{2}^{w}$), which is impossible. Hence, by
Observation 1.2, $(u,y,v,w,u)$ is an $H$-cycle of length 4 in $G$ containing
$v$ (since $uy\in P_{1}^{u}-P_{1}^{y}$, $yv\in P_{1}^{y}-P_{2}^{v}$, $vw\in
P_{2}^{v}\cap P_{2}^{w}$ and $wu\in P_{1}^{w}\cap P_{2}^{u}$), a
contradiction. Therefore $uy\in P_{1}^{y}$.

Finally, proceeding by contradiction we will show that $uy\notin P_{2}^{u}$.
Thus by Observation 1.1, we have the following three assertions: $u$ is an
obstruction of the cycle $C^{\prime\prime}=(y,u,w,y)$ (because $uw\in
P_{2}^{u}$), $y$ is an obstruction of the cycle $C^{\prime\prime}$ (as
$\\{uy,wy\\}\subseteq P_{1}^{y}$), and $w$ is not an obstruction of the cycle
$C^{\prime\prime}$ (recall that $uw\in P_{1}^{w}$ and $yw\notin P_{1}^{w}$).
Hence, the cycle $C^{\prime\prime}$ has exactly two obstructions (namely $u$
and $y$), with $\ell(C)=3$, which is impossible because of the hypothesis 3 of
Theorem 1.4. Therefore $uy\notin P_{2}^{u}$.

This concludes the proof of Claim 1. ∎

For every $i$ in $\\{1,2,\cdots,k_{w}\\}$, let $N_{i}^{w}=\\{y\in
N_{G}(w):yw\in P_{i}^{w}\\}$ be, and consider $Z=\\{y\in
N_{G}(w)-(N_{1}^{w}\cup N_{2}^{w}):uy\in P_{1}^{u}\\}$.

Claim 2. $Z\subseteq N_{i}^{w}$ for some $i$ in $\\{3,\cdots,k_{w}\\}$.

###### Proof.

Let $y_{1}$ be in $Z$, and w.l.o.g. assume that $uy_{1}\in P_{i}^{w}$ for some
fixed $i$, $i>2$. We will prove that $Z\subseteq N_{i}^{w}$.
Let $y_{2}$ be in $Z\setminus\\{y_{1}\\}$. Given that $\\{y_{1},y_{2}\\}$ is a
subset of $Z$, we have that $y_{1}\notin N_{1}^{w}\cup N_{2}^{w}$ and
$y_{2}\notin N_{1}^{w}\cup N_{2}^{w}$, that is, $y_{1}w\notin P_{1}^{w}\cup
P_{2}^{w}$ and $y_{2}w\notin P_{1}^{w}\cup P_{2}^{w}$. By Claim 1, $wy_{j}$
and $uy_{j}$ are in the same part of the $k_{y_{j}}$-partition of
$V(G_{y_{j}})$, for $j$ in $\\{1,2\\}$, so by Observation 1.1, $y_{j}$ is an
obstruction of the path $(w,y_{j},u)$. Also, as $\\{y_{1},y_{2}\\}$ is a
subset of $Z$, we have that $\\{uy_{1},uy_{2}\\}\subseteq P_{1}^{u}$, which
implies by the previous observation that $u$ is an obstruction of the path
$(y_{1},u,y_{2})$. Thus $u$, $y_{1}$ and $y_{2}$ are obstructions of the cycle
$C=(w,y_{1},u,y_{2},w)$.
If $w$ is not an obstruction of the cycle $C$, then the cycle $C$ has exactly
3 obstructions (namely $u$, $y_{1}$ y $y_{2}$), with $\ell(C)=4$,
contradicting the hypothesis 2 of Theorem 1.4, so $w$ is an obstruction of the
cycle $C$. Hence, by Observation 1.1, $wy_{1}$ and $wy_{2}$ are in the same
part of the $k_{w}$-partition of $V(G_{w})$, and given that $wy_{1}$ is in
$P_{i}^{w}$, it follows that $wy_{2}\in P_{i}^{w}$, which implies that
$y_{2}\in N_{i}^{w}$.
Therefore $Z\subseteq N_{i}^{w}$ for some $i$ in $\\{3,\cdots,k_{w}\\}$. ∎

Suppose without loss of generality that $Z\subseteq N_{3}^{w}$, and let
$A=\bigcup_{i=4}^{k_{w}}N_{i}^{w}$ be and $S=V(G)-(A\cup\\{u,v,w,x\\})$.
Notice that $|A|\neq 0$, since $k_{w}\geq 5$; moreover $|A|\geq 2$.

Claim 3. $A$ has the $H$-dependency property with respect to the vertex $v$.

###### Proof.

Let $\\{a,a^{\prime}\\}$ be a subset of $A$. As $\\{a,a^{\prime}\\}$ is a
subset of $A$, it follows that $a\notin N_{1}^{w}\cup N_{2}^{w}$ and
$a^{\prime}\notin N_{1}^{w}\cup N_{2}^{w}$, that is, $aw\notin P_{1}^{w}\cup
P_{2}^{w}$ and $a^{\prime}w\notin P_{1}^{w}\cup P_{2}^{w}$. Now, by Claim 1,
$wa$ and $va$ are in the same part of the $k_{a}$-partition of $V(G_{a})$, and
$wa^{\prime}$ and $va^{\prime}$ are in the same part of the
$k_{a^{\prime}}$-partition of $V(G_{a^{\prime}})$. Say that
$\\{va,wa\\}\subseteq P_{1}^{a}$ and $\\{va^{\prime},wa^{\prime}\\}\subseteq
P_{1}^{a^{\prime}}$.
Proceeding by contradiction, suppose that $A$ has not the $H$-dependency
property with respect to the vertex $v$, that is, $a$ is not an obstruction of
the path $(v,a,a^{\prime})$ and $a^{\prime}$ is not an obstruction of the path
$(v,a^{\prime},a)$. This implies, by Observation 1.1, that $va$ and
$aa^{\prime}$ are in different parts of the $k_{a}$-partition of $V(G_{a}$),
and $va^{\prime}$ and $aa^{\prime}$ are in different part of the
$k_{a^{\prime}}$-partition of $V(G_{a^{\prime}})$. Since $va$ is in
$P_{1}^{a}$ and $va^{\prime}$ is in $P_{1}^{a^{\prime}}$, we have that
$aa^{\prime}\notin P_{1}^{a}\cup P_{1}^{a^{\prime}}$; moreover, as
$wa^{\prime}$ is not in $P_{1}^{w}\cup P_{2}^{w}$, it follows by Claim 1 that
$va^{\prime}\notin P_{2}^{v}$. Hence, by Observation 1.2 and given that $wa\in
P_{1}^{a}-P_{2}^{w}$, $aa^{\prime}\notin P_{1}^{a}\cup P_{1}^{a^{\prime}}$,
$a^{\prime}v\in P_{1}^{a^{\prime}}-P_{2}^{v}$ and $vw\in P_{2}^{v}\cap
P_{2}^{w}$, it follows that $(w,a,a^{\prime},v,w)$ is an $H$-cycle of length 4
in $G$ containing $v$, which is impossible by our assumption.
Therefore $A$ has the $H$-dependency property with respect to the vertex $v$.
∎

Given that $A$ has the $H$-dependency property with respect to the vertex $v$,
we have by Proposition 3.1 that there exists a vertex $a$ in $A$ such that
$l_{a}^{D}\leq\frac{t+1}{2}$, where $D=G[A]$ and $t=|A|$, and $a$ is an
obstruction of the path $(v,a,a^{\prime})$ for some $a^{\prime}$ in $N_{D}(a)$
(recall that $|A|\geq 2$). Since $a$ is in $A$, it follows that $a\notin
N_{1}^{w}\cup N_{2}^{w}$, that is, $wa\notin P_{1}^{w}\cup P_{2}^{w}$, which
implies by Claim 1 that $ua$, $va$, $wa$ and $xa$ are in the same part of the
$k_{a}$-partition of $V(G_{a})$, and $va\notin P_{2}^{v}$. Suppose that $va\in
P_{1}^{a}$, so $\\{ua,va,wa,xa\\}\subseteq P_{1}^{a}$, moreover, as $a$ is an
obstruction of the path $(v,a,a^{\prime})$, it follows by Observation 1.1 that
$aa^{\prime}\in P_{1}^{a}$.
Denoting by $s=min\\{|S|,3\\}$ (recall that $S=V(G)-(A\cup\\{u,v,w,x\\})$),
$S_{1}=N_{1}^{w}-\\{u,x\\}$, $S_{2}=N_{2}^{w}-\\{v\\}$ and $S_{3}=N_{3}^{w}$,
we have that $S=S_{1}\cup S_{2}\cup S_{3}$ and
$n=|S|+|A|+|\\{u,v,w,x\\}|=|S|+t+4\geq s+t+4$.

Claim 4. $k_{a}\leq l_{a}^{D}+s$ (see Notation 3.1).

###### Proof.

Recall that $G_{a}$ is a complete $k_{a}$-partite graph for some $k_{a}$ in
$\mathbb{N}$, and $\mathcal{P}=\\{P_{1}^{a},P_{2}^{a},\cdots,P_{k_{a}}^{a}\\}$
is the $k_{a}$-partition of $V(G_{a})$ into independent sets. By the
Observation 3.1, since $D$ is an induced subgraph of $G$, we have that
$\mathcal{Q}=\\{P_{i}^{a}\cap V(D_{a}):P_{i}^{a}\cap
V(D_{a})\neq\emptyset,i\in\\{1,2,\cdots,k_{a}\\}\\}$ is the
$l_{a}^{D}$-partition of $V(D_{a})$ into independent sets, where
$V(D_{a})=\\{e\in E(D):e\ \mbox{is incident with}\ a\\}$. Renaming, if
necessary, we say that $\mathcal{Q}=\\{P_{1}^{a}\cap V(D_{a}),P_{2}^{a}\cap
V(D_{a}),\cdots,P_{l_{a}^{D}}^{a}\cap V(D_{a})\\}$ is the
$l_{a}^{D}$-partition of $V(D_{a})$ into independent sets.
Now, in order to prove this upper bound of $k_{a}=k_{a}^{G}$ in terms of
$l_{a}^{D}$, consider the edges incident with $a$ that are not vertices in
$D_{a}$, that is, $V(G_{a})-V(D_{a})=\\{ua,va,wa,xa\\}\cup\\{ay:y\in S\\}$.
Since $\\{ua,va,wa,xa\\}\subseteq P_{1}^{a}$ and $a^{\prime}a\in P_{1}^{a}$,
with $a^{\prime}\in N_{D}(a)$, when we consider the edges $ua$, $va$, $wa$ and
$xa$, we add no extra part in $\mathcal{P}$ with respect to the number of
parts of $\mathcal{Q}$. Given this, it is enough to analyze what happens when
we consider the edges $ya$, with $y\in S$. We will see that, when we consider
such edges, we add at most three parts in the $k_{a}$-partition of $V(G_{a})$
with respect to the number of parts in the $l_{a}^{D}$-partition of
$V(D_{a})$, one part for each set $S_{i}$, with $i$ in $\\{1,2,3\\}$.
Let $y$ be in $S$, hence $y\in S_{1}\cup S_{2}\cup S_{3}$ (moreover, by the
definition of the sets $S_{1}$, $S_{2}$ and $S_{3}$, we have that $yw\in
P_{1}^{w}\cup P_{2}^{w}\cup P_{3}^{w}$). In view of this, we divide the rest
of the proof of Claim 4 into 3 cases, depending on whether $y$ is in $S_{1}$,
$S_{2}$ or $S_{3}$.

Case 4.1. $y\in S_{1}$.
Thus $wy\in P_{1}^{w}$, in particular $wy\notin P_{2}^{w}$. W.l.o.g. suppose
that $wy\in P_{1}^{y}$.

Claim 4.1. For every $z$ in $S_{1}$, if $wz$ is in $P_{1}^{z}$, then $az\in
P_{1}^{z}\cup P_{1}^{a}$.

###### Proof.

Let $z$ be in $S_{1}$, thus $zw\in P_{1}^{w}$ (in particular $zw\notin
P_{2}^{w}$) and w.l.o.g suppose that $wz\in P_{1}^{z}$. Proceeding by
contradiction, suppose that $az\notin P_{1}^{z}\cup P_{1}^{a}$. Since $wv\in
P_{2}^{v}\cap P_{2}^{w}$, $va\in P_{1}^{a}-P_{2}^{v}$, $az\notin P_{1}^{z}\cup
P_{1}^{a}$ and $zw\in P_{1}^{z}-P_{2}^{w}$, we have by Observation 1.2 that
$(w,v,a,z,w)$ is an $H$-cycle of length 4 in $G$ containing $v$, which is
impossible, and Claim 4.1 holds. ∎

Given that $y\in S_{1}$, with $wy\in P_{1}^{y}$, we have by Claim 4.1 that
$ay\in P_{1}^{y}\cup P_{1}^{a}$. If $ay\in P_{1}^{a}$, then when we consider
that edge, we add no extra part in the $k_{a}$-partition of $V(G_{a})$ with
respect to the number of parts of the $l_{a}^{D}$-partition of $V(D_{a})$, as
$a^{\prime}a\in P_{1}^{a}$, with $a^{\prime}\in N_{D}(a)$. Now, we can assume
that $ay\notin P_{1}^{a}$, which implies that $ay\in P_{1}^{y}$ and $ay\in
P_{\alpha}^{a}$ for some $\alpha\neq 1$ (moreover, we can assume that
$\alpha>l_{a}^{D}$, otherwise, the edge $ay$ is already counted in the first
$l_{a}^{D}$ parts of the partition of $V(G_{a})$).

Claim 4.2. For every $y^{\prime}$ in $S_{1}$, $ay^{\prime}\in P_{1}^{a}$ or
$ay^{\prime}\in P_{\alpha}^{a}$.

###### Proof.

Let $y^{\prime}$ be in $S_{1}-\\{y\\}$, and w.l.o.g. suppose that
$wy^{\prime}\in P_{1}^{y^{\prime}}$. By Claim 4.1, we have that
$ay^{\prime}\in P_{1}^{y^{\prime}}\cup P_{1}^{a}$. Assuming that
$ay^{\prime}\notin P_{1}^{a}$, we will see that $ay^{\prime}\in
P_{\alpha}^{a}$.
First notice that $ay^{\prime}\in P_{1}^{y^{\prime}}$. Since
$\\{ay^{\prime},wy^{\prime}\\}$ is a subset of $P_{1}^{y^{\prime}}$, it
follows by Observation 1.1 that $y^{\prime}$ is an obstruction of the walk
$(a,y^{\prime},w)$. By the same argument, $y$ is an obstruction of the path
$(a,y,w)$ (recall that $\\{wy,ay\\}\subseteq P_{1}^{y}$) and $w$ is an
obstruction of the path $(y,w,y^{\prime})$ (as $\\{wy,wy^{\prime}\\}\subseteq
P_{1}^{w}$). Thus $w$, $y$ and $y^{\prime}$ are obstructions of the cycle
$C=(w,y,a,y^{\prime},w)$. If $a$ is an obstruction of the cycle $C$, then $C$
has exactly 3 obstructions (namely $w$, $y$ and $y^{\prime}$), contradicting
the hypothesis 2 of Theorem 1.4, so $a$ is not an obstruction of the cycle
$C$. By Observation 1.1, $ay$ and $ay^{\prime}$ are in the same part of the
$k_{a}$-partition of $V(G_{a}$), and since $ay$ is in $P_{\alpha}^{a}$, it
follows that $ay^{\prime}\in P_{\alpha}^{a}$, as desired. ∎

Since for every $y^{\prime}$ in $S_{1}$, $ay^{\prime}\in P_{1}^{a}$ or
$ay^{\prime}\in P_{\alpha}^{a}$, with $\alpha$ in
$\\{l_{a}^{D}+1,\cdots,k_{a}\\}$, we have that, when we consider the edges
$y^{\prime}a$, with $y^{\prime}$ in $S_{1}$, we add at most one part in
$\mathcal{P}$ with respect to the number of parts in $\mathcal{Q}$, namely
$P_{\alpha}^{a}$.

Case 4.2. $y\in S_{2}$.
Thus $wy\in P_{2}^{w}$, w.l.o.g. assume that $wy\in P_{1}^{y}$.

Claim 4.3. For every $z$ in $S_{2}$, if $wz$ is in $P_{1}^{z}$, then $vz\in
P_{1}^{z}$ and $az\in P_{1}^{z}\cup P_{1}^{a}$.

###### Proof.

Let $z$ be in $S_{2}$, thus $wz\in P_{2}^{w}$ and w.l.o.g. suppose that $wz\in
P_{1}^{z}$.
Now, proceeding by contradiction we will prove that $vz\in P_{1}^{z}$; so
suppose that $vz\notin P_{1}^{z}$.
If $vz\in P_{3}^{v}$, then by Observation 1.1 and given that $wu\in
P_{1}^{w}\cap P_{2}^{u}$, $uv\in P_{1}^{v}\cap P_{1}^{u}$, $vz\in
P_{3}^{v}-P_{1}^{z}$ and $zw\in P_{1}^{z}\cap P_{2}^{w}$, we have that
$(w,u,v,z,w)$ is an $H$-cycle of length 4 in $G$ containing $v$, which is
impossible.
If $vz\notin P_{3}^{v}$, then by the same observation with $wx\in
P_{1}^{w}\cap P_{1}^{x}$, $xv\in P_{2}^{x}\cap P_{3}^{v}$, $vz\notin
P_{3}^{v}\cup P_{1}^{z}$ and $zw\in P_{1}^{z}\cap P_{2}^{w}$, we have that
$(w,x,v,z,w)$ is an $H$-cycle of length 4 in $G$ containing $v$, a
contradiction.
We conclude that $vz\in P_{1}^{z}$.

Now, we will see that $az\in P_{1}^{z}\cup P_{1}^{a}$. Proceeding by
contradiction, suppose that $az\notin P_{1}^{z}\cup P_{1}^{a}$.
If $vz\in P_{2}^{v}$, then by Observation 1.1 and given that $vu\in
P_{1}^{v}$, it follows that $v$ is not an obstruction of the path $(z,v,u)$.
By the same argument, $a$ is not an obstruction of the path $(u,a,z)$ (as
$ua\in P_{1}^{a}$ and $az\notin P_{1}^{a}$), and $z$ is not an obstruction of
the path $(a,z,v)$ (recall that $zv\in P_{1}^{z}$ and $az\notin P_{1}^{z}$).
Since $a$ is in $A=\bigcup_{i=4}^{k_{w}}N_{i}^{w}$, it follows that $a\notin
N_{3}^{w}$, with $Z\subseteq N_{3}^{w}$ (see Claim 2), implying that $a\notin
Z$. Hence, by the definition of the set $Z$, we have that $ua\notin
P_{1}^{u}$, and given that $vu$ is in $P_{1}^{u}$, we have by the Observation
1.1 that $u$ is not an obstruction of the path $(v,u,a)$. Thus $z$, $v$, $u$
and $a$ are not obstructions of the cycle $C=(z,v,u,a,z)$, and by Observation
1.2, $C$ is an $H$-cycle of length 4 in $G$ containing $v$, which is
impossible.
If $vz\notin P_{2}^{v}$, then by Observation 1.2 we have that $(w,v,z,a,w)$ is
an $H$-cycle of length 4 in $G$ containing $v$ (since $wv\in P_{2}^{v}\cap
P_{2}^{w}$, $vz\in P_{1}^{z}-P_{2}^{v}$, $za\notin P_{1}^{z}\cup P_{1}^{a}$
and $aw\in P_{1}^{a}-P_{2}^{w}$), a contradiction.
We conclude that $az\in P_{1}^{z}\cup P_{1}^{a}$. ∎

Since $y\in S_{2}$, with $wy\in P_{1}^{y}$, we have by Claim 4.3 that $ay\in
P_{1}^{y}\cup P_{1}^{a}$. If $ay\in P_{1}^{a}$, then when we consider this
edge, we add no extra part in the $k_{a}$-partition of $V(G_{a})$ with respect
to the number of parts of the $l_{a}^{D}$-partition of $V(D_{a})$, as
$a^{\prime}a\in P_{1}^{a}$, with $a^{\prime}\in N_{D}(a)$. Hence, we can
assume that $ay\notin P_{1}^{a}$, which implies that $ay\in P_{1}^{y}$ and
$ay\in P_{\alpha}^{a}$ for some $\alpha\neq 1$ (moreover, we can assume that
$\alpha>l_{a}^{D}$, otherwise, the edge $ay$ is already counted in the first
$l_{a}^{D}$ parts of the partition of V($G_{a}$)).
Proceeding in a very similar way to the proof of Claim 4.2 (taking $S_{2}$
instead of $S_{1}$ and $P_{2}^{w}$ instead of $P_{1}^{w}$) we can prove that:

Claim 4.4. For every $y^{\prime}$ in $S_{2}$, $ay^{\prime}\in P_{1}^{a}$ or
$ay^{\prime}\in P_{\alpha}^{a}$.

Since for every $y^{\prime}$ in $S_{2}$, $ay^{\prime}\in P_{1}^{a}$ or
$ay^{\prime}\in P_{\alpha}^{a}$, with $\alpha$ in
$\\{l_{a}^{D}+1,\cdots,k_{a}\\}$, we have that, when we consider the edges
$y^{\prime}a$ with $y^{\prime}$ in $S_{2}$, we add at most one part in
$\mathcal{P}$ with respect to the number of parts in $\mathcal{Q}$, namely
$P_{\alpha}^{a}$.

Case 4.3. $y\in S_{3}$.
Thus $wy\in P_{3}^{w}$, in particular $wy\notin P_{2}^{w}$. To prove the Case
4.1 of Claim 4, we only need that $wy\notin P_{2}^{w}$ as an extra
information. Hence, the proof of this Case 4.3 is exactly the same to the
proof of the Case 4.1.
Therefore, when we consider the edges $ya$, with $y\in S_{3}$, we add at most
one part in $\mathcal{P}$ with respect to the number of parts in
$\mathcal{Q}$.

This concludes the proof of Claim 4. ∎

Now we finish the proof of the Case 1 of Theorem 1.4.
By Claim 4, we have that $l_{a}^{D}+s\geq k_{a}$, and since
$k_{a}\geq\frac{n+1}{2}$ (by hypothesis) and $\frac{t+1}{2}\geq l_{a}^{D}$, it
follows that

$\frac{t+1}{2}+s\geq l_{a}^{D}+s\geq k_{a}\geq\frac{n+1}{2}.$

Simplifying this inequality we obtain that $t+2s\geq n$, and since $n\geq
s+t+4$, we have that $t+2s\geq s+t+4$, that is, $s\geq 4$, which is impossible
because $s=min\\{|S|,3\\}\leq 3$.

This concludes the Case 1.

Case 2. There exists no vertex $x$ in $V(G)-\\{u,v,w\\}$ with the following
properties

  * •

$xu\in P_{2}^{u}$, $xw\in P_{1}^{w}$,

  * •

$ux$ and $wx$ are in the same part of the $k_{x}$-partition of $V(G_{x})$,

  * •

$vx$ and $ux$ are in different part of the $k_{x}$-partition of $V(G_{x})$,

  * •

$xv\notin P_{1}^{v}\cup P_{2}^{v}$.

Claim 5. For every $x$ in $V(G)-\\{u,v,w\\}$, if $vx\notin P_{1}^{v}\cup
P_{2}^{v}$, then

  1. 1.

$ux$, $vx$ y $wx$ are in the same part of the $k_{x}$-partition of $V(G_{x})$,

  2. 2.

$wx\notin P_{2}^{w}$ and $ux\notin P_{1}^{u}$.

###### Proof.

Let $x$ be a vertex in $V(G)-\\{u,v,w\\}$ such that $vx\notin P_{1}^{v}\cup
P_{2}^{v}$. Suppose without loss of generality that $vx\in P_{1}^{x}\cap
P_{3}^{v}$, thus the item (1) can be rewritten as follows:
$\\{ux,vx,wx\\}\subseteq P_{1}^{x}$.

To prove Claim 5, first we establish the two following claims.

Claim 5.1. $wx\in P_{1}^{w}\cup P_{1}^{x}$ and $ux\in P_{2}^{u}\cup
P_{1}^{x}$.

###### Proof.

First, proceeding by contradiction we will prove that $wx\in P_{1}^{w}\cup
P_{1}^{x}$. So suppose that $wx\notin P_{1}^{w}\cup P_{1}^{x}$. Since $wu\in
P_{1}^{w}\cap P_{2}^{u}$, $uv\in P_{1}^{u}\cap P_{1}^{v}$, $vx\in
P_{3}^{v}\cap P_{1}^{x}$ and $xw\notin P_{1}^{w}\cup P_{1}^{x}$, we have by
Observation 1.2 that $(w,u,v,x,w)$ is an $H$-cycle of length 4 in $G$
containing $v$, which is impossible. Therefore $wx\in P_{1}^{w}\cup
P_{1}^{x}$.

Now, we will see that $ux\in P_{2}^{u}\cup P_{1}^{x}$. Proceeding by
contradiction, suppose that $ux\notin P_{2}^{u}\cup P_{1}^{x}$. Given that
$wu\in P_{1}^{w}\cap P_{2}^{u}$, $ux\notin P_{2}^{u}\cup P_{1}^{x}$, $xv\in
P_{3}^{v}\cap P_{1}^{x}$ and $vw\in P_{2}^{v}\cap P_{2}^{w}$, it follows by
Observation 1.2 that $(w,u,x,v,w)$ is an $H$-cycle of length 4 in $G$
containing $v$, a contradiction. Therefore $ux\in P_{2}^{u}\cup P_{1}^{x}$. ∎

Claim 5.2. If $wx\in P_{1}^{x}$, then $wx\notin P_{2}^{w}$, and if $ux\in
P_{1}^{x}$, then $ux\notin P_{1}^{u}$.

###### Proof.

First, we will prove that $wx\in P_{1}^{x}$ implies that $wx\notin P_{2}^{w}$.
Proceeding by contradiction, suppose that $wx\in P_{1}^{x}\cap P_{2}^{w}$.
Since $\\{wx,vx\\}$ is a subset of $P_{1}^{x}$, we have by Observation 1.1
that $x$ is an obstruction of the path $(v,x,w)$. By the same observation, $w$
is an obstruction of the path $(v,w,x)$ (since $\\{wx,wv\\}\subseteq
P_{2}^{w}$), and $v$ is not an obstruction of the path $(w,v,x)$ (recall that
$vw\in P_{2}^{v}$ and $vx\in P_{3}^{v}$). Hence, $(v,x,w,v)$ is a cycle of
length 3 in $G$ with exactly two obstructions (namely $w$ and $x$), which is
impossible because of the hypothesis 3 of Theorem 1.4. Therefore $wx\notin
P_{2}^{w}$, whenever $wx\in P_{1}^{x}$.

Now, we will see that $ux\in P_{1}^{x}$ implies that $ux\notin P_{1}^{u}$.
Proceeding by contradiction, suppose that $ux\in P_{1}^{x}\cap P_{1}^{u}$.
Given that $\\{ux,vx\\}$ is a subset of $P_{1}^{x}$, it follows by Observation
1.1 that $x$ is an obstruction of the path $(v,x,u)$. By the same observation,
$u$ is an obstruction of the path $(v,u,x)$ (as $\\{ux,uv\\}\subseteq
P_{1}^{u}$), and $v$ is not an obstruction of the path $(u,v,x)$ (since $vu\in
P_{1}^{v}$ and $vx\in P_{3}^{v}$). Hence, $(v,x,u,v)$ is a cycle of length 3
in $G$ with exactly two obstructions (namely $u$ and $x$), contradicting the
hypothesis 3 of Theorem 1.4. Therefore $ux\in P_{1}^{x}$ implies $ux\notin
P_{1}^{u}$. ∎

To conclude, we split the proof of Claim 5 into 4 cases with respect to the
set $P_{1}^{x}$.

Case 5.1. $\\{wx,ux\\}\subseteq P_{1}^{x}$.
Since $\\{wx,ux\\}\subseteq P_{1}^{x}$, Claim 5.2 implies that $wx\notin
P_{2}^{w}$ and $ux\notin P_{1}^{u}$. Also, by the assumption of this case,
$\\{ux,vx,wx\\}\subseteq P_{1}^{x}$. In this case, Claim 5 holds.

Case 5.2. $wx\in P_{1}^{x}$ and $ux\notin P_{1}^{x}$.
Given that $ux\in P_{2}^{u}\cup P_{1}^{x}$ (see Claim 5.1) and $ux\notin
P_{1}^{x}$, we have that $ux\in P_{2}^{u}$; also, as $wx$ is in $P_{1}^{x}$,
we have by Claim 5.2 that $wx\notin P_{2}^{w}$. Hence, by Observation 1.2,
$(v,u,x,w,v)$ is an $H$-cycle of length 4 in $G$ containing $v$ (since $vu\in
P_{1}^{v}\cap P_{1}^{u}$, $ux\in P_{2}^{u}-P_{1}^{x}$, $xw\in
P_{1}^{x}-P_{2}^{w}$ and $wv\in P_{2}^{v}\cap P_{2}^{w}$), which is a
contradiction. Therefore this case is not possible.

Case 5.3. $wx\notin P_{1}^{x}$ and $ux\in P_{1}^{x}$.
By the Claim 5.1, we have that $wx\in P_{1}^{w}\cup P_{1}^{x}$, but $wx\notin
P_{1}^{x}$, thus $wx\in P_{1}^{w}$; also, as $ux$ is in $P_{1}^{x}$, it
follows by Claim 5.2 that $ux\notin P_{1}^{u}$. Hence, by Observation 1.2,
$(v,u,x,w,v)$ is an $H$-cycle of length 4 in $G$ containing $v$ (recall that
$vu\in P_{1}^{v}\cap P_{1}^{u}$, $ux\in P_{1}^{x}-P_{1}^{u}$, $xw\in
P_{1}^{w}-P_{1}^{x}$ and $wv\in P_{2}^{v}\cap P_{2}^{w}$), a contradiction.
Therefore this case is impossible.

Case 5.4. $wx\notin P_{1}^{x}$ and $ux\notin P_{1}^{x}$.
By Claim 5.1 we know that $wx\in P_{1}^{w}\cup P_{1}^{x}$ and $ux\in
P_{2}^{u}\cup P_{1}^{x}$, but $wx\notin P_{1}^{x}$ and $ux\notin P_{1}^{x}$,
thus $wx\in P_{1}^{w}$ and $ux\in P_{2}^{u}$. Since $vu\in P_{1}^{u}$ and
$xu\in P_{2}^{u}$, we have by Observation 1.1 that $u$ is not an obstruction
of the path $(v,u,x)$. By the same observation, $v$ is not an obstruction of
the path $(w,v,u)$ (given that $uv\in P_{1}^{v}$ and $wv\in P_{2}^{v}$), and
$w$ is not an obstruction of the path $(v,w,x)$ (as $xw\in P_{1}^{w}$ and
$vw\in P_{2}^{w}$). So $u$, $v$ and $w$ are not obstructions of the cycle
$C=(v,w,x,u,v)$. If $x$ is not an obstruction of the cycle $C$, then by the
Observation 1.2, $C$ is an $H$-cycle of length 4 in $G$ containing $v$, which
is impossible. Hence, $v$ is not an obstruction of the cycle $C$, which
implies by Observation 1.1 that $ux$ and $wx$ are in the same part of the
$k_{x}$-partition of $V(G_{x})$. Recall that $xu\in P_{2}^{u}$, $xw\in
P_{1}^{w}$, and $xv\notin P_{1}^{v}\cup P_{2}^{v}$; also $ux\notin P_{1}^{x}$
and $vx\in P_{1}^{x}$ (that is, $ux$ and $vx$ are in different part of the
$k_{x}$-partition of $V(G_{x})$). This contradicts the assumption of the Case
2 of Theorem 1.4. Therefore this case is not possible.

This concludes the proof of Claim 5. ∎

For every $i$ in $\\{1,2,\cdots,k_{v}\\}$, let $N_{i}^{v}=\\{y\in N(v):zv\in
P_{i}^{v}\\}$ be, and consider $A=\bigcup_{i=3}^{k_{v}}N_{i}^{v}$ and
$S=V(G)-(A\cup\\{u,v,w\\})$. Notice that $|A|\neq 0$, since $k_{v}\geq 5$;
moreover $|A|\geq 2$.

Claim 6. $A$ has the $H$-dependency property with respect to the vertex $v$.

###### Proof.

Let $\\{a,a^{\prime}\\}$ be a subset of $A$. As $\\{a,a^{\prime}\\}$ is a
subset of $A$, it follows that $a\notin N_{1}^{v}\cup N_{2}^{v}$ and
$a^{\prime}\notin N_{1}^{v}\cup N_{2}^{v}$, that is, $av\notin P_{1}^{v}\cup
P_{2}^{v}$ and $a^{\prime}v\notin P_{1}^{v}\cup P_{2}^{v}$. Now, by Claim 5,
$va$ and $wa$ are in the same part of the $k_{a}$-partition of $V(G_{a})$, and
$va^{\prime}$ and $wa^{\prime}$ are in the same part of the
$k_{a^{\prime}}$-partition of $V(G_{a^{\prime}})$. Suppose without loss of
generality that $\\{va,wa\\}\subseteq P_{1}^{a}$ and
$\\{va^{\prime},wa^{\prime}\\}\subseteq P_{1}^{a^{\prime}}$.
Proceeding by contradiction, suppose that $A$ has not the $H$-dependency
property with respect to the vertex $v$, that is, $a$ is not an obstruction of
the path $(v,a,a^{\prime})$ and $a^{\prime}$ is not an obstruction of the path
$(v,a^{\prime},a)$. This implies by Observation 1.1, that $va$ and
$aa^{\prime}$ are in different parts of the $k_{a}$-partition of $V(G_{a}$),
and $va^{\prime}$ and $aa^{\prime}$ are in different part of the
$k_{a^{\prime}}$-partition of $V(G_{a^{\prime}})$. Since $va$ is in
$P_{1}^{a}$ and $va^{\prime}$ is in $P_{1}^{a^{\prime}}$, we have that
$aa^{\prime}\notin P_{1}^{a}\cup P_{1}^{a^{\prime}}$; moreover, as $va$ is not
in $P_{1}^{v}\cup P_{2}^{v}$, it follows by Claim 5 that $wa\notin P_{2}^{w}$.
Next, by Observation 1.2 and given that $wa\in P_{1}^{a}-P_{2}^{w}$,
$aa^{\prime}\notin P_{1}^{a}\cup P_{1}^{a^{\prime}}$, $a^{\prime}v\in
P_{1}^{a^{\prime}}-P_{2}^{v}$ and $vw\in P_{2}^{v}\cap P_{2}^{w}$, we have
that $(w,a,a^{\prime},v,w)$ is an $H$-cycle of length 4 in $G$ containing $v$,
which is impossible.
Therefore $A$ has the $H$-dependency property with respect to the vertex $v$.
∎

Given that $A$ has the $H$-dependency property with respect to the vertex $v$,
we have by Proposition 3.1 that there exists a vertex $a$ in $A$ such that
$l_{a}^{D}\leq\frac{t+1}{2}$, where $D=G[A]$ and $t=|A|$, and $a$ is an
obstruction of the path $(v,a,a^{\prime})$ for some $a^{\prime}$ in $N_{D}(a)$
(recall that $|A|\geq 2$). Since $a$ is in $A$, thus $a\notin N_{1}^{v}\cup
N_{2}^{v}$, that is, $va\notin P_{1}^{v}\cup P_{2}^{v}$, this implies by Claim
5 that $ua$, $va$ and $wa$ are in the same part of the $k_{a}$-partition of
$V(G_{a})$, $wa\notin P_{2}^{w}$ and $ua\notin P_{1}^{u}$. Suppose that $va$
is in $P_{1}^{a}$, so $\\{ua,va,wa\\}\subseteq P_{1}^{a}$, moreover, as $a$ is
an obstruction of the path $(v,a,a^{\prime})$, it follows by Observation 1.1
that $aa^{\prime}\in P_{1}^{a}$.
Denoting by $s=min\\{|S|,2\\}$, $S_{1}=N_{1}^{v}-\\{u\\}$ and
$S_{2}=N_{2}^{v}-\\{w\\}$, it follows that $S=S_{1}\cup S_{2}$ and
$n=|S|+|A|+|\\{u,v,w\\}|=|S|+t+3\geq s+t+3$.

Claim 7. $k_{a}\leq l_{a}^{D}+s$ (see Notation 3.1).

###### Proof.

Recall that $G_{a}$ is a complete $k_{a}$-partite graph for some $k_{a}$ in
$\mathbb{N}$, and $\mathcal{P}=\\{P_{1}^{a},P_{2}^{a},\cdots,P_{k_{a}}^{a}\\}$
is the $k_{a}$-partition of $V(G_{a})$ into independent sets. As $D$ is an
induced subgraph of $G$, by Observation 3.1 we have that
$\mathcal{Q}=\\{P_{i}^{a}\cap V(D_{a}):P_{i}^{a}\cap
V(D_{a})\neq\emptyset,i\in\\{1,2,\cdots,k_{a}\\}\\}$ is the
$l_{a}^{D}$-partition of $V(D_{a})$ into independent sets, where
$V(D_{a})=\\{e\in E(D):e\ \mbox{incide en}\ a\\}$. Renaming, if necessary, we
say that $\mathcal{Q}=\\{P_{1}^{a}\cap V(D_{a}),P_{2}^{a}\cap
V(D_{a}),\cdots,P_{l_{a}^{D}}^{a}\cap V(D_{a})\\}$ is the
$l_{a}^{D}$-partition of $V(D_{a})$ into independent sets.
Now, in order to prove this upper bound of $k_{a}=k_{a}^{G}$ in terms of
$l_{a}^{D}$, consider the edges incident with $a$ that are not vertices in
$D_{a}$, that is, $V(G_{a})-V(D_{a})=\\{ua,va,wa\\}\cup\\{ya:y\in S\\}$. Since
$\\{ua,va,wa\\}\subseteq P_{1}^{a}$ and $a^{\prime}a\in P_{1}^{a}$, with
$a^{\prime}\in N_{D}(a)$, when we consider the edges $ua$, $va$ and $wa$, we
add no extra part in $\mathcal{P}$ with respect to the number of parts of
$\mathcal{Q}$. In view of this, it suffices to analyze what happens when we
consider the edges $ya$, with $y\in S$. We will see that, when we consider
such edges, we add at most 2 parts in the $k_{a}$-partition of $V(G_{a})$ with
respect to the number of parts of the $l_{a}^{D}$-partition of $V(D_{a})$, one
part for each set $S_{i}$, with $i$ en $\\{1,2\\}$.
Let $y$ in $S$, hence $y\in S_{1}\cup S_{2}$ (moreover, by the definition of
the sets $S_{1}$ and $S_{2}$, we have that $yv\in P_{1}^{v}\cup P_{2}^{v}$).
We divide the rest of the proof of Claim 7 into two cases, depending on
whether $y$ is in $S_{1}$ or $S_{2}$.

Case 7.1. $y\in S_{1}$.
Thus $vy\in P_{1}^{v}$ and suppose without loss of generality that $wy\in
P_{1}^{y}$.

Claim 7.1. For every $z$ in $S_{1}$, if $vz$ is in $P_{1}^{z}$, then $az\in
P_{1}^{z}\cup P_{1}^{a}$.

###### Proof.

Let $z$ be in $S_{1}$, thus $vz\in P_{1}^{v}$ and suppose w.l.o.g. that $vz\in
P_{1}^{z}$. Proceeding by contradiction, suppose that $az\notin P_{1}^{z}\cup
P_{1}^{a}$. Since $vz\in P_{1}^{v}\cap P_{1}^{z}$, $za\notin P_{1}^{z}\cup
P_{1}^{a}$, $aw\in P_{1}^{a}-P_{2}^{w}$ and $wv\in P_{2}^{v}\cap P_{2}^{w}$,
we have by Observation 1.2 that $(v,z,a,w,v)$ is an $H$-cycle of length 4 in
$G$ containing $v$, which is impossible and Claim 7.1 holds. ∎

Given that $y\in S_{1}$, with $vy\in P_{1}^{y}$, we have by Claim 7.1 that
$ay\in P_{1}^{y}\cup P_{1}^{a}$. When $ay\in P_{1}^{a}$, and we consider such
edge, no extra part appears in the $k_{a}$-partition of $V(G_{a})$, with
respect to the number of parts of the $l_{a}^{D}$-partition of $V(D_{a})$, as
$a^{\prime}a\in P_{1}^{a}$, with $a^{\prime}\in N_{D}(a)$. Now, we can assume
that $ay\notin P_{1}^{a}$, which implies that $ay\in P_{1}^{y}$ and $ay\in
P_{\alpha}^{a}$ for some $\alpha\neq 1$ (moreover, we can assume that
$\alpha>l_{a}^{D}$, otherwise, the edge $ay$ is already counted in the first
$l_{a}^{D}$ parts of $V(G_{a})$).

Claim 7.2. For every $y^{\prime}$ in $S_{1}$, $ay^{\prime}\in P_{1}^{a}$ or
$ay^{\prime}\in P_{\alpha}^{a}$.

###### Proof.

Let $y^{\prime}$ be in $S_{1}-\\{y\\}$, thus $vy^{\prime}\in P_{1}^{v}$, and
(w.l.o.g.) suppose that $vy^{\prime}\in P_{1}^{y^{\prime}}$. By Claim 7.1 we
have that $ay^{\prime}\in P_{1}^{y^{\prime}}\cup P_{1}^{a}$. If
$ay^{\prime}\in P_{1}^{a}$ we are done, so suppose that $ay^{\prime}\notin
P_{1}^{a}$, which implies that $ay^{\prime}\in P_{1}^{y^{\prime}}$. We will
see that $ay^{\prime}\in P_{\alpha}^{a}$.
Since $\\{ay^{\prime},vy^{\prime}\\}$ is a subset of $P_{1}^{y^{\prime}}$, it
follows by Observation 1.1 that $y^{\prime}$ is an obstruction of the path
$(a,y^{\prime},v)$ in $G$. By the same argument, $y$ is an obstruction of the
path $(a,y,v)$ (as $\\{vy,ay\\}\subseteq P_{1}^{y}$) and $v$ is an obstruction
of the path $(y,v,y^{\prime})$ (recall that $\\{vy,vy^{\prime}\\}\subseteq
P_{1}^{v}$). So $v$, $y$ and $y^{\prime}$ are obstructions of the cycle
$C=(v,y,a,y^{\prime},v)$. If $a$ is not an obstruction of the cycle $C$, then
the cycle $C$ has exactly 3 obstructions (namely $v$, $y$ and $y^{\prime}$),
contradicting the hypothesis 2 of Theorem 1.4, so $a$ is an obstruction of the
cycle $C$. By Observation 1.1, $ay$ and $ay^{\prime}$ are in the same part of
the $k_{a}$-partition of $V(G_{a}$), and since $ay$ is in $P_{\alpha}^{a}$, it
follows that $ay^{\prime}\in P_{\alpha}^{a}$, as desired. ∎

Since for every $y^{\prime}$ in $S_{1}$, $ay^{\prime}\in P_{1}^{a}$ or
$ay^{\prime}\in P_{\alpha}^{a}$, with $\alpha$ in
$\\{l_{a}^{D}+1,\cdots,k_{a}\\}$, we have that, when we consider the edges
$ay^{\prime}$, with $y^{\prime}$ in $S_{1}$, we add at most one part in
$\mathcal{P}$ with respect to the number of parts in $\mathcal{Q}$, namely
$P_{\alpha}^{a}$.

Case 7.2. $y\in S_{2}$.
Thus $vy\in P_{2}^{v}$ and suppose without loss of generality that $wy\in
P_{1}^{y}$.

Claim 7.3. For every $z$ in $S_{2}$, if $vz$ is in $P_{1}^{z}$, then $az\in
P_{1}^{z}\cup P_{1}^{a}$.

###### Proof.

Let $z$ be in $S_{2}$, thus $vz\in P_{2}^{v}$ and suppose (w.l.o.g.) that
$vz\in P_{1}^{z}$. Proceeding by contradiction, suppose that $az\notin
P_{1}^{z}\cup P_{1}^{a}$. Since $vz\in P_{2}^{v}\cap P_{1}^{z}$, $za\notin
P_{1}^{z}\cup P_{1}^{a}$, $au\in P_{1}^{a}-P_{1}^{u}$ and $uv\in P_{1}^{v}\cap
P_{1}^{u}$, we have by Observation 1.2 that $(v,z,a,u,v)$ is an $H$-cycle of
length 4 in $G$ containing $v$, a contradiction and Claim 7.3 holds. ∎

Given that $y\in S_{2}$, with $vy\in P_{1}^{y}$, we have by Claim 7.3 that
$ay\in P_{1}^{y}\cup P_{1}^{a}$. If $ay\in P_{1}^{a}$, then when we consider
that edge, we add no extra part in the $k_{a}$-partition of $V(G_{a})$ with
respect to the number of parts of the $l_{a}^{D}$-partition of $V(D_{a})$, as
$a^{\prime}a\in P_{1}^{a}$, with $a^{\prime}\in N_{D}(a)$. Now, we can assume
that $ay\notin P_{1}^{a}$, which implies that $ay\in P_{1}^{y}$ and $ay\in
P_{\alpha}^{a}$ for some $\alpha\neq 1$ (moreover, we can assume that
$\alpha>l_{a}^{D}$, otherwise, the edge $ay$ is already counted in the first
$l_{a}^{D}$ parts of $G_{a}$).
Proceeding in a very similar way to the proof of Claim 7.2 (taking $S_{2}$
instead of $S_{1}$, and $P_{2}^{v}$ instead of $P_{1}^{v}$), we can prove the
following assertion:

Claim 7.4. For every $y^{\prime}$ in $S_{2}$, $ay^{\prime}\in P_{1}^{a}$ or
$ay^{\prime}\in P_{\alpha}^{a}$.

Since for every $y^{\prime}$ in $S_{2}$, $ay^{\prime}\in P_{1}^{a}$ or
$ay^{\prime}\in P_{\alpha}^{a}$, with $\alpha$ in
$\\{l_{a}^{D}+1,\cdots,k_{a}\\}$, we have that, when we consider the edges
$ay^{\prime}$, with $y^{\prime}$ in $S_{2}$, we add at most one part in
$\mathcal{P}$ with respect to the number of parts in $\mathcal{Q}$, namely
$P_{\alpha}^{a}$.

This concludes the proof of Claim 7. ∎

Now we finish the proof of the Case 2 of Theorem 1.4.
By Claim 7, we have that $l_{a}^{D}+s\geq k_{a}$, and as
$k_{a}\geq\frac{n+1}{2}$ (by hypothesis) and $\frac{t+1}{2}\geq l_{a}^{D}$, it
follows that

$\frac{t+1}{2}+s\geq l_{a}^{D}+s\geq k_{a}\geq\frac{n+1}{2}.$

Simplifying this inequality we obtain that $t+2s\geq n$, and since $n\geq
s+t+3$, we have that $t+2s\geq s+t+3$, that is, $s\geq 3$, which is impossible
because $s=min\\{|S|,2\\}\leq 2$.

This concludes the Case 2.

Therefore, as we assumed that the conclusion of Theorem 1.4 is false, and each
case led us to a contradiction, we conclude that each vertex of $G$ is
contained in an $H$-cycle of length 4 in $G$. $\square$

We show some consequences of the main results of this paper, which are well-
known results in the theory of properly colored walks. We need the following
definition and the Observation 4.4.

######  Definition 4.1.

Let $G$ be an edge-colored graph and $x$ be a vertex in $G$. We define the
color degree of the vertex $x$, denoted by $\delta^{c}(x)$, as follows:
$\delta^{c}(x)=|\\{c(e):e\ \mbox{is an edge incident with}\ x\\}|$.

######  Observation 4.4.

Let $H$ be the complete graph without loops and $G$ be an $H$-colored graph.
For every $u$ in $V(G)$:

  1. 1.

$G_{u}$ is a complete $k_{u}$-partite graph for some $k_{u}$ in $\mathbb{N}$,
moreover, $k_{u}=\delta^{c}(u)$.

  2. 2.

If $W$ is a walk in $G$, then $W$ is a properly colored walk if and only if
$W$ is an $H$-walk. In particular, $W$ is a properly colored path (cycle) if
and only if $W$ is an $H$-path ($H$-cycle).

  3. 3.

The graph $G$ does not contain a cycle of length 3 with exactly 2
obstructions.

  4. 4.

The graph $G$ does not contain a cycle of length 4 with exactly 3
obstructions.

######  Corollary 4.1 ([12]).

Let $G$ be a edge-colored complete graph of order $n$. If $n\geq 3$ and
$\delta^{c}(x)\geq\frac{n+1}{2}$ for every $x$ in $V(G)$, then each vertex is
contained in a properly colored cycle of length 3.

######  Corollary 4.2 ([12]).

Let $G$ be a edge-colored complete graph of order $n$. If $n\geq 4$ and
$\delta^{c}(x)\geq\frac{n+1}{2}$ for every $x$ in $V(G)$, then each vertex is
contained in a properly colored cycle of length 4.

######  Remark 4.1.

The edge-colored complete graph $G$ of the Figure 3 shows that, Corollary 4.1
does not imply Theorem 1.2, and Corollary 4.2 does not imply Corollary 1.1.

Figure 3: Corollary 4.1 does not imply Theorem 1.2, and Corollary 4.2 does not
imply Corollary 1.1.

## References

  * [1] S.K. Ahuja, Algorithms for routing and channel assignment in wireless infrastructure networks, Ph.D. thesis. Univ. Arizona (2010)
  * [2] S. Brandt, R. Faudree, W. Goddard, Weakly pancyclic graphs, J. Graph Theory 27, 141–176 (1998)
  * [3] J. Bang-Jensen, G. Gutin, Alternating cycles and paths in edge-coloured multigraphs: a survey, Discrete Mathematics 165, 39–60 (1997)
  * [4] J. Bang-Jensen, G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, London (2009)
  * [5] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, 1st edn. North-Holland, Amsterdam (1976)
  * [6] J.A. Bondy, Pancyclic graphs, in: Proceedings of the Second Louisiana Conference on Combinatorics, Graph Theory and Computing, Louisiana State University, Baton Rouge, LA., 167–172 (1971)
  * [7] J.A. Bondy, Pancyclic graphs. I., J. Combinatorial Theory Ser. B 11, 80–84 (1971)
  * [8] J.A. Bondy, Pancyclic graphs: recent results. Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. I, pp. 181–187. Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, (1975)
  * [9] W. Chow, Y. Manoussakis, O. Megalakaki, M. Spyratos, Z. Tuza, Paths through fixed vertices in edge-colored graphs, Math. Inf. Sci. Hum. 127, 49–58 (1994)
  * [10] D. Dorninger, Hamiltonian circuits determining the order of chromosomes, Discrete Applied Math. 50, 159–168 (1994)
  * [11] D. Dorninger, W. Timischl, Geometrical constraints on Bennett’s predictions of chromosome order, Heredity 58, 321–325 (1987)
  * [12] S. Fujita, C. Magnant, Properly colored paths and cycles, Discrete Applied Mathematics 159, 1391–1397 (2011)
  * [13] H. Galeana-Sánchez, F. Hernández-Lorenzana, R. Sánchez-López, A generalization of properly colored paths and cycles in edge-colored graphs, Theor. Comput. Sci., (2023), DOI:10.1016/j.tcs.2022.12.029.
  * [14] H. Galeana-Sánchez, R. Rojas-Monroy, R. Sánchez-López, J.I. Villareal-Valdés, Some Conditions for the Existence of Euler $H$-trails, Graphs and Combinatorics 35, 1197-1208 (2019)
  * [15] H. Galeana-Sánchez, R. Rojas-Monroy, R. Sánchez-López, J.I. Villareal-Valdés, $H$-cycles in $H$-colored multigraphs, Graphs and Combinatorics 38, 62 (2022).
  * [16] J.W. Grossman, R. Häggkvist, Alternating cycles in edge-partitioned graphs, J. Combin. Theory Ser. B 34, 77–81 (1983)
  * [17] G. Gutin, E.J. Kim, Properly Coloured Cycles and Paths: Results and Open Problems, Lecture Notes in Computer Science, 200–208 (2009)
  * [18] R. Häggkvist, On $F$-Hamiltonian graphs, Graph Theory and Related Topics, Academic Press, New York, 219–231 (1979)
  * [19] A. Kotzig, Moves without forbidden transitions in a graph, Matematický časopis 18(1), 76–80 (1968)
  * [20] Ming-Chu. Li, D.G. Corneil, E. Mendelsohn, Pancyclicity and NP-completeness in planar graphs, Discrete Appl. Math. 98, 219–225 (2000)
  * [21] X. Li, C. Magnant, Properly colored notions of connectivity-a dynamic survey, Theory and Applications of Graphs (1):2, (2015).
  * [22] V. Linek, B. Sands, A note on paths in edge-colored tournaments, Ars Combin. 44, 225–228 (1996)
  * [23] J. Petersen, Die theorie der regulären graphs, Acta Math. 15, 193–220 (1891)
  * [24] P.A. Pevzner, DNA physical mapping and alternating eulerian cycles in colored graphs, Algorithmica 13, 77–105 (1995)
  * [25] B. Randerath, I. Schiermeyer, M. Tewes, L. Volkmann, Vertex pancyclic graphs, Discrete Applied Mathematics 120, 219-237 (2002)
  * [26] S. Sankararaman, A. Efrat, S. Ramasubramanian, On channel-discontinuity-constraint routing in wireless networks, Ad Hoc Netw. 134, 153–169 (2014)
  * [27] M. Szachniuk, M.C. De Cola, G. Felici, The orderly colored longest path problem a survey of applications and new algorithms, RAIRO-Oper. Res. 48, 25–51 (2014)
  * [28] I.L. Tseng, H.W. Chen, C.I. Lee, Obstacle-aware longest path routing with parallel MILP solvers, Proc. WCECS-ICCS 2, 827–831 (2010)
  * [29] D. Woodall, Improper colourings of graphs, Graph Colourings 218, Longman, Harlow, 45–63 (1990)
  * [30] H. Xu, D. Kilgour, K. Hipel, G. Kemkes, Using matrices to link conflict evolution and resolution in a graph model, Eur. J. Oper. Res. 207(1), 318–329 (2010)
  * [31] H. Xu, K. Li, K. Hipel, D. Kilgour, A matrix approach to status quo analysis in the graph model for conflict resolution, Appl. Math. Comput 212(2), 470–480 (2009)
  * [32] A. Yeo, A note on alternating cycles in edge-coloured graphs, J. Combin. Theory Ser. B, 69, 222–225 (1997)