Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 3 (2010) 139–146
Immersing small complete graphs
Matt DeVos ∗
Department of Mathematics, Simon Fraser University, Burnaby, B.C. V5A 1S6, Canada
Ken-ichi Kawarabayashi †
National Institute of Informatics, 2-1-2, Hitotsubashi, Chiyoda-ku, Tokyo, Japan
Bojan Mohar ‡
Department of Mathematics, Simon Fraser University, Burnaby, B.C. V5A 1S6, Canada
Haruko Okamura
Department of Intelligence and Informatics, Konan University
Okamoto Kobe 658-8501, Japan
Received 10 July 2009, accepted 31 August 2010, published online 19 October 2010
Abstract
Following in the spirit of the Hadwiger and Hajós conjectures, Abu-Khzam and Lang-
ston have conjectured that every k-chromatic graph contains an immersion of Kk. They
proved this for k ≤ 4. Much before that, Lescure and Meyniel [10] obtained a stronger
result that included also the values k = 5 and 6, by proving that every simple graph of
minimum degree k − 1 contains an immersion of Kk. They noted that they also have
a proof of the same result for k = 7 but have not published it due to the length of the
proof. We give a simple proof of this result. This, in particular, proves the conjecture of
Abu-Khzam and Langston for every k ≤ 7.
Keywords: Immersion, Hadwiger Conjecture.
Math. Subj. Class.: 05C35, 05C83
∗Supported in part by an NSERC grant.
†Research partly supported by Japan Society for the Promotion of Science, Grant-in-Aid for Scientific Re-
search, by C & C Foundation, by Kayamori Foundation and by Inoue Research Award for Young Scientists.
‡On leave from: IMFM & FMF, Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia.
Supported in part by Slovenian Research Grant P1–0297 and by Canadian NSERC Discovery Grant and by the
Canada Research Chairs program.
E-mail addresses: mdevos@sfu.ca (Matt DeVos), k keniti@nii.ac.jp (Ken-ichi Kawarabayashi),
mohar@sfu.ca (Bojan Mohar), okamura@center.konan-u.ac.jp (Haruko Okamura)
Copyright c© 2010 DMFA Slovenije
140 Ars Math. Contemp. 3 (2010) 139–146
1 Introduction
In this paper, all graphs are finite and may have loops and multiple edges. A graph H is a
minor of a graph G if (a graph isomorphic to) H can be obtained from a subgraph of G by
contracting edges. A graph H is a topological minor of a graph G if G contains a subgraph
which is isomorphic to a graph that can be obtained from H by subdividing some edges. In
such a case, we also say that G contains a subdivision of H . The chromatic number of G,
denoted χ(G), is the minimum number of colors required by G in any proper coloring of
its vertices. The graph G is k-chromatic if χ(G) = k.
Our paper is motivated by two famous conjectures concerning the chromatic number
and the minor and topological order, namely, Hadwiger’s conjecture and Hajós’ conjecture.
Hadwiger’s Conjecture from 1943 suggests a far-reaching generalization of the Four
Color Theorem [2, 3, 11] and is considered to be one of the deepest open problems in
graph theory. It states that every loopless graph without a Kk-minor is (k − 1)-colorable.
The special case of the Hadwiger Conjecture when k = 5 was shown earlier (Wagner [16])
to be equivalent to the Four Color Theorem. In 1993, Robertson, Seymour and Thomas
[14] proved that the case k = 6 also follows from the Four Color Theorem. The cases
k ≥ 7 are open; for the case k = 7, a partial result in [9] is all that is known.
Hajós proposed a stronger conjecture that for all k ≥ 1, every k-chromatic graph con-
tains a subdivision of the complete graph on k vertices. He already considered the conjec-
ture in the 1940’s in connection with attacks on the Four Colour Conjecture (now theorem).
For k ≤ 4, the conjecture is true, for k = 5, 6, it still remains open. But for every k ≥ 7, it
was disproved by Catlin [6]. In fact, Erdős and Fajtlowicz [7] proved that the conjecture is
false for almost all graphs, see also Bollobás and Catlin [4]. Recently, Thomassen provided
a variety of interesting natural examples where Hajós’ Conjecture fails [15].
In this paper, we consider a different containment relation – graph immersions. A pair
of adjacent edges uv and vw with u 6= w is lifted by deleting the edges uv and vw, and
adding the edge uw (possibly in parallel to an existing edge). A graph H is said to be
immersed in a graph G if a graph isomorphic to H can be obtained from a subgraph of G
by lifting pairs of edges. If H is immersed in a graph G, then we also say that G contains
an H-immersion.
Previous investigation on immersions has been mainly conducted from an algorithmic
standpoint. We refer the reader to [5, 8]. On the other hand, it would be interesting to
consider structural issues, since the notions of an immersion and a minor seem to be quite
similar, and structural approach concerning graph minors has been extremely successful. In
fact, Robertson and Seymour extended their proof of the famous Wagner’s conjecture [12]
to prove that graphs are well-quasi-ordered by the immersion relation [13]. This proves a
conjecture of Nash-Williams. The proof is based on a significant part of the graph minors
project. Hence, we may expect that structural approach concerning immersions is difficult,
maybe as difficult as structure results concerning graph minors.
Immersion containment is quite different from that of topological or minor contain-
ment. It is immediate that a topological minor ofH implies both a minor and an immersion
ofH , but the converse is not generally true. The existence of anH minor and anH immer-
sion are easily seen to be incomparable. Therefore, it would be interesting to investigate
relations between the chromatic number of a graph G and the largest size of a complete
graph immersed in G. In fact, Abu-Khzam and Langston conjectured the following in [1].
Conjecture 1. The complete graph Kk can be immersed in any k-chromatic graph.
M. DeVos et al.: Immersing small complete graphs 141
This conjecture, like Hadwiger’s conjecture and Hajós’ conjecture, is trivially true for
k ≤ 4. In fact, since Hajós’ conjecture is true if k ≤ 4, this immediately implies Conjecture
1 for the cases k ≤ 4.
On the other hand, the case k = 5 does not seem to be trivial. Abu-Khzam and Langston
[1] proved a weaker statement that K−5 is immersed in every 5-chromatic graph. They also
pointed out that structural investigations are extensively studied for graphs without a K4-
immersion (see [5]), but almost nothing is done for graphs without a K5-immersion.
Let us observe that every k-chromatic graph contains a k-critical subgraph and that the
minimum degree of every k-critical graph is at least k − 1. This shows that the following
question for complete immersions is of importance in relation to Conjecture 1.
Problem 2. Let k be a positive integer. Find the smallest value f(k) such that every simple
graph of minimum degree at least f(k) contains an immersion of Kk.
Clearly, f(k) ≥ k − 1, and if f(k) = k − 1, then Conjecture 1 holds since every k-
chromatic graph has a simple subgraph of minimum degree k − 1. Again, this problem is
trivial for k ≤ 4.
The following example, due to Paul Seymour (private communication), shows that
f(k) ≥ k for every k ≥ 10. Let G be the graph obtained from the complete graph K12 by
deleting the edges of four disjoint triangles. Then G has minimum degree 9, but it is easy
to argue that it does not contain an immersion of K10.
The purpose of this paper is to prove the following theorem which establishes Conjec-
ture 1 and resolves Problem 2 for the intermediate values of k.
Theorem 3. Let f(k) be the smallest integer such that every simple graph of minimum
degree at least f(k) contains an immersion of Kk. Then f(k) = k − 1 for k ∈ {5, 6, 7}.
As mentioned before, every k-chromatic graph contains a subgraph of minimum degree
k − 1. Therefore, Theorem 3 also shows that Conjecture 1 holds for k ≤ 7. Although the
methods of our proof may extend to the next case (k = 8), it appears that there may be too
many cases to make this approach feasible.
After completion of the original version of this paper, it came to our attention that
Lescure and Meyniel [10] solved Problem 2 for k = 5, 6. They also report in their paper
that they also have a proof of the same result for k = 7 but have not published it due to the
length of the proof. Our proof turns out to have some similarities with the proof of Lescure
and Meyniel, but the hardest case when k = 7 is simple enough to be presented on a few
pages only.
2 Immersing complete graphs
In this section we shall prove the main theorem. Actually, for inductive purposes, we shall
prove a slightly stronger statement. We begin with a little notation.
Our graphs may in general have parallel edges; If two vertices are joined by more than
one edge, the set of edges joining them is called a proper parallel class. The degree of a
vertex v, denoted deg(v), is the number of edges incident with v (counting loops twice).
We let N(v) denote the set of vertices adjacent to v and we let N(v) = N(v) ∪ {v}.
Theorem 4. Let d ∈ {4, 5, 6}, let G = (V,E) be a loopless graph, and let u ∈ V . Assume
further that G satisfies the following properties:
142 Ars Math. Contemp. 3 (2010) 139–146
• |V | ≥ d.
• deg(v) ≥ d for every v ∈ V \ {u}.
• There are at most d−2 proper parallel classes, and every edge in such a parallel class
is incident with u.
Then there is an immersion of Kd+1 in G.
Proof. Suppose (for a contradiction) that G is a counterexample to the theorem with |V |+
|E| minimum. We shall prove properties of G in several steps.
(1) |V | ≥ d+ 1.
It follows from the assumptions that there exists a vertex in V \ {u} not incident with
any proper parallel class. Consequently, |V | ≥ d+ 1.
(2) Every edge has an end of degree at most d.
If e has no end of degree ≤ d, then G− e is a smaller counterexample.
(3) deg(v) = d for every v ∈ N(u).
If v ∈ N(u) has degree > d, then G− uv is a smaller counterexample.
(4) deg(v) ≤ d+ 1 for every v ∈ V \ {u}.
If there exists v ∈ V \ {u} with deg(v) > d + 1, then either the neighbors of v form
a complete graph (giving us an immersion of Kd+1 in G) or there exist w1, w2 ∈ N(v)
which are nonadjacent, and the graph obtained from G by lifting vw1 and vw2 to form the
edge w1w2 is a smaller counterexample.
(5) N(u) induces a complete graph.
If v1, v2 ∈ N(u) are nonadjacent, then the graph obtained by lifting uv1 and uv2 to
form the edge v1v2 is a smaller counterexample.
(6) |N(u)| ≥ 3.
If |N(u)| ≤ 1, then G − u is a smaller counterexample. If |N(u)| = 2, then we
may let {v1, v2} = N(u) and assume that there are s edges between u, v1 and t between
u, v2 with s ≤ t. Now G immerses the graph G′ obtained from G by deleting u and
adding s new parallel edges between v1, v2, so G′ (with the special vertex v2) is a smaller
counterexample.
(7) |N(u)| ≤ d− 2.
If |N(u)| ≥ d, then (5) implies thatN(u) containsKd+1 as a subgraph, soG immerses
Kd+1. If |N(u)| = d − 1, let G′ be the graph obtained from G by identifying N(u) to a
single new vertex and deleting any resulting loops. More precisely, we replace V (N(u))
by a single vertex u′ and replace each edge vw (v ∈ N(u), w /∈ N(u)) by the edge u′w,
possibly obtaining multiple edges incident with u′. By using (3) and (5), it is easy to see
that each vertex in N(u) has precisely one neighbor outside N(u) and that the degree of
u′ is d − 1. This implies that G immerses the graph G′. Since immersion is a transitive
M. DeVos et al.: Immersing small complete graphs 143
relation, we conclude that G′ (with the special vertex u′) is a smaller counterexample. This
contradiction proves (7).
(8) d = 6 and |N(u)| = 3.
Suppose (for a contradiction) that (8) fails. By (6) and (7) we must have d ∈ {5, 6} and
|N(u)| = d− 2. Again in this case, we form a new graph G′ from G by identifying N(u)
to a single new vertex u′ and deleting any resulting loops. By the minimality of G we find
that G′ immerses Kd+1. This immersed Kd+1 in G′ can be used to find an immersion of
Kd+1 in G. The “hardest” case to verify is when d = 6, u′ has degree 8, and the immersed
K7 uses all of these edges, and has u′ as a vertex. Up to symmetries, there are two cases to
be considered, and they are conveniently displayed in Figure 1, where the black vertex and
the bold paths show the neighborhood of the immersed vertex of K7 and the dotted edges
show the segment of the additional subdivided edge that is passing through u′ in G′. This
yields a contradiction and completes the proof of (8).
Figure 1: Extending K7-immersion from G′ to G when |N(u)| = 4
(9) G does not have exactly one proper parallel class.
Suppose (for a contradiction) that N(u) = {v1, v2, v3} and that the edges between u
and v1 form the only proper parallel class in G. Now, form a new graph G′ by deleting
u and adding edges v1v2 and v1v3. The graph G′ is now immersed in G, and gives us a
smaller counterexample (using the special vertex v1).
(10) There do not exist w1, w2 ∈
⋂
v∈N(u)N(v) \ {u} so that either w1w2 ∈ E or
deg(w1) = 6 = deg(w2).
Suppose that such a pair w1, w2 exists and let us form the graph G′ from G by identi-
fying N(u) ∪ {w1, w2} to a single new vertex u′. It follows from (2)–(5) and (8) that u′
will have degree ≤ 9 (so G′ will have at most four proper parallel classes). Since N(u)
has at least one and at most three neighbors outside of N(u) ∪ {u,w1, w2}, it also follows
that G has a vertex that is not adjacent to N(u). This implies that G′ has at least 6 vertices.
Consequently, G′ contains an immersion of K7. This immersion of K7 in G′ can be used
to find an immersion of K7 in G. The “hardest” case is when eight of the edges incident
with u′ are used in the K7 and u′ is a vertex of the immersed K7. As for the most general
subcase, we may also assume that deg(u′) = 9. This case can be divided into subcases
depending on which pair of edges incident with u′ are lifted to form a new edge (drawn as
a broken bold curve in Figure 2). Up to symmetries, there are four subcases as shown in
Figure 2: both edges are incident with w1, one is incident with w1 and the other one with
w2, one withw1 and the other withN(u), or both withN(u). In Figure 2, bold paths repre-
sent partial routings for each of these four cases, up to symmetries. In each subcase, one or
144 Ars Math. Contemp. 3 (2010) 139–146
aa
a a
bcb
b bc
Figure 2: Extending K7-immersion from G′ to G for claim (10)
two of the edges incident with the vertex of degree 6 in K7 (drawn as the black vertex) are
still missing. In this way, each of these figures describes two or three additional subcases,
corresponding to which of the remaining edges a, b (or c) is not used in the K7-immersion.
It is easy to verify that all of these subcases can be completed to form an immersion of K7
in G.
(11) |
⋂
v∈N(u)N(v) \ {u}| ≤ 2.
Suppose (for a contradiction) that w1, w2, w3 ∈
⋂
v∈N(u)N(v) \ {u} are distinct. It
follows from (10) that {w1, w2, w3} is an independent set, and that at most one of these
vertices has degree 6. Now, form a new graphG′ fromG by deletingN(u) and then adding
the new edges w1w2, w2w3, and w3w1. The graph G′ is simple with at most one vertex
of degree < 6 and has at least 6 vertices, so it immerses K7. But then G immerses K7 as
well, since G′ is immersed in G. This yields a contradiction.
(12) Every v ∈ N(u) satisfies |N(v)| ≤ 5.
M. DeVos et al.: Immersing small complete graphs 145
LetN(u) = {v1, v2, v3} and suppose (for a contradiction) thatN(v3) = {u, v1, v2, w1,
w2, w3}. First suppose that v1w1, v2w2 6∈ E. Then the graph G′ obtained from G by
deleting v3 and adding the edges v1w1, v2w2, and uw3 is immersed in G, and yields a
smaller counterexample, a contradiction. Next suppose that v1w1, v1w2 6∈ E. By the
previous case, we may assume that v2w1, v2w2, v2w3 ∈ E. It follows from this that v2 and
v3 have six distinct neighbors, so by (9) the graph G is simple. Now, form the graph G′′
from G by deleting u and v3, then adding the edges v1w1 and v1w2, and then adding a new
edge v2w3 in parallel to the existing edge. The graph G′′ is immersed in G, but then G′′
with the special vertex v2 is a smaller counterexample, giving us a contradiction.
Using the two properties just demonstrated, we may now assume that v1w2, v1w3,
v2w2, v2w3 ∈ E. Further, by (11), we may assume that v1w1 6∈ E, and by (10) we
may assume that w2w3 6∈ E. Now we form the graph G′′′ from G by deleting v3 and then
adding the edges v1w1, w2w3, and uv2. Now G′′′ is immersed in G, but then G′′′ is a
smaller counterexample, giving us a contradiction. This proves (12).
Now, (12) implies that every neighbor of u is incident with a proper parallel class. It
follows from this and (3), (5), (8) that the graph obtained from G by identifying N(u)
to a single new vertex and deleting loops is immersed in G. This new graph is a smaller
counterexample, thus completing the proof.
References
[1] F. N. Abu-Khzam and M. A. Langston, Graph coloring and the immersion order, preprint.
[2] K. Appel and W. Haken, Every planar map is four colorable, Part I. Discharging, Illinois J.
Math. 21 (1977), 429–490.
[3] K. Appel, W. Haken and J. Koch, Every planar map is four colorable, Part II. Reducibility,
Illinois J. Math. 21 (1977), 491–567.
[4] B. Bollobás and P. A. Catlin, Topological cliques of random graphs, J. Combin. Theory Ser. B
30 (1981), 224–227.
[5] H. D. Booth, R. Govindan, M. A. Langston and S. Ramachandramurthis, Sequetial and parallel
algorithms for K4-immersion testing, J. Algorithms 30 (1999), 344–378.
[6] P. A. Catlin, A bound on the chromatic number of a graph, Discrete Math. 22 (1978), 81–83.
[7] P. Erdős and S. Fajtlowicz, On the conjecture of Hajós, Combinatorica 1 (1981), 141–143.
[8] M. R. Fellows and M. A. Langston, Nonconstructive tools for proving polynomial-time decid-
ability, J. ACM 35 (1998), 727–738.
[9] K. Kawarabayashi and B. Toft, Any 7-chromatic graph has K7 or K4,4 as a minor, Combina-
torica 25 (2005), 327–353.
[10] F. Lescure and H. Meyniel, On a problem upon configurations contained in graphs with given
chromatic number, Graph theory in memory of G. A. Dirac (Sandbjerg, 1985), 325–331, Ann.
Discrete Math. 41, North-Holland, Amsterdam, 1989.
[11] N. Robertson, D. P. Sanders, P. D. Seymour and R. Thomas, The four-color theorem, J. Combin.
Theory Ser. B 70 (1997), 2–44.
[12] N. Robertson and P. D. Seymour, Graph minors. XX. Wagner’s conjecture, J. Combin. Theory
Ser. B 92 (2004), 325–357.
[13] N. Robertson and P. D. Seymour, Graph Minors XXIII, Nash-Williams’ immersion conjecture,
submitted.
146 Ars Math. Contemp. 3 (2010) 139–146
[14] N. Robertson, P. D. Seymour and R. Thomas, Hadwiger’s conjecture for K6-free graphs, Com-
binatorica 13 (1993), 279–361.
[15] C. Thomassen, Some remarks on Hajós’ conjecture, J. Combin. Theory Ser. B 93 (2005), 95–
105.
[16] K. Wagner, Über eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937), 570–590.