# Does Cyclomatic or Cognitive Complexity Better Represents Code
Understandability? An Empirical Investigation on the Developers Perception

Valentina Lenarduzzi<EMAIL_ADDRESS>Terhi Kilamo
<EMAIL_ADDRESS>Andrea Janes<EMAIL_ADDRESS>University of Oulu,
Finland  Tampere University, Finland  FHV Vorarlberg University of Applied
Sciences, Austria

###### Abstract

Background. Code understandability is fundamental. Developers need to clearly
understand the code they are modifying. A low understandability can increase
the amount of coding effort and misinterpretation of code has impact on the
entire development process. Ideally, developers should write clear and
understandable code with the least possible effort.
Objective. The goal of this work is to investigate if the McCabe Cyclomatic
Complexity or the Cognitive Complexity can be a good predictor for the
developers’ perceived code understandability to understand which of the two
complexities can be used as criteria to evaluate if a piece of code is
understandable.
Method. We designed and conducted an empirical study among 216 junior
developers with professional experience ranging from one to four years. We
asked them to manually inspect and rate the understandability of 12 Java
classes that exhibit different levels of Cyclomatic and Cognitive Complexity.
Results. Cognitive Complexity slightly outperforms the Cyclomatic Complexity
to predict the developers’ perceived understandability.
Conclusion. The identification of a clear and validated measure for Code
Complexity is still an open issue. Neither the old fashioned McCabe Cyclomatic
Complexity and the most recent Cognitive Complexity are good predictors for
code understandability, at least when considering the complexity perceived by
junior developers.

###### keywords:

Cyclomatic Complexity , Cognitive Complexity , Empirical Study

††journal: Journal of Systems and Software††journal: Journal of Systems ans
Software

##  1 Introduction

Code understandability is the ability of software developers to comprehend and
effectively work with code written by others or by themselves in the past. In
other words, it refers to how easy it is to read and interpret a piece of
code.

Code understandability is an essential aspect of software development, as it
can greatly impact the efficiency and effectiveness of the development
process. When code is easy to understand, developers can more easily identify
and fix errors, modify existing code, and integrate new code into existing
projects. On the other hand, code that is difficult to understand can lead to
confusion, errors, and time-consuming troubleshooting.

There are several factors that contribute to code understandability, including
the use of clear and concise syntax, consistent formatting and naming
conventions, and well-organized code structure. Additionally, documentation
and comments can also play a crucial role in improving code understandability.

Code understandability can be defined as the measure to which “code possesses
the characteristic of understandability to the extent that its purpose is
clear to the inspector” [1]. Having a poor code understandability in the
program code can increase the amount of coding effort by more than 50% [2, 3]
and any misinterpretation of the code will influence the entire development
process. To avoid misinterpretation of the code, developers should write code
that requires the least amount of effort to be understood [4].

Different metrics, such as the McCabe Cyclomatic Complexity [5], and the
Cognitive Complexity [6] have been proposed in the past to evaluate the
complexity of the code. Current static analysis tools allow the developers to
keep track of these metrics in their code on real-time. Cognitive Complexity
has been introduced by SonarQube111 https://www.sonarqube.org as an extension
of the McCabe Cyclomatic Complexity, to better evaluate code understandability
[6]. The effect of Cognitive Complexity on code understandably was
investigated by two recent studies [7, 4]. Based on their results, Cognitive
Complexity seems to be a good indicator of understandability where a higher
value means a reduction of understandability. However, both studies did not
consider the opinion of the developers on the perceived complexity of the
code. Yet, we believe that only two studies (of which one was conducted by the
original authors of the Cognitive Complexity metric) are not enough to
demonstrate the effectiveness of a new metric. Moreover, as highlighted by
Munoz [4], the different complexity and understandability metrics are not
deeply investigated and validated. In particular, it is still not evident
which of the metrics better support the prediction of code understandability
[7].

As consequence, Lavazza et al. [8] extended [4] correlating Cognitive and
Cyclomatic complexity to identify which metric provides advantage for code
understandability. Unfortunately, the achieved results are not proposing for a
particular metric.

Code can be complex also due to problems in the code such as design issues or
code smells. As highlighted by Politowski et al. [9], the presence of anti-
patterns in the code can decrease the code understandability, and increase the
effort needed to modify the code. Therefore, if the complexity metrics are
correlated with code understandability, also problems in the code can be
correlated with the complexity measures.

Since the previous studies highlighted the need to understand whether
Cognitive complexity is correlated with understandability better than the
other existing metrics and the previous results, based on mining software
repository studies, were not able to tip the scales, we decided to investigate
the impact of these two metrics on code understandably from the point of view
of the developer’s perception.

To this purpose, we designed and conducted an empirical study involving 216
developers with at least one year of experience. We asked them to manually
inspect twelve Java classes that exhibit different levels of Cyclomatic and
Cognitive Complexity measured by SonarQube. The tasks requested for each class
were to rate the code understandability.

Moreover, if a positive correlation exists between complexity measures and
code understandability, we also aim at understanding if complexity measures
are correlated with the developers’ perceived severity of problems in the Java
code.

While there seems to be some differences between developers’ opinions on the
perception of complexity of the code, the overall data indicates that
Cognitive Complexity is a better indicator on the perceived understandability
of the code.

The paper is structured as follows: In Section 2 we introduce the background
of this work, while in Section 3 we outline the research methodology adopted
in this study. Section 4 presents and discusses the obtained results. Section
6 identifies the threats to validity, while Section 7 describes the related
work. Finally, Section 8 draws the conclusions.

##  2 Background

In this Section, we briefly describe the two complexity measures we considered
in this work. Both measures are included in the SonarQube suite.

###  2.1 Cyclomatic Complexity

Cyclomatic Complexity is a metric introduced by McCabe already in 1976 [5]. It
is a graph theoretical measure for program complexity. The idea behind
Cyclomatic Complexity is to measure the amount of linearly independent paths
in the program. It is based on the assumption that the more independent paths
there are in a program, the more complex the program is likely to be.

The definition of Cyclomatic Complexity is based on representing program code
as a control flow graph, i.e. a directed graph with all execution paths of the
program depicted. Each node in the graph represents a basic code block and
each edge a pass of control between the blocks. Based on the graph, Cyclomatic
Complexity $M$ is calculated as $M=E-N+P$ where $E$ is the number of edges,
$N$ the number of nodes and $P$ the number of strongly connected components in
the graph. While Cyclomatic Complexity is a widely used metric to indicate the
error proneness of program code, it fails to address certain code issues
especially when it comes to computational complexity. Cyclomatic Complexity is
poor at handling nested condition and iterative structures [10]. Also it has
been regarded as a poor metric for code understandability [6].

In SonarQube, the Complexity measure is calculated based on the Cyclomatic
Complexity of the code [11] where each split in the control flow of a function
increments the complexity measure by one. However, there are small differences
between languages in how the complexity gets calculated due to differences in
language structures.

Cyclomatic complexity can be used as an indicator of how difficult a program
is to test, maintain, or modify. Programs with high cyclomatic complexity are
generally more difficult to understand, analyze, and change, as they contain
more decision points and potential paths through the code. As such, cyclomatic
complexity is often used as a quality metric to evaluate the maintainability
and overall complexity of software programs.

###  2.2 Cognitive Complexity

Cognitive complexity is based on the idea that not all decision points in a
program are equally difficult for a human to understand. Some decisions are
simple and easy to reason about, while others are more complex and require
more mental effort. Therefore, cognitive complexity assigns a weight to each
decision point in the code based on its level of complexity, with more complex
decisions receiving a higher weight.

In SonarQube, Cognitive Complexity was introduced as “a new metric for
measuring the understandability of any given piece of code” [6]. Based on the
documentation [12], Cognitive Complexity exhibits some similarity with
Cyclomatic Complexity defined by McCabe [5], since Cognitive Complexity can
address some of the “common critiques and shortcomings belonging to Cyclomatic
Complexity” [10]. Moreover, Cognitive Complexity can fill the gap related to
understandability present in the Cyclomatic Complexity [6].

Investigating the construction model, Cognitive Complexity is based on three
basic rules [6]:

  1. 1.

“Ignore structures that allow multiple statements to be readably shorthanded
into one”;

  2. 2.

“Increment for each break in the linear flow of the code”;

  3. 3.

“Increment when flow-breaking structures are nested”.

The first rule implicates to obtain no increment of complexity for a method
declaration or null-coalescing operators like “??” in C# or PHP, to not
penalize developers writing shorter code than those using the operators
written on multiple lines.

The second rule increments complexity whenever the flow of statements is
broken, i.e., [6]:

  * •

switch, if, else if, else, ternary operator

  * •

for, foreach, while, do while

  * •

catch

  * •

goto LABEL, break LABEL, continue LABEL

  * •

sequences of like binary logical operators

  * •

each method in a recursion cycle.

The last rule increases the complexity value to take the level of nesting of
control flow structures into account. The following structures increment the
nesting level [6]:

  * •

switch, if, else if, else, ternary operator

  * •

for, foreach, while, do while

  * •

catch

  * •

nested methods and method-like structures

##  3 The Empirical Study

We designed and conducted an empirical study by following the guideline
proposed by Runeson and Höst [13]. In this section, we present the goal, the
research questions, metrics and hypotheses for the empirical study. We outline
the study context, the data collection and the data analysis.

###  3.1 Goal and Research Questions

The goal of this study is to compare cyclomatic complexity and cognitive
complexity with the _purpose_ of understanding which complexity metric better
represents the developer’s perceived complexity of the Java code. The
_perspective_ is of researchers, since they are interested in understanding
what complexity metrics can be more helpful to understand the code complexity.

Based on the aforementioned goal, we derived the following Research Questions:

RQ1:

Which complexity metric has a higher correlation with the perceived
understandability level of a given developer for a specific code snippet?

RQ2:

Is there a correlation between the complexity metrics and the perceived
severity of an existing problem in the code?

These research questions are further divided into the following sub-research
questions:

RQ1.1:

What is the correlation between the Cyclomatic Complexity and the perceived
understandability level of a given developer for a specific code snippet?

RQ1.2:

What is the correlation between the Cognitive Complexity and the perceived
understandability level of a given developer for a specific code snippet?

RQ2.1:

Is there a correlation between Cyclomatic Complexity and the perceived
severity of existing problems in the code?

RQ2.2:

Is there a correlation between Cognitive Complexity and the perceived severity
of existing problems in the code?

In RQ1, we investigated correlations between perceived code understandability
and Cyclomatic (RQ1.1) and Cognitive (RQ1.2) complexities. The goal of this
question is to understand if it is possible to use only one of the two
complexities to represent code understandability. In particular, since
Cognitive Complexity is considered a “more contextualized form of quantitative
data on code complexity”, we are interested to understand if Cognitive
Complexity is a better predictor for the code understandability. Since the
Cognitive Complexity was build upon the Cyclomatic Complexity, we hypothesized
that it might better represent the code understandability.

Complex code is considered hard to modify [2, 3]. Moreover, code affected by
high levels of Cyclomatic Complexity is usually affected by more severe
problems [2, 3]. Therefore, in our second research question (RQ2), we aim at
understanding if Cognitive Complexity can better represent the severity of the
problems in the code (RQ2.2) compared to Cyclomatic Complexity (RQ2.1).

Moreover, we considered that a lower code understandability can lead to a
misleading in the problem identification in the inspected code and,
consequently, a wrong perception of its severity (RQ2).

###  3.2 Empirical Study Design

To answer our research questions, we designed our empirical study consisting
of the five steps below. Fig. 1 illustrates the process using the Business
Process Model and Notation (BPMN) [14] specification language.

  1. 1.

Code Selection: We selected Java code affected by problems of different
severity from Apace Software Foundation projects.

  2. 2.

Complexity measurement: We measured the Cyclomatic and Cognitive Complexity of
the selected Java code using SonarQube.

  3. 3.

Developers selection: we identified the junior developers to be included in
our study.

  4. 4.

Code inspection: We asked developers to inspect the selected Java code and to
provide their opinion on the understandability of the code, on the presence of
issues, and to rate the severity of the existing problem, if any.

  5. 5.

Data Analysis: We analyzed the developers’ answers and correlated the
developer’s perceived understandability with the Cyclomatic and Cognitive
Complexity.

Figure 1: Empirical study design process

In the remainder of this Section, we describe the all aforementioned steps in
detail.

####  3.2.1 Code Selection

In this section, we report the case and subject selection for this study. We
selected classes written in Java affected by different problems that can
influence code understandably from Apace Software Foundation projects. Two of
three authors, together with a senior Java developer, evaluated independently
the presence of issues in the code. Then, all the three persons discussed
possible inconsistencies and finally defined a list of 12 classes where all of
them agree on the presence of the same issues (Table 2). More details of the
selected classes and of the problems identified in the code are available in
Table 1.

Table 1: Validated problem in the selected cases

Class |  Validated problem in the code
---|---
C1 |  Maintainability low because of code smells present in the code
[1pt/1pt] C2 |  As C1, and in addition, cognitive complexity exceeds threshold defined by SonarQube
[1pt/1pt] C3 |  Code is not tested
[1pt/1pt] C4 |  As C2, and in addition, code contains faults
[1pt/1pt] C6 |  Duplicated code
[1pt/1pt] C5 |  Combination of C1 (constants missing) and C6
[1pt/1pt] C7 |  Variation of C1 with a higher criticality (unimplemented functions)
[1pt/1pt] C8 |  Variation of C1 with a lower criticality
[1pt/1pt] C9 |  Code smell: exception handling
[1pt/1pt] C10 |  Code is not tested
[1pt/1pt] C11 |  Code is not tested
[1pt/1pt] C12 |  Minor code smell

  * •

Details about the classes (name and path) are available in the replication
package4

####  3.2.2 Complexity Measurement.

We measured the code complexity by means of Cognitive Complexity and
Cyclomatic Complexity applying SonarQube version 7.51.

####  3.2.3 Developers Selection

As for participants, we selected junior developers. The reason for selecting
them, instead of senior developers, is because they are the developers that
most frequently need to approach new code. In particular, junior developers
commonly need to extend existing code in the company they work, fixing bugs or
integrating new features. Therefore, we selected master or bachelor students
in their last year of studies, with at least one year of experience as
developer in a company. The selected participants, are exactly these
developers that are working on existing code and that need to understand
problems in the code when extending it or when they are fixing bugs.

We finally involved 216 junior developers with an experience in Java that
range from one to four years.

We did not present to the participants the Cyclomatic Complexity and Cognitive
Complexity values, in order not to influence them in their ability to
recognize a potential design problem only because they see the complexity
values in advance.

Table 2: Selected classes

Class | Cyclomatic Complexity | Cognitive Complexity
---|---|---
C1 | 37 | 38
[1pt/1pt] C2 | 130 | 73
[1pt/1pt] C3 | 113 | 36
[1pt/1pt] C4 | 56 | 68
[1pt/1pt] C5 | 57 | 3
[1pt/1pt] C6 | 35 | 6
[1pt/1pt] C7 | 110 | 0
[1pt/1pt] C8 | 23 | 6
[1pt/1pt] C9 | 2 | 1
[1pt/1pt] C10 | 6 | 0
[1pt/1pt] C11 | 7 | 1
[1pt/1pt] C12 | 3 | 0

  * •

Details about the classes (name and path) are available in the replication
package4

####  3.2.4 Code Inspection.

We asked developers to manual inspect the 12 Java classes and provide their
opinion about the code understandability. To collect the information, we
organized the questionnaire into four sections:

  * •

Respondents’ Background. We collected the profile of the respondents
considering development experience.

  * •

Code Inspection. In this section of the questionnaire we asked participants to
manually inspect a Java class and provide their opinion about their perceived
Code Understandability through a five-point Likert Scale (1 means “very easy”
and 5 means “very difficult”).

  * •

Perceived Problem Criticality in the code, reporting if the problem exists in
the class and rating their severity through a five-point Likert Scale (1 means
“very low severity” and 5 means “very high severity”).

We implemented the questionnaire using Google Forms. The Questionnaire is
available in the replication package4.

Table 3: Questions about code inspection’s section RQ | Question | Answer type
---|---|---
RQ1 | How easy is it to understand the code of this class? | Five-point scales
[1pt/1pt] RQ2 | Does, in your opinion, this class has design, coding style, or any other problems? | Yes/No
If YES, please rate the severity of the problem | Five-point Likert Scales

###  3.3 Study Execution

We provided the participants the instructions describing how to access the
classes and how to answer the survey. The participants were allowed to inspect
the classes and fill out the online questionnaire in a single round. We
informed the participants, according to the GDPR222https://gdpr-info.eu, about
their rights and that they can abandon the study anytime. Moreover, all
information provided by each participant have been treated as confidential,
without disclosing any sensible data, such as name and surname.

###  3.4 Data Analysis

Concerning the results of the code inspection phase, we first verified the
participants’ background analyzing the distribution of their education level
(bachelor or master) and their experience as developers in software companies.

To answer our RQ, we first quantitatively analyzed the perceived code
understandability reported by the developers.

Then, we investigated the correlations between the perceived code
understandability (dependent variable) and the Cyclomatic Complexity (RQ1.1)
and Cognitive Complexity (RQ1.2) as independent variables. We adopted the
Spearman rank correlation coefficient $\rho$ [15], which measures how well a
monotonic function can be fitted between two groups of values measured from
the same samples. This is a non-parametric method and the values of $\rho$
range between -1 and 1, where 1 means perfect positive monotonic association,
-1 means perfect negative monotonic association, and 0 means there is no
monotonic association between the groups.

For interpreting the other values of $\rho$, we followed the guideline
suggested by Cohen [16]: no correlation if $0\leq\rho<0.1$, small correlation
if $0.1\leq\rho<0.3$, medium correlation if $0.3\leq\rho<0.5$, and large
correlation if $0.5\leq\rho\leq 1$. Corresponding limits apply for negative
correlation coefficients. We determined the statistical significance of the
correlations checking p-values, that should be lower than 0.05 (significance
level alpha). Therefore, we adopted the value of $\rho$ to compare the
correlations obtained in (RQ1.1) and (RQ1.2). To enable to visualize the key
value of our results, we plotted the results with box-plots.

We applied statistical tests to verify whether the differences are
statistically significant. Since the data are not normally distributed, we
exploited the Friedman Test with the Nemenyi post-hoc test [17] on all the
machine learning models. This is a post-hoc test that identifies the groups of
data that differ after a statistical test of multiple comparisons has rejected
the null hypothesis (the groups are similar), making a pair-wise performance.
We selected this test because it is robust to multiple comparisons - which is
our case since we had to compare multiple models on multiple features. To
conduct the statistical analysis, we used the Nemenyi package for Python333The
Nemenyi Python package: https://scikit-posthocs.readthedocs.io/en/latest/..

Then, we first manually validated if the problems reported by the developers
in the code refer to actual problems in the code (Table 1). As for (RQ2), the
qualitative data analysis has been conducted individually by each author.
Moreover, in order to to get a fair/good agreement on the first iteration of
this process, pairwise inter-rater reliability was measured across the three
sets of decisions. Based on the disagreements, we clarified possible
discrepancies and different classifications. A second iteration resulted in
100% agreement among all the authors.

We conducted the next analysis only for the cases where participants correctly
identified a problem in the code.

We analyzed the correlations between the perceived problem severity (dependent
variable) and the Cyclomatic Complexity (RQ2.1) and Cognitive Complexity
(RQ2.2) as independent variables with the Spearman rank correlation
coefficient $\rho$ [15], following the same approach adopted in (RQ1.1).

###  3.5 Replicability

In order to allow our study to be replicated, we have published the complete
raw data together with the instruction of the assignment and the complete
questionnaire in the replication
package444https://figshare.com/s/0044c83c4fcb45dd831f.

##  4 Results

In this section, we report the results obtained answering our RQs. We
collected information from 216 students.

Background Information. The respondents were 170 master students (79%) and 46
(21%) were bachelor students. 96 (79.34%) of them had between 1 and 2 years of
developing experience, while the remaining 25 (20.66%) had more than 3 and 4
years (Table 4).

Table 4: Background Information Role | Developer Experience
---|---
Bachelor |  21% |  less than 2 years |  84%
[1pt/1pt] Master |  79% |  3 and 4 years |  16%

###  4.1 Which is the correlation between complexity metrics and the perceived
code understandability (RQ1)

As we can see from Table 5, the respondents considered the vast majority of
the classes (83%) neither to easy (median 3) or hard to understand (median 3),
while the remaining classes (C3 and C4) are easy to understand (median 2).

As evidence on the application on Cognitive Complexity as an understandability
measure is scarce, we set out to study how junior developers perceive code
with different Cyclomatic and Cognitive Complexity levels. Our results
indicate that cognitive complexity seems a better indicator on severity across
developers and that while there is quite a lot of variance cognitive
complexity also is better agreed on as a complexity indicator. It was evident
that less complex classes were considered easy to understand indicating that
low Cyclomatic and Cognitive Complexity supports understandability of the
code. However, if Cyclomatic or Cognitive Complexity was high, the opinion on
understandability was varied.

This is a very interesting result and requires further investigation. It does
seem that low Cognitive Complexity makes the code more understandable despite
the high Cyclomatic Complexity but reducing the Cognitive Complexity does not
make the understandability of the code universally better for all developers.
What is especially eyeopening is that having both complexity measures high,
the perception on understandability varied.

Understandability appears to be a little more correlated with Cognitive
Complexity. However, the difference to Cyclomatic Complexity was not drastic.
The developers were more agreed on Cognitive Complexity as a complexity
measure which means that it could be more useful of the two. Prior results [7,
18] have indicated that the metrics themselves do not indicate
understandability.

Investigating the correlation between the overall code understandability and
the Cyclomatic and Cognitive Complexities, results are statistical
significant, since p-values is equal to 0.000 (Table 6). Overall, both metrics
are not correlated with the perceived problem ($\tau$ equal to 0.364 for
Cyclomatic and 0.466 for Cognitive [16]).

Table 5: Perceived Code Understandability (RQ1) Class id. | Perc. Understandability | # respondent |  Mode
---|---|---|---
C1 | 1-Very Easy | 20 |  3
2-Easy | 54 |
3-Neither Easy or Hard | 76 |
4-Hard | 42 |
5-Very Hard | 8 |
[1pt/1pt] C2 | 1-Very Easy | 48 |  2
2-Easy | 55 |
3-Neither Easy or Hard | 58 |
4-Hard | 28 |
5-Very Hard | 3 |
[1pt/1pt] C3 | 1-Very Easy | 51 |  2
2-Easy | 49 |
3-Neither Easy or Hard | 58 |
4-High | 29 |
5-Very Hard | 7 |
[1pt/1pt] C4 | 1-Very Easy | 27 |  3
2-Easy | 46 |
3-Neither Easy or Hard | 65 |
4-Hard | 40 |
5-Very Hard | 12 |
[1pt/1pt] C5 | 1-Very Easy | 22 |  4
2-Easy | 35 |
3-Neither Easy or Hard | 67 |
4-Hard | 49 |
5-Very Hard | 23 |
[1pt/1pt] C6 | 1-Very Easy | 8 |  3
2-Easy | 21 |
3-Neither Easy or Hard | 34 |
4-Hard | 72 |
5-Very Hard | 60 |
[1pt/1pt] C7 | 1-Very Easy | 18 |  4
2-Easy | 35 |
3-Neither Easy or Hard | 61 |
4-Hard | 52 |
5-Very Hard | 29 |
[1pt/1pt] C8 | 1-Very Easy | 7 |  4
2-Easy | 14 |
3-Neither Easy or Hard | 39 |
4-Hard | 50 |
5-Very Hard | 83 |
[1pt/1pt] C9 | 1-Very Easy | 29 |  4
2-Easy | 29 |
3-Neither Easy or Hard | 38 |
4-Hard | 35 |
5-Very Hard | 66 |
[1pt/1pt] C10 | 1-Very Easy | 10 |  4
2-Easy | 18 |
3-Neither Easy or Hard | 35 |
4-Hard | 52 |
5-Very Hard | 75 |
[1pt/1pt] C11 | 1-Very Easy | 6 |  4
2-Easy | 10 |
3-Neither Easy or Hard | 31 |
4-Hard | 57 |
5-Very Hard | 88 |
[1pt/1pt] C12 | 1-Very Easy | 6 |  4
2-Easy | 19 |
3-Neither Easy or Hard | 28 |
4-Hard | 51 |
5-Very Hard | 92 |
Figure 2: Perceived Code Understandability distribution (RQ1) Table 6: Code
Understandability - Spearman correlation (RQ1) Complexity
---
Spearman | Cyclomatic | Cognitive
r | 0.364 | 0.466
[1pt/1pt] p-value | 0.000 | 0.000
Figure 3: Correlation between complexity metrics and the perceived code
understandability (RQ1)

###  4.2 Which complexity metric better represents the severity of an existing
problem in the code (RQ2)

To answer RQ2, we first investigated if they perceived a design or coding
style problem and if they correctly detected and identified it.

Perceived design or coding style problem. The percentage of respondents than
consider a class affected by a design or coding style problem is less than
75%.

Design coding style problem identification. It is interesting to note that,
almost all the participants that identified a problem in the classes,
correctly identified at least one of the actual problems. The only exception
is for classes C7 and C12 not all the developers provided a description.
77.85% of them correctly identified the correct problem for C7 and 89%
considering C12 class. Table 7 shows the results for the identification of the
problems grouped by Class (C).

Therefore, as also highlighted by Table 7, we can conclude that the
understandability of the code is independent from the perception of a problem.

Table 7: Problem identification and description and Perceived Severity (RQ2) Class | Problem |  Mode
---|---|---
Perceived | Described | Severity |
# |  % |  # |  % |  # |  # |
C1 |  146 |  69 |  146 |  100 |  1-Very Easy |  5 |  3
2-Easy |  11 |
3-Neither Easy or Hard |  25 |
4-Hard |  24 |
5-Very Hard |  16 |
[1pt/1pt] C2 |  159 |  75 |  159 |  100 |  1-Very Easy |  7 |  3
2-Easy |  29 |
3-Neither Easy or Hard |  23 |
4-Hard |  21 |
5-Very Hard |  8 |
[1pt/1pt] C3 |  154 |  74 |  154 |  100 |  1-Very Easy |  9 |  3
2-Easy |  21 |
3-Neither Easy or Hard |  35 |
4-Hard |  16 |
5-Very Hard |  10 |
[1pt/1pt] C4 |  127 |  60 |  127 |  100 |  1-Very Easy |  8 |  3
2-Easy |  17 |
3-Neither Easy or Hard |  17 |
4-Hard |  21 |
5-Very Hard |  12 |
[1pt/1pt] C5 |  145 |  69 |  145 |  100 |  1-Very Easy |  11 |  3
2-Easy |  17 |
3-Neither Easy or Hard |  21 |
4-Hard |  22 |
5-Very Hard |  15 |
[1pt/1pt] C6 |  81 |  38 |  81 |  100 |  1-Very Easy |  4 |  4
2-Easy |  5 |
3-Neither Easy or Hard |  9 |
4-Hard |  11 |
5-Very Hard |  21 |
[1pt/1pt] C7 |  149 |  71 |  116 |  78 |  1-Very Easy |  9 |  3
2-Easy |  10 |
3-Neither Easy or Hard |  24 |
4-Hard |  24 |
5-Very Hard |  13 |
[1pt/1pt] C8 |  60 |  28 |  60 |  100 |  1-Very Easy |  0 |  4
2-Easy |  4 |
3-Neither Easy or Hard |  8 |
4-Hard |  8 |
5-Very Hard |  17 |
[1pt/1pt] C9 |  96 |  46 |  75 |  78 |  1-Very Easy |  6 |  4
2-Easy |  9 |
3-Neither Easy or Hard |  11 |
4-Hard |  9 |
5-Very Hard |  20 |
[1pt/1pt] C10 |  39 |  19 |  39 |  100 |  1-Very Easy |  1 |  4
2-Easy |  4 |
3-Neither Easy or Hard |  5 |
4-Hard |  3 |
5-Very Hard |  10 |
[1pt/1pt] C11 |  53 |  25 |  53 |  100 |  1-Very Easy |  1 |  5
2-Easy |  0 |
3-Neither Easy or Hard |  5 |
4-Hard |  9 |
5-Very Hard |  16 |
[1pt/1pt] C12 |  89 |  42 |  55 |  62 |  1-Very Easy |  1 |  4
2-Easy |  6 |
3-Neither Easy or Hard |  10 |
4-Hard |  15 |
5-Very Hard |  20 |

Design or coding style problem severity. The participants rated how concerned
they were with respect to the design problem identified in the inspected code
for each class. The participants rated their evaluation based on a 5-point
Likert scale (1 means “very low” and 5 means “very high”).

Table 7 shows the obtained results grouped by Class (C), 5-point Likert scale
levels (from 1 to 5), and number of respondents. We report the average and the
median of the perceived Severity. Almost all the respondents that perceived a
problem in the inspected classes considered it at least with a medium severity
(median 3).

Figure 4: Perceived Severity Problem distribution (RQ2) Table 8: Perceived
Problem Severity - Spearman correlation (RQ2) Complexity
---
Spearman | Cyclomatic | Cognitive
r | -0.268 | -0.152
[1pt/1pt] p-value | 0.000 | 0.001
Figure 5: Correlation between complexity metrics and the perceived severity of
the design problem - (RQ2)

##  5 Discussion

As evidence on the application on Cognitive Complexity as an understandability
measure is scarce, we set out to study how junior developers perceive code
with different Cyclomatic and Cognitive Complexity levels. Our results
indicate that cognitive complexity seems a better indicator on severity across
developers and that while there is quite a lot of variance cognitive
complexity also is better agreed on as a complexity indicator.

It was evident that less complex classes were considered easy to understand
indicating that low Cyclomatic and Cognitive Complexity supports
understandability of the code. However, if Cyclomatic or Cognitive Complexity
was high, the opinion on understandability was varied. This is a very
interesting result and requires further investigation. It does seem that low
Cognitive Complexity makes the code more understandable despite the high
Cyclomatic Complexity but reducing the Cognitive Complexity does not make the
understandability of the code universally better for all developers. What is
especially eyeopening is that having both complexity measures high, the
perception on understandability varied. Understandability appears to be a
little more correlated with Cognitive Complexity. However, the difference to
Cyclomatic Complexity was not drastic. The developers were more agreed on
Cognitive Complexity as a complexity measure which means that it could be more
useful of the two.

Prior results [8, 7, 18] have indicated that the metrics themselves do not
indicate understandability and that the different proposed metrics are not
positive correlated [8]. Based on our findings low complexity measures do seem
to indicate good understandability but having either Cognitive or Cyclomatic
high, makes understandability unpredictable. Moreover, out results also
confirm that both complexity metrics are also not correlated with the
perceived severity of the problems in the code.

When looking into RQ2 the increased complexity increased the perception on
severity as well. However, there was large variance especially with Cyclomatic
Complexity.

The perception on the code issues was good among the junior developers. If the
class was considered to be affected by a design problem the developers are
also able to describe what the problem is. This shows that highlighting the
issues contributing to complexity measures can help in keeping
understandability high. The understandability, however, is not dependent on
the type of the problem. This may indicate that the developers should take
also the more minor design issues more seriously.

##  6 Threats to Validity

In this Section, we introduce the threats to validity, following the structure
suggested by Yin [19], reporting construct validity, internal validity,
external validity, and reliability. Moreover, we will also discuss the
different tactics adopted to mitigate them.

Construct validity. Concerning the set of tasks, we considered classes whose
code complexity was measured by the same tool (SonarQube) that allows to
compute both complexities considered in this work (cyclomatic and cognitive
complexities). We checked each question to avoid potential misunderstandings,
negative questions, and threats. The perceived priority of the design problem
was collected by asking the participants to first describe the problem they
perceived to understand if their perception is actually related to the
identified problem and not to other potential issue in the code. We asked the
participants to rate the severity of the problem by means of a Likert scale,
to allow us to compare the responses based on an homogeneous scale. To reduce
this threat, we checked the correctness of the identification both manually
and by means of automated tools.

Internal Validity. Considering the respondents, we selected junior developers
with maximum 4 years of experience in programming skills to better focus on
our goal. However, we are aware that the results could be biased by the
selection of participants belonging to a set of developers more deeply trained
in this tasks.

External validity. It can be concerned to the subjects of the study and the
selected objects. To mitigate this threat, we adopted a treatment set of
classes measure was possible to use the same tool to measured cognitive and
cyclomatic complexities. Moreover, we are aware that further studies with
different analyzed classes considering also the missing groups are needed to
confirm our results.

Conclusion validity. Conclusion validity focuses on how sure we can be that
the tasks we adopted are related to the actual outcome we observed. The survey
were checked by three experts on empirical studies. Moreover, it was ensured
that the subjects of both groups had similar backgrounds and knowledge
regarding code understandability and code inspection.

##  7 Related Work

Code understandability is described as the measure of how well “code possesses
the characteristic of understandability to the extent that its purpose is
clear to the inspector” [1]. To better understand a piece of code, legibility
is one of the main factors to take under control, since if code is harder to
read, it could be harder to understand [1]. Code understanding requires
building high-level abstractions from code statements or visualizations or
models [20, 21]. However, also readable code could be difficult to be
understand [7].

Code understandability can be measured considering several different factors.
One possibility is based on the perceived understandability reported by
developers answering comprehension questions [22, 23], or filling out blank
program parts [24], or extending and/or modifying existing piece of code [25].
To be more accurate, some studies traced the time to perform the assigned
task, both questions or developing ones [18, 26, 25]. Other approaches
evaluate code understandability focusing on physiological metrics detected by
biometrics sensors [27, 28] or eye-tracking devices [29, 30].

Moreover, considering the perceived understandability by rating the different
pieces of code under analysis, can provide a positive step forward in this
field [7]. Different factors can positively or negatively influence how
developers perceive the understandability of a piece of code [7], that can be
useful to develop a model to automatically measure the understandability.

Several studies investigated the role of software metrics focusing on
complexity as well as source-level metrics, such as LOC [7] and Cyclomatic
Complexity [31, 7] or Cognitive Complexity [6] during the developing process
or during maintenance tasks [18]. Moreover, other types of metrics such as
documentation related metrics such as comment readability and metrics relating
to a developer’s experience were considered from researchers [7]. Results
showed that none of the investigated metrics accurately represent code
understandability [18, 7]. However, all the software metrics considered in
these studies suffered of empirical validation of their ability to measure
code understandability. In particular, Cognitive Complexity needs more
accurate validation [6]. However, the results demonstrated that such metrics
can improve the effectiveness of the code understandability under evaluation
[7].

A deeper investigation of Cognitive Complexity has been performed by Munoz et
al. [4] and later by Lavazza et al. [8]. Munoz et al. [4] considered as
Cognitive Complexity the metric measured by SonarQube and evaluated the
association with different code understandability metrics: the time taken to
understand a code snippet, the percentage of correctly answered comprehension
questions on a code snippet, subjective ratings of a comprehension task, and
physiological measures on the subjects engaged in understanding code. Results
showed that Cognitive Complexity is correlated with the time spent by a
developer to understand source code. However, they did not compared the
magnitude of this correlation against different complexity metrics. As Lavazza
et al. [8] reported in their work “before embracing the use of Cognitive
Complexity, we need to understand whether Cognitive Complexity is really
correlated with understandability better than the measures that were proposed
in the past for the same purpose”. To assess it, Lavazza et al. [8] conducted
an empirical study extending study [4]. They correlated Cognitive and
Cyclomatic complexity to identify which metric provides advantage for code
understandability. Unfortunately, the achieved results are not proposing for a
particular metric.

##  8 Conclusion

We designed and conducted a case study among 216 junior developers (bachelor
and master level students). We asked them to manually inspect 12 Java classes
that exhibit different code complexity levels as Cognitive and Cyclomatic
Complexity measured by SonarQube. For each class, developers had to rate the
code understandability.

Our finding show that Cognitive Complexity better represents the code
understandability than Cyclomatic Complexity, even if its correlation with the
code understandability is not high.

  * •

Cognitive Complexity better represents the code understandability than
Cyclomatic Complexity, even if its correlation with the code understandability
is not high.

  * •

The severity problems in the code are not correlated with the complexity (both
Cyclomatic and Cognitive). We expected to find more problems in classes with
higher levels of complexities, mainly because we were expecting these classes
to be harder to understand. Therefore, we cannot claim that classes with a
higher Cyclomatic or Cognitive complexity are affected by more severe problems
than these with lower levels of complexity.

Future works will include a replication of this work with more developers
asking them to suggest the refactoring action in order to fix the identified
problem. Moreover, future work will include the comparison between the
perceived understandability of the code of junior and senior developers, and
the consideration of other programming languages such as Python and
Javascript.

## References

  * Boehm et al. [1976] B. W. Boehm, J. R. Brown, M. Lipow,  Quantitative Evaluation of Software Quality,  in: 2nd International Conference on Software Engineering, ICSE ’76, IEEE Computer Society Press, 1976, pp. 592–605.
  * Minelli et al. [2015] R. Minelli, A. Mocci, M. Lanza,  I Know What You Did Last Summer - An Investigation of How Developers Spend Their Time,  in: 23rd International Conference on Program Comprehension, pp. 25–35.
  * Xia et al. [2018] X. Xia, L. Bao, D. Lo, Z. Xing, A. E. Hassan, S. Li,  Measuring Program Comprehension: A Large-Scale Field Study with Professionals,  IEEE Transactions on Software Engineering 44 (2018) 951–976.
  * Muñoz Barón et al. [2020] M. Muñoz Barón, M. Wyrich, S. Wagner,  An Empirical Validation of Cognitive Complexity as a Measure of Source Code Understandability,  in: International Symposium on Empirical Software Engineering and Measurement (ESEM).
  * McCabe [1976] T. J. McCabe,  A Complexity Measure,  IEEE Transactions on Software Engineering SE-2 (1976) 308–320.
  * Campbell [2018] G. A. Campbell,  Cognitive Complexity - An Overview and Evaluation,  in: International Conference on Technical Debt (TechDebt’18), pp. 57–58.
  * Scalabrino et al. [2019] S. Scalabrino, G. Bavota, C. Vendome, M. Linares-V?squez, D. Poshyvanyk, R. Oliveto,  Automatically Assessing Code Understandability,  IEEE Transactions on Software Engineering (2019) 1–1.
  * Lavazza et al. [2023] L. Lavazza, A. Z. Abualkishik, G. Liu, S. Morasca,  An empirical evaluation of the “Cognitive Complexity” measure as a predictor of code understandability,  Journal of Systems and Software 197 (2023) 111561.
  * Politowski et al. [2020] C. Politowski, F. Khomh, S. Romano, G. Scanniello, F. Petrillo, Y.-G. Guéhéneuc, A. Maiga,  A large scale empirical study of the impact of Spaghetti Code and Blob anti-patterns on program comprehension,  Information and Software Technology 122 (2020) 106278.
  * Suleman Sarwar et al. [2013] M. M. Suleman Sarwar, S. Shahzad, I. Ahmad,  Cyclomatic complexity: The nesting problem,  in: Eighth International Conference on Digital Information Management (ICDIM 2013), pp. 274–279.
  * SonarSource [2022] SonarSource, Metric Definitions, https://docs.sonarqube.org/latest/user-guide/metric-definitions/, accessed on July 28, 2022.
  * Campbell [2022] G. A. Campbell, Cognitive Complexity, a new way of measuring understandability, https://www.sonarsource.com/docs/CognitiveComplexity.pdf, accessed on July 28, 2022.
  * Runeson and Höst [2009] P. Runeson, M. Höst,  Guidelines for Conducting and Reporting Case Study Research in Software Engineering,  Empirical Softw. Engg. 14 (2009).
  * OMG [2011] OMG, Business Process Model and Notation (BPMN), Version 2.0, 2011.
  * Student [1921] Student,  An Experimental Determination of the Probable Error of Dr Spearman’s Correlation Coefficients,  Biometrika 13 (1921) 263.
  * Cohen [1988] J. Cohen,  Statistical power analysis for the behavioral sciences,  Lawrence Earlbaum Associates 2 (1988).
  * Nemenyi [1962] P. Nemenyi,  Distribution-free multiple comparisons,  in: Biometrics, volume 18, p. 263\.
  * Feigenspan et al. [2011] J. Feigenspan, S. Apel, J. Liebig, C. Kastner,  Exploring Software Measures to Assess Program Comprehension,  in: International Symposium on Empirical Software Engineering and Measurement, pp. 127–136.
  * Yin [2014] R. Yin, Case Study Research: Design and Methods, 5th Edition, SAGE Publications, Inc, 5th edition, 2014.
  * Storey et al. [2000] M.-A. Storey, K. Wong, H. Muller,  How do program understanding tools affect how programmers understand programs?,  Science of Computer Programming 36 (2000) 183–207.
  * Lin and Wu [2006] J. Lin, K. Wu,  A Model for Measuring Software Understandability,  in: International Conference on Computer and Information Technology, pp. 192–192.
  * Dolado et al. [2003] J. J. Dolado, M. Harman, M. C. Otero, L. Hu,  An empirical investigation of the influence of a type of side effects on program comprehension,  IEEE Transactions on Software Engineering 29 (2003) 665–670.
  * Salvaneschi et al. [2014] G. Salvaneschi, S. Amann, S. Proksch, M. Mezini,  An Empirical Study on Program Comprehension with Reactive Programming,  in: International Symposium on Foundations of Software Engineering, pp. 564–575.
  * Borstler and Paech [2016] J. Borstler, B. Paech,  The Role of Method Chains and Comments in Software Readability and Comprehension—An Experiment,  IEEE Transactions on Software Engineering 42 (2016) 886–898.
  * Hofmeister et al. [2017] J. Hofmeister, J. Siegmund, D. V. Holt,  Shorter identifier names take longer to comprehend,  in: 24th International Conference on Software Analysis, Evolution and Reengineering (SANER), pp. 217–227.
  * Aljunid et al. [2012] S. Aljunid, A. Zin, Z. Shukur,  A Study on the Program Comprehension and Debugging Processes of Novice Programmers,  Journal of Software Engineering 6 (2012) 1–9.
  * Fucci et al. [2019] D. Fucci, D. Girardi, N. Novielli, L. Quaranta, F. Lanubile,  A Replication Study on Code Comprehension and Expertise using Lightweight Biometric Sensors,  in: 27th International Conference on Program Comprehension (ICPC), pp. 311–322.
  * Yeh et al. [2017] M. K. . Yeh, D. Gopstein, Y. Yan, Y. Zhuang,  Detecting and comparing brain activity in short program comprehension using EEG,  in: IEEE Frontiers in Education Conference (FIE), pp. 1–5.
  * Fritz et al. [2014] T. Fritz, A. Begel, S. C. Müller, S. Yigit-Elliott, M. Züger,  Using Psycho-Physiological Measures to Assess Task Difficulty in Software Development,  in: Int. Conference on Software Engineering, pp. 402–413.
  * Turner et al. [2014] R. Turner, M. Falcone, B. Sharif, A. Lazar,  An Eye-Tracking Study Assessing the Comprehension of C++ and Python Source Code,  in: Symposium on Eye Tracking Research and Applications, pp. 231–234.
  * Kasto and Whalley [2013] N. Kasto, J. Whalley,  Measuring the Difficulty of Code Comprehension Tasks Using Software Metrics,  in: Fifteenth Australasian Computing Education Conference - Volume 136, pp. 59–65.


# Subcubic graphs of large treewidth do not have the edge-Erdős-Pósa property

Henning Bruhn and Raphael Steck

###### Abstract

We show that subcubic graphs of treewidth at least $2500$ do not have the
edge-Erdős-Pósa property.

##  1 Introduction

Menger’s theorem provides a strong duality between packing and covering for
paths: In every graph $G$, there are either $k$ disjoint paths between
predefined sets $A,B\subseteq V(G)$, or there is a set $X\subseteq V(G)$ of
size at most $k$ such that $G-X$ contains no $A$–$B$ path. Relaxed versions of
this result exist for many sets of graphs, and we call this duality the
_Erdős-Pósa property_. In this article, we focus on the edge variant: A class
$\mathcal{F}$ has the _edge-Erdős-Pósa property_ if there exists a function
$f:{\mathbb{Z}}_{+}\rightarrow\mathbb{R}$ such that for every graph $G$ and
every integer $k$, there are $k$ edge-disjoint subgraphs of $G$ each
isomorphic to some graph in $\mathcal{F}$ or there is an edge set $X\subseteq
E(G)$ of size at most $f(k)$ meeting all subgraphs of $G$ isomorphic to some
graph in $\mathcal{F}$. The edge set $X$ is called the _hitting set_. If we
replace vertices with edges in the above definition, that is, if we look for a
vertex hitting set or vertex-disjoint graphs, then we obtain the _vertex-
Erdős-Pósa property_. The class $\mathcal{F}$ that is studied in this article
arises from taking minors: For a fixed graph $H$, we define the set
$\mathcal{F}_{H}=\\{G\,:\,H\text{ is a minor of }G\\}.$ Any graph
$G\in\mathcal{F}_{H}$ is called an _$H$ -expansion_.

The vertex-Erdős-Pósa property for $\mathcal{F}_{H}$ is well understood:
Robertson and Seymour [7] proved that the class $\mathcal{F}_{H}$ has the
vertex-Erdős-Pósa property if and only if $H$ is planar. While both the
vertex- and the edge-Erdős-Pósa property are false for all non-planar graphs
$H$ (see for example [6]), the situation is much more mysterious for planar
graphs. For some simple planar graphs $H$ such as long cycles[2] or
$K_{4}$[1], $\mathcal{F}_{H}$ still has the edge-Erdős-Pósa property, while
for some others, for example subcubic trees of large pathwidth[3], it does
not. For most planar graphs, it is unknown whether the edge-Erdős-Pósa
property holds or not. For an overview of results on the Erdős-Pósa-property,
we recommend the website of Jean-Florent Raymond [5].

We partially fill this gap by proving that for every subcubic graph of large
treewidth $H$, $\mathcal{F}_{H}$ does not have the edge-Erdős-Pósa property.
Note that while it was known that large walls do not have the edge-Erdős-Pósa
property (claimed without proof in [3]), this does not imply our main result
as, unlike the vertex-Erdős-Pósa property, is not known whether the edge
variant is closed under taking minors.

######  Theorem 1.

For subcubic graphs $H$ of treewidth at least $2500$, $\mathcal{F}_{H}$ does
not have the edge-Erdős-Pósa property.

To prove Theorem 1, we only use treewidth to deduce that $H$ contains a large
wall, for which we use the linear bound provided by Grigoriev [4]. So in fact,
we show the following theorem:

######  Theorem 2.

For subcubic graphs $H$ that contain a wall of size $250\times 250$,
$\mathcal{F}_{H}$ does not have the edge-Erdős-Pósa property.

There is room for improvement in the theorem. Requiring the graph $H$ to be
subcubic simplifies the argument considerably, but we suspect it is not
necessary. Moreover, we believe that with a more careful but somewhat tedious
analysis the wall size could be dropped to about $30\times 30$. Still, this
seems unlikely to be close to be best possible. Indeed, walls of size $6\times
4$ do not have the edge-Erdős-Pósa property [8]. (Whether graphs containing
$6\times 4$-walls have the property is not known.)

##  2 Construction

There is only one known tool to prove that a set $\mathcal{F}_{H}$ of
$H$-expansions that satisfies the vertex-Erdős-Pósa property does not have the
edge-Erdős-Pósa property: The _Heinlein Wall_ , after [3], shown at size 5 in
Figure 1.

$c^{*}$$d^{*}$$a^{*}$$b^{*}$ Figure 1: A Heinlein Wall of size 5.

For any integer $n\in{\mathbb{Z}}_{+}$, we define $[n]=\\{1,\ldots,n\\}$. A
Heinlein Wall $W$ of size $r\in{\mathbb{Z}}_{+}$ is the graph consisting of
the following:

  * •

For every $j\in[r]$, let $P^{j}=u^{j}_{1}\ldots u^{j}_{2r}$ be a path of
length $2r-1$ and for $j\in\\{0\\}\cup[r]$, let $z_{j}$ be a vertex. Moreover,
let $a^{*}$, $b^{*}$ be two further vertices.

  * •

For every $i,j\in[r]$, add the edges
$z_{j-1}u^{j}_{2i-1},z_{j}u^{j}_{2i},z_{i-1}{z_{i}},a^{*}u^{j}_{1}$ and
$b^{*}u^{j}_{2r}$.

We define $c^{*}=z_{0}$ and $d^{*}=z_{r}$. We call the vertices
$a^{*},b^{*},c^{*}$ and $d^{*}$ _terminals_ of $W$, while the vertices
$z_{j},j\in\\{0\\}\cup[r]$ are called _bottleneck vertices_. Additionally, we
define $W^{0}=W-\\{a^{*},b^{*},c^{*},d^{*}\\}$.

An _( $a^{*}$–$b^{*}$, $c^{*}$–$d^{*}$) linkage_ is the vertex-disjoint union
of an $a^{*}$–$b^{*}$ path with a $c^{*}$–$d^{*}$ path. We need an easy
observation:

######  Lemma 3 (Bruhn et al [3]).

There are no two edge-disjoint ($a^{*}$–$b^{*}$, $c^{*}$–$d^{*}$) linkages in
a Heinlein Wall.

For $m,n\in{\mathbb{Z}}_{+}$, an _elementary grid_ of size $m\times n$ is a
graph with vertices $v_{i,j}$ for all $i\in[m],j\in[n]$ and edges
$v_{i,j}v_{i+1,j}\,\,\forall i\in[m-1],j\in[n]$ as well as
$v_{i,j}v_{i,j+1}\,\,\forall i\in[m],j\in[n-1]$. A _grid_ is a subdivision of
an elementary grid.

A wall is the subcubic variant of a grid. We define an elementary wall as an
elementary grid with every second vertical edge removed. That is, an
elementary wall of size $m\times n$ is an elementary grid of size
$(m+1)\times(2n+2)$ with every edge $v_{i,2j}v_{i+1,2j}\,,i\in[m],i\text{ is
odd},j\in[n+1]$ and every edge $v_{i,2j-1}v_{i+1,2j-1}\,,i\in[m],i\text{ is
even},j\in[n+1]$ being removed. Additionally, we remove all vertices of degree
$1$ and their incident edges. The _$i^{\text{th}}$ row_ of an elementary wall
is the induced subgraph on $v_{i,1},\ldots,v_{i,2n+2}$ for $i\in[m+1]$ (ignore
the vertices that have been removed); this is a path. There is a set of
exactly $n+1$ disjoint paths between the first row and the $(m+1)^{\text{th}}$
row. These paths are the _columns_ of an elementary wall. The _bricks_ of an
elementary wall are its $6$-cycles. (See Figure 2)

$1$st rowcolumnrowbrick Figure 2: An elementary wall of size $8\times 8$.

A _wall_ is defined as the subdivision of an elementary wall. However,
elementary walls have some vertices of degree $2$ on the outer face of the
wall. As we never want to distinguish between graphs that only differ by
subdivision of edges, we avoid some annoying technicalities by slightly
modifying the above definition. We define a _wall’_ of size $m\times n$ as the
subdivision of an elementary wall of size $m\times n$ with all degree $2$
vertices being contracted. (See Figure 3)

Figure 3: An elementary wall of size $4\times 3$ and a wall’ of the same size.

Throughout, we will use this slightly modified definition of a wall. The key
properties of a wall, such as large treewidth and planarity, carry over to a
wall’. The definition of rows, columns and bricks in an elementary wall
carries over to a wall’ in a natural way (with some truncation of the first
and last row and column). For brevity of notation, we define an _$n$ -wall’_
as a wall’ of size $n\times n$.

The _outercycle_ of a wall’ $W$ is the cycle $C$ contained in $W$ that
contains the first and last row and first and last column. Two vertices $u,v$
of $W$ are _$d$ -apart in $W$_ if every $u$–$v$ path in $W$, every $u$–$C$
path and every $v$–$C$ path in $W$ intersects at least $d+1$ rows or at least
$d+1$ columns of $W$. We extend the definition to bricks by saying that two
bricks $B_{1},B_{2}$ of $W$ are _$d$ -apart in $W$_ if every pair of one
vertex from $B_{1}$ and one vertex from $B_{2}$ is $d$-apart in $W$. Note that
if $v_{1},v_{2}$ are $d$-apart and if $v_{1}$ lies in the brick $B_{1}$, and
$v_{2}$ in the brick $B_{2}$ then $B_{1},B_{2}$ are $(d-2)$-apart.

Note, furthermore, that if $W$ is part of a planar graph $G$ then there are no
shortcuts in $G$. That is, if $u,v$ are $d$-apart in $W$ then there is also no
$u$–$v$ path _in_ $G$ that meets fewer than $d+1$ rows and columns of $W$, and
the same holds true for paths from $u$ or $v$ to the outercycle.

To apply Menger’s theorem, for $n\in{\mathbb{Z}}_{+}$ and vertex sets $A$ and
$B$ in a graph $G$, we define an _$n$ -separator_ as a vertex set $X\subseteq
V(G)$ of size $|X|\leq n$ such that there is no $A$–$B$ path in $G-X$. We will
usually apply this for one side being a single vertex, that is $A=\\{a\\}$, in
which case we additionally require that $a\not\in X$.

##  3 Large treewidth results

How do we prove our main result? Let $H$ be a planar subcubic graph of
treewidth $\geq 2500$. Given a size $r$ of a hypothetical hitting set, we show
that there is a graph $Z$ that neither contains two edge-disjoint subdivisions
of $H$, nor admits an edge set $U$ of size $|U|\leq r$ such that $Z-U$ is
devoid of subdivisions of $H$. That then proves that $\mathcal{F}_{H}$ does
not have the edge-Erdős-Pósa property.

Since $H$ has treewidth $\geq 2500$, it contains a grid-minor of size at least
$501\times 501$ [4] and thus a wall’ $M$ of size at least $250\times 250$. We
pick two edges $e_{1}$ and $e_{2}$ of $M$ such that both of them are incident
with a branch vertices of degree $3$ of $M$ and such that

every pair of one endvertex from $e_{1}$ and one endvertex from $e_{2}$ is
$70$-apart in $M$. (1)

As $H$ is planar and $M$ large enough it is possible to find such edges
$e_{1},e_{2}$. We denote the endvertex of $e_{1}$ that is also a branch
vertices of degree $3$ of $M$ by $a$, and the other endvertex by $b$ (which
may, or not, be a branch vertex, too). For $e_{2}$, we call its endvertices
$c$ and $d$, where $c$ is chosen to be a branch vertex of degree $3$ of $M$.

$a^{*}$$b^{*}$$c^{*}$$d^{*}$$M^{*}$$a^{*}$$b^{*}$$c^{*}$$d^{*}$$W$$g^{*}$$h^{*}$$Z$
Figure 4: Construction of the counterexample graph $Z$

Given a positive integer $r$, we define $Z$ as follows:

  * •

start with a copy of $H-\\{e_{1},e_{2}\\}$, where we denote the copy of a
vertex $h$ of $H$ by $h^{*}$;

  * •

replace every edge $g^{*}h^{*}$ in the copy of $H-\\{e_{1},e_{2}\\}$ by $2r$
internally disjoint $g^{*}$–$h^{*}$ paths of length $2$; and

  * •

add a Heinlein wall $W$ of size $2r$, where the terminals $a^{*},b^{*}$ of $W$
are identified with the endvertices of $e_{1}$, and where the terminals
$c^{*},d^{*}$ are identified with the endvertices of $e_{2}$.

A depiction of $Z$ can be seen in Figure 4.

We extend the mapping $V(H)\to V(Z)$ defined by $h\mapsto h^{*}$ to sets of
vertices in $H-\\{e_{1},e_{2}\\}$: for a vertex set $J\subseteq V(H)$, we set
$J^{*}=\\{h^{*}:h\in J\\}$.

To better to distinguish between $H$ and $Z$, we use the first half of the
alphabet ($a$–$m$) for vertices, vertex sets and graphs that are part of $H$,
while the second half of the alphabet ($o$–$z$) is reserved for objects
belonging to $Z$. Starred letters of the first half ($a^{*}$–$m^{*}$) are used
for vertices and objects in $Z$ that have counterparts in $H$. We define
$M^{*}$ to be an arbitrary subdivision of $M-\\{e_{1},e_{2}\\}$ in $Z$ such
that the set of its branch vertices is precisely $(V(M))^{*}$ and such that
each subdivided edge of $M^{*}$ consists of one of the $2r$ paths originating
from multiplying the corresponding edge of $M-\\{e_{1},e_{2}\\}$. Note that
$M^{*}$ is a wall’ except for $e_{1},e_{2}$, and note that $M^{*}$ is disjoint
from $W^{0}$.

Let us first prove the first half of Theorem 1: there is no small edge hitting
set in $Z$.

######  Lemma 4.

For every edge set $U$ in $Z$ of size $|U|\leq r$, the graph $Z-U$ contains a
subdivision of $H$.

###### Proof.

As for every edge $gh\in E(H)\setminus\\{e_{1},e_{2}\\}$, the vertices $g^{*}$
and $h^{*}$ are linked by $2r$ internally disjoint paths, we may easily find a
subdivision of $H-\\{e_{1},e_{2}\\}$ in $Z-U$. Moreover, $U$ is too small to
meet all ($a^{*}$–$b^{*}$, $c^{*}$–$d^{*}$) linkages in the Heinlein wall $W$.
Thus, the subdivision of $H-\\{e_{1},e_{2}\\}$ can be extended to one of $H$
in $Z-U$. ∎

The harder part of Theorem 1 is to prove that there can be no two edge-
disjoint subdivisions of $H$ in $Z$. We will prove:

######  Lemma 5.

Every subdivision of $H$ in $Z$ contains an ($a^{*}$–$b^{*}$, $c^{*}$–$d^{*}$)
linkage in $W$.

Recall that, by Lemma 3, any two such linkages share an edge. Thus, once we
have shown the above lemma, we then have finished the proof of the theorem.

When we talk about a subdivision of $H$ in $Z$, we implicitly assume that an
_embedding_ of $H$ into $Z$ is fixed: a function $\Phi$ that maps every vertex
of $H$ to the corresponding branch vertex in $Z$, and that maps every edge of
$H$ to the corresponding subdivided edge in $Z$. We will extend such an
embedding $\Phi$ to subgraphs of $H$ in the obvious way. In particular,
$\Phi(H)$ then denotes the subdivision of $H$ in $Z$.

For the remainder of this article, we assume $\Phi$ to be a fixed embedding of
$H$ in $Z$. We will prove Lemma 5 for this fixed embedding of $H$. The main
difficulty is that we do not know how $H$ embeds in $Z$. In order to get some
control on what is mapped where by $\Phi$, we concentrate on a set of vertices
that are well connected to large walls’. We will later see that only a small
number of them can be mapped into $W$. We define a _$3$ -fan_ from a vertex
$v$ to a set $S$ as the union of three non-trivial paths from $v$ to $S$ that
are disjoint except for their first vertex $v$. Set

$\displaystyle B=\\{$ $\displaystyle h\in V(H)\,:\,\text{there is $10$-wall'
$M^{\prime}$ and}$ $\displaystyle\text{a $3$-fan from $h$ to the branch
vertices of degree~{}$3$ of $M^{\prime}$}\\}.$

Note that $M$ is also a $10$-wall’.

######  Lemma 6.

Not all branch vertices of any $10$-wall’ can be contained in $W$.

###### Proof.

It is easy to check that a Heinlein Wall has pathwidth at most $5$, and thus
also treewidth at most $5$. Therefore, it cannot contain a $10$-wall’ since
the latter has treewidth at least $10$. ∎

As we are only ever interested in branch vertices of degree $3$, we will call
those _proper branch vertices_. Moreover, a _proper branch vertex_ of $M^{*}$
is the image under the $*$-map of a proper branch vertex of $M$. Note that
every proper branch vertex of every $10$-wall’ $M^{\prime}$ is in $B$: Indeed,
every proper branch vertex in $M^{\prime}$ is connected to its three adjacent
proper branch vertices of $M^{\prime}$, and those paths form the desired
$3$-fan. In particular, this implies that every proper branch vertex of $M$ is
in $B$. Recall that by choice of $e_{1}$ and $e_{2}$, this includes $a$ and
$c$. For $b$ and $d$, we do not know, but the following lemma helps to deal
with them.

######  Lemma 7.

Let $h^{*}\in V(Z-W)$ and let $T\subseteq Z$ be a $3$-fan from $h^{*}$ to the
union of the proper branch vertices of $M^{*}$ with $\\{b^{*},d^{*}\\}$. Then
there is also a $3$-fan from $h$ to proper branch vertices of $M$ in $H$.

###### Proof.

To prove the lemma, we need to show two things: First, we need to find a
$3$-fan that is disjoint from $W^{0}$ so we can pull it back to $H$. Second,
we need to get rid of $b$ and $d$ and find a $3$-fan that connects $h$ with
proper branch vertices of $M$ only.

Since the terminals $a^{*}$ and $c^{*}$ of $W$ are proper branch vertices of
$M^{*}$ and since $h^{*}\not\in V(W)$, we can shorten the $3$-fan $T$ to
obtain a $3$-fan that is disjoint from $W^{0}$ but still connects $h^{*}$ with
proper branch vertices of $M^{*}$ or $b^{*}$ or $d^{*}$ if necessary. Since
this $3$-fan is disjoint from $W^{0}$, we can find a corresponding $3$-fan $F$
in $H$ that connects $h$ with proper branch vertices of $M$ or $b$ or $d$.

By Menger’s theorem, we may assume that $h$ can be separated in $H$ from the
proper branch vertices of $M$ by a set $K\subseteq V(H)\setminus\\{h\\}$ of at
most two vertices; otherwise we are done. In particular, the $3$-fan $F$ has
to contain at least one of $b$ and $d$; let us say it contains $b$. Moreover,
the $h$–$b$ path $L_{b}$ in $F$ cannot meet $K$ as $K$ already has to meet the
two other paths in the $3$-fan $F$. We are done if $b$ is a proper branch
vertex itself. Thus we may assume that there is a unique subdivided edge $E$
of $M$ that contains $b$ in its interior. One endvertex of $E$ is $a$. The set
$K$ also has to separate $b$ from the endvertices of $E$ (as we can reach $b$
from $h$ via $L_{b}$ without meeting $K$), which implies $K\subseteq V(E)$,
and $a\in K$ as $b$ is a neighbour of $a$. This implies $a\in V(F)$. Now
consider the $h$–$a$ path $L_{a}$ in $F$, and observe that $L_{a}$ is
internally disjoint from $K$ as $a\in K$. Furthermore, since $b\not\in
V(L_{a})$, the penultimate vertex of $L_{a}$ is a neighbour $g\neq b$ of $a$.
Then, as $H$ is subcubic, $g$ lies on a subdivided edge $E^{\prime}$ of $M$
that is not $E$. By extending $hL_{a}g$ along $E^{\prime}$ to the endvertex of
$E^{\prime}$ that is not $a$, we obtain a path from $h$ to a proper branch
vertex of $M$ that avoids $E$. Since $K\subseteq V(E)$, that path also avoids
$K$, a contradiction. ∎

The next lemma gives us control over $\Phi$, at least for the set $B$.

######  Lemma 8.

$\Phi(B)\subseteq B^{*}\cup V(W)$.

###### Proof.

Consider a vertex $z\in\Phi(B)\setminus V(W)$. First observe that, by
definition of $B$, every vertex in $\Phi(B)$ has degree at least $3$ in $Z$.
Thus, for $z$ there is a vertex $h$ of $H$ with $z=h^{*}$. We will show that
$h\in B$, which then implies $z=h^{*}\in B^{*}$.

As $h^{*}\in\Phi(B)$, there is a vertex $g\in B$ with $h^{*}=\Phi(g)$. Since
$g\in B$, there is a $3$-fan in $\Phi(H)$ connecting $h^{*}$ to the set of
proper branch vertices of a $10$-wall’ $R\subseteq\Phi(H)$. We define $O$ to
be the union of this fan and $R$. If $O$ is disjoint from the proper branch
vertices of $M^{*}$ and also disjoint from $b^{*}$ and $d^{*}$, then it is
also disjoint from $W^{0}$ and we can find a corresponding wall’ and fan in
$H$, implying that $h\in B$. (When pulling back from $Z$ to $H$, paths between
proper branch vertices of $R$ can become shorter, so that the resulting graph
in $H$ may be missing some of the required degree $2$ vertices to be
considered a wall; this is precisely the reason why we make do with walls’.)
Therefore, we conclude that $O$ contains some proper branch vertex of $M^{*}$
(and thus potentially also a part of $W^{0}$) or that $O$ contains $b^{*}$ or
$d^{*}$.

Next, suppose that there is no $2$-separator that separates $h^{*}$ from all
proper branch vertices of $M^{*}$ and from $b^{*}$ and $d^{*}$ in $Z$. By
Menger’s theorem, there is thus a $3$-fan from $h^{*}$ to the proper branch
vertices of $M^{*}$ or $b^{*}$ or $d^{*}$. We apply Lemma 7 to obtain a
$3$-fan in $H$ from $h$ to proper branch vertices of $M$ only, which proves
$h\in B$.

We conclude that there is a $2$-separator $\\{x,y\\}\subseteq V(Z-h^{*})$ that
separates $h^{*}$ from all proper branch vertices of $M^{*}$ and all terminals
of $W$. As every vertex of degree $3$ in $O$ is connected via three internally
disjoint paths to $h^{*}$, we deduce that there is an $x$–$y$ path $P$ in $O$
that contains all vertices that are separated by $\\{x,y\\}$ from $h^{*}$ in
$O$ and such that all interior vertices of $P$ have degree $2$ in $O$. As $O$
contains a proper branch vertex of $M^{*}$ or a terminal, the path $xPy$ must
contain a vertex from $(V(M))^{*}$. Pick $p,q$ to be the first respectively
the last vertex of $(V(M))^{*}$ on $P$, and choose a $p$–$q$ path $Q$ in
$M^{*}$. Note that $Q$ is disjoint from $O-pPq$ since $O\cap M^{*}\subseteq
pPq$. Moreover, note that $Q$ is disjoint from $W^{0}$ as $M^{*}$ is disjoint
from $W^{0}$. Replacing $pPq$ by $Q$, we obtain a new graph $O^{\prime}$ that
is the union of a $10$-wall’ $R^{\prime}$ with a $3$-fan from $h^{*}$ to the
branch vertices of $R^{\prime}$ that is disjoint from $W^{0}$. We then also
find in $H$ a $3$-fan from $h$ to the branch vertices of a $10$-wall’, which
again leads to $h\in B$. ∎

With the next two lemmas we show that, with only a few exceptions, a vertex in
$B$ is mapped to a vertex in $B^{*}$ under $\Phi$.

######  Lemma 9.

$|B^{*}\setminus\Phi(B)|=|\Phi(B)\cap(V(W)\setminus B^{*})|$

###### Proof.

By Lemma 8, we have

$\displaystyle|\Phi(B)\cap B^{*}|+|\Phi(B)\cap(V(W)\setminus B^{*})|$
$\displaystyle=|\Phi(B)|=|B|=|B^{*}|$
$\displaystyle=|B^{*}\cap\Phi(B)|+|B^{*}\setminus\Phi(B)|.$

∎

######  Lemma 10.

$|B^{*}\setminus\Phi(B)|\leq 52$.

###### Proof.

By Lemma 9, it suffices to show that $|\Phi(B)\cap(V(W)\setminus B^{*})|\leq
52$. We show that $|\Phi(B)\cap V(W^{0})|\leq 48$, which proves the above
claim since $V(W)\setminus B^{*}$ may differ from $V(W^{0})$ only in the $4$
terminals of $W$.

Let $z\in\Phi(B)\cap V(W^{0})$, and let $h$ be such that $z=\Phi(h)$. By
definition of $B$, $h$ has a $3$-fan to proper branch vertices of a $10$-wall’
$M^{\prime}$ in $H$. By Lemma 6, some proper branch vertex of $M^{\prime}$
needs to be mapped outside $W$ under $\Phi$. Then, however, there is a $3$-fan
$T_{z}\subseteq\Phi(H)$ from $z$ to a set of vertices in $Z-W$. This $3$-fan
must contain at least three terminals of $W$, and thus at least one of $a^{*}$
and $b^{*}$.

Since $z\in V(W^{0})$, it lies in one or possibly two blocks of
$W-\\{a^{*},b^{*}\\}$. We say that a block $O$ of $W-\\{a^{*},b^{*}\\}$ _owns_
a vertex $z\in\Phi(B)\cap V(W^{0})$ if $z$ is incident in $\Phi(H)$ with at
least two edges of $O$. As each $z\in\Phi(B)\cap V(W^{0})$ has degree $3$,
every vertex in $\Phi(B)\cap V(W^{0})$ is owned by exactly one block of
$W-\\{a^{*},b^{*}\\}$.

Now, assume that the block $O$ owns $z$. If $z$ is not a bottleneck vertex,
then the three paths in $T_{z}$ cannot all leave $O$ through its two
bottleneck vertices: one such path traverses an edge between $O$ and $a^{*}$
or $b^{*}$. The same happens if $z$ is a bottleneck vertex: then the two paths
in $T_{z}$ with an edge in $O$ cannot both leave $O$ through the remaining
bottleneck vertex. Therefore, whenever a block $O$ owns a vertex in $\Phi(B)$,
there must be an edge between $O$ and $\\{a^{*},b^{*}\\}$ in $\Phi(H)$. As
$a^{*},b^{*}$ both have degree at most $3$ in $\Phi(H)$, at most six blocks
may own vertices in $\Phi(B)$.

How many vertices in $\Phi(B)$ may be owned by a block $O$ of
$W-\\{a^{*},b^{*}\\}$? Every $z\in\Phi(B)\cap V(W^{0})$ that is not a
bottleneck vertex must have a bottleneck vertex as its neighbour in $\Phi(H)$
since $z$ has degree $3$, see Figure 1. As each bottleneck vertex has degree
at most $3$ in $\Phi(H)$, we conclude that each block contains at most six
non-bottleneck vertices of $\Phi(B)$. Together with the two bottleneck
vertices, we obtain $\leq 8$ vertices of $\Phi(B)$ per block. As at most six
blocks may own vertices in $\Phi(B)$, we obtain at most $48$ vertices in
blocks of $W-\\{a^{*},b^{*}\\}$. Together with the terminals, this yields
$|\Phi(B)\cap(V(W)\setminus B^{*})|\leq 52$. ∎

Define $B_{M}$ to be the set of all vertices in $H$ that send a $3$-fan to
proper branch vertices of $M$. We note that $B_{M}$ contains all proper branch
vertices of $M$, and $B_{M}\subseteq B$.

######  Lemma 11.

Let $h^{*}$ be a vertex in $Z-W$ with a $3$-fan $T\subseteq Z$ to vertices in
$B^{*}_{M}$. Then $h\in B_{M}$.

###### Proof.

Suppose there is a set $X$ of at most two vertices that separates $h^{*}$ from
all proper branch vertices of $M^{*}$ in $Z$. Because $X$ cannot separate
$h^{*}$ from all three endvertices of $T$, there exists a path $P$ in $Z-X$
between $h^{*}$ and some vertex $g^{*}\in B_{M}^{*}$. As there is, by
definition, a $3$-fan from $g$ to proper branch vertices of $M$ in $H$, there
is also $3$-fan from $g^{*}$ to proper branch vertices of $M^{*}$ in $Z$, and
then, as $|X|\leq 2$, also a path $Q$ from $g^{*}$ to a proper branch vertex
of $M^{*}$ in $Z-X$. However, $P\cup Q$ is disjoint from $X$ but contains a
path from $h^{*}$ to a proper branch vertex of $M^{*}$, which is impossible.

Therefore, by Menger’s theorem, there is a $3$-fan $T^{\prime}$ from $h^{*}$
to proper branch vertices of $M^{*}$. By Lemma 7, we obtain $h\in B_{M}$. ∎

In conjunction with Lemma 10, the next lemma will be used to repair $M$, that
is to prove that $\Phi(H)$ contains most proper branch vertices of $M^{*}$ and
sufficient subdivided edges in between them.

######  Lemma 12.

Let $g,h\in B_{M}$, and let $L$ be a $g$–$h$ path in $H-e_{1}-e_{2}$. Let $P$
be a $g^{*}$–$h^{*}$ path in $Z$ such that $V(P)\cap(V(H))^{*}=(V(L))^{*}$ and
such that $P$ is disjoint from $B^{*}\setminus\Phi(B)$. For every vertex
$i^{*}\in V(P)$ that is a terminal, we furthermore require that $i^{*}$ has
degree $2$ in $\Phi(H)-W^{0}$. Let $\mathcal{S}$ be the set of all
$B^{*}_{M}$-paths in $Z$ that are disjoint from the interior of $P$ and that
have at most one endvertex with $P$ in common. Then there is a $g^{*}$–$h^{*}$
path $Q$ in $\Phi(H)-W^{0}$ that is internally disjoint from every path in
$\mathcal{S}$.

###### Proof.

We do induction on the number $n$ of internal vertices of $P$ that lie in
$B^{*}_{M}$. Because it is shorter, we start with the induction step. Thus,
assume that $n>0$, ie that $P$ contains an internal vertex $k^{*}\in
B^{*}_{M}$. We split the path $P$ into $P_{1}=g^{*}Pk^{*}$ and
$P_{2}=k^{*}Ph^{*}$, and observe that both paths have fewer than $n$ internal
vertices in $B^{*}_{M}$. As subpaths of $P$, the paths $P_{1}$ and $P_{2}$
still satisfy the conditions of the lemma. Now induction yields a
$g^{*}$–$k^{*}$ path $Q_{1}\subseteq\Phi(H)-W^{0}$ and a $k^{*}$–$h^{*}$ path
$Q_{2}\subseteq\Phi(H)-W^{0}$. Let $Q$ be a $g^{*}$–$h^{*}$ path contained in
$Q_{1}\cup Q_{2}\subseteq\Phi(H)-W^{0}$.

Consider a path $S\in\mathcal{S}$, and suppose that $S$ meets $Q$ in an
internal vertex of $Q$. We first note that $S$ cannot contain $k^{*}$ as any
path in $\mathcal{S}$ is disjoint from the interior of $P$. Thus, $S$ meets an
internal vertex of $Q_{1}$ or of $Q_{2}$, say of $Q_{1}$. This, however, is
impossible as $S$ is disjoint from the interior of $P_{1}$, and may have at
most one endvertex with $P_{1}$ in common. Therefore, $Q$ is as desired, and
we have proved the induction step.

It remains to establish the induction start. Then, $n=0$, which implies that:

No internal vertex of $P$ lies in $B^{*}_{M}$. (2)

As $P$ is disjoint from $B^{*}\setminus\Phi(B)$, we get $g^{*}\in\Phi(B)$.
Thus, there is a $10$-wall’ $R$ and a $3$-fan from $g^{*}$ to proper branch
vertices of $R$ in $\Phi(H)$. We denote by $O$ the union of $R$ and this
$3$-fan. Note that $O$ is a subgraph of $\Phi(H)$.

Let us prove that:

For any neighbour $g_{0}$ of $g$ in $H-e_{1}-e_{2}$, the vertex $g_{0}^{*}$
lies in $O$.  (3)

Indeed, since $H$ is subcubic and since $g^{*}$ has degree $3$ in $O$ it
follows that for every neighbour $g_{0}$ of $g$ in $H$, we have $g^{*}_{0}\in
V(O)$ — unless $g^{*}$ is a terminal. Then, since $g\in B_{M}$, $g$ has degree
$2$ in $H-e_{1}-e_{2}$, and by assumption, $g^{*}$ has degree $2$ in
$\Phi(H)-W^{0}$: again, for every neighbour $g_{0}$ of $g$ in $H-e_{1}-e_{2}$,
the vertex $g_{0}^{*}$ lies in $O$.

Let $g_{1}$ be the neighbour of $g$ in $H-e_{1}-e_{2}$ that lies in $L$, the
$g$–$h$ path in $H$. It now follows from (3) that:

For the neighbour $g_{1}$ of $g$ in $L$ it holds that $g_{1}^{*}\in V(O\cap
P)$. (4)

Among all vertices in $O\cap P$, pick $k^{*}$ to be closest to $h^{*}$ on $P$.
Note that since $g_{1}^{*}\in V(P)$, it is a candidate for $k^{*}$. Thus we
immediately have $k^{*}\neq g^{*}$.

Next, we claim:

$k^{*}\in B^{*}_{M}$ (5)

Suppose not. In particular, $k^{*}\neq h^{*}$ as $h^{*}\in B^{*}_{M}$. By
Lemma 11, there are two vertices $x_{1},x_{2}\neq k^{*}$ that separate $k^{*}$
from $B^{*}_{M}$. As $k^{*}Ph^{*}$ is a $k^{*}$–$B^{*}_{M}$ path, one of
$x_{1},x_{2}$ lies in $k^{*}Ph^{*}$, say $x_{1}$. By choice of $k^{*}$, the
subpath $k^{*}Ph^{*}$ meets $O$ only in $k^{*}$, which implies that
$x_{1}\not\in V(O)$. In $O$ there are two internally disjoint $k^{*}$–$g^{*}$
paths. Since $x_{1}\not\in V(O)$, one of the two internally disjoint
$k^{*}$–$g^{*}$ paths in $O$ is disjoint from $x_{1},x_{2}$ unless
$x_{2}=g^{*}$. We thus conclude $x_{2}=g^{*}$.

Next, as $g^{*}\in B^{*}_{M}$ by assumption, it follows that there exists a
$3$-fan $T$ from $g^{*}$ to $B^{*}_{M}$ in $Z$. Since $H$ is subcubic, for two
neighbours $g_{1},g_{2}$ of $g$ in $H-e_{1}-e_{2}$, $g_{1}^{*}$ and
$g_{2}^{*}$ lie on different paths of the $3$-fan $T$ from $g^{*}$ to
$B^{*}_{M}$ in $Z$. That is, there are disjoint paths $P_{1},P_{2}$, where
$P_{1}$ is a $g_{1}^{*}$–$B_{M}^{*}$ path and $P_{2}$ is a
$g_{2}^{*}$–$B_{M}^{*}$ path, both disjoint from $x_{2}=g^{*}$. As $O$ is
$2$-connected, there are paths in $O$ from $k^{*}$ to $g_{1}^{*}$ and
$g_{2}^{*}$ that avoid $\\{x_{1},x_{2}\\}$ (recall that $x_{1}\not\in V(O)$).
Since $P_{1}$ and $P_{2}$ are disjoint, at least one of them is disjoint from
$x_{1}$. Thus there is a $k^{*}$–$B_{M}^{*}$ path in $Z-\\{x_{1},x_{2}\\}$, a
contradiction. This proves (5).

With (2) we get that $k^{*}=h^{*}$, which implies $h^{*}\in V(O)$. We claim
that:

There is a $g^{*}$–$h^{*}$ path $Q$ in $O$ whose second vertex in $(V(H))^{*}$
is $g_{1}^{*}$.  (6)

Since $O$ is $2$-connected and $g_{1}^{*}\in V(O)$ by (4), there is a
$g_{1}^{*}$–$h^{*}$ path $Q^{\prime}$ in $O$ that is disjoint from $g^{*}$.
Since $g_{1}$ is a neighbour of $g$ in $H-e_{1}-e_{2}$, there is a
$g^{*}$–$g_{1}^{*}$ path $Q^{\prime\prime}$ of length $2$ in $O$, which by
construction of $Z$ is internally disjoint from $Q^{\prime}$. Combining those
to $Q=Q^{\prime\prime}\cup Q^{\prime}$ thus yields the desired $g^{*}$–$h^{*}$
path $Q$ in $O$. This proves (6).

Note that $Q\subseteq\Phi(H)$. Thus, to finish the proof we need to show that
$Q$ is disjoint from $W^{0}$; and that $Q$ is internally disjoint from every
$S\in\mathcal{S}$.

Suppose that the interior of $Q$ meets either $W^{0}$ or some path in
$\mathcal{S}$, and let $q$ be the first vertex in the interior of $Q$ where
that happens. Next, among all vertices in $g^{*}Qq\cap P$, pick $\ell^{*}$ to
be the one closest to $h^{*}$ on $P$.

$g^{*}$$h^{*}$$P$$Q$$q$$\ell^{*}$$S$ Figure 5: Situation in Lemma 12. Vertices
in $B^{*}_{M}$ in black.

We observe that $\ell^{*}$ must be an internal vertex of $P$. Indeed,
$\ell^{*}\neq h^{*}$ as $q$ is an internal vertex of $Q$, and $\ell^{*}\neq
g^{*}$ by (6). From (2) it follows that $\ell^{*}\notin B^{*}_{M}$, and from
Lemma 11 it follows that there is a set $Y=\\{y_{1},y_{2}\\}$ of at most two
vertices that separates $\ell^{*}$ from $B^{*}_{M}$ in $Z$.

As the paths $g^{*}Q\ell^{*}$ and $\ell^{*}Ph^{*}$ meet only in $\ell^{*}$ by
choice of $\ell^{*}$, it follows that one vertex in $Y$, $y_{1}$ say, lies in
$\ell^{*}Ph^{*}$ and the other, $y_{2}$, in $g^{*}Q\ell^{*}$. Now, the path
$\ell^{*}Qq$ meets $g^{*}Q\ell^{*}$ and $\ell^{*}Ph^{*}$ also only in
$\ell^{*}$ and thus is disjoint from $Y$. As a consequence, $q$ cannot lie in
$W^{0}$ as every vertex in $W^{0}$ sends a $3$-fan to $B^{*}_{M}$. Therefore,
$q$ lies on a path $S\in\mathcal{S}$.

Note that as $\ell^{*}Qq$ is disjoint from $Y$ and as the endvertices of $S$
lie in $B^{*}_{M}$, it follows that both vertices in $Y$ must lie on $S$. If
$y_{1}$ lies in $S$ then, as $y_{1}\in V(P)$ and as $P$ is internally disjoint
from $S$, the vertex $y_{1}$ must be an endvertex of $P$, ie, $y_{1}=h^{*}$.
As $S$ is a $B^{*}_{M}$-path, it follows that $y_{1}$ is an endvertex of $S$.
That $y_{2}\in V(g^{*}Q\ell^{*})$ lies in $S$ implies, too, that $y_{2}$ must
be an endvertex of $S$: Indeed, $q$ was the first internal vertex on $Q$ to
lie in $S$, and thus $y_{2}=g^{*}$, which lies in $B^{*}_{M}$. But now, $S$
has both endvertices with $P$ in common, which is not allowed for a path in
$\mathcal{S}$. We have obtained the final contradiction that proves the lemma.
∎

We are done if we find an ($a^{*}$–$b^{*}$, $c^{*}$–$d^{*}$) linkage in
$\Phi(H)\cap W$. The next lemma tells us that if there is no such linkage then
we obtain two different paths between the terminals, one inside the Heinlein
wall and one outside.

######  Lemma 13.

Either there is an ($a^{*}$–$b^{*}$, $c^{*}$–$d^{*}$) linkage in $\Phi(H)\cap
W$, or there is an $\\{a^{*},b^{*}\\}$–$\\{c^{*},d^{*}\\}$ path in
$\Phi(H)\cap W$ whose endvertices are in the same component of
$\Phi(H)-W^{0}$.

###### Proof.

We proceed by case distinction. First, consider the case that there is a
$v\in\Phi(B)$ such that $v$ lies in $W^{0}$ or such that $v$ is a terminal
with degree at least $2$ in $\Phi(H)\cap W$.

As $v\in\Phi(B)$, there is a $3$-fan $T$ in $\Phi(H)$ from $v$ to the proper
branch vertices of some $10$-wall’ $R\subseteq\Phi(H)$. Moreover, as $R$ is
too large to fit into $W$ by Lemma 6, there must be some proper branch vertex
$w$ of $R$ outside $W$. Thus, $T\cup R$ contains three internally disjoint
$v$–$w$ paths $P_{1},P_{2},P_{3}\subseteq\Phi(H)$.

By definition of $v$, there are three terminals that are incident with an edge
in $(P_{1}\cup P_{2}\cup P_{3})-W^{0}$. Therefore, $P_{1}\cup P_{2}\cup P_{3}$
contains an $\\{a^{*},b^{*}\\}$–$\\{c^{*},d^{*}\\}$ path that lies in
$\Phi(H)\cap W$. Moreover, the endvertices of that path are connected in
$\Phi(H)-W^{0}$ via $P_{1}\cup P_{2}\cup P_{3}-W^{0}$.

Second, we consider the case when $\Phi(B)\cap V(W^{0})=\emptyset$ and when
every terminal in $\Phi(B)$ has degree at most $1$ in $\Phi(H)\cap W$. We
claim that

$\Phi(B)\cap(V(W)\setminus B^{*})=\emptyset$ (7)

Since $\Phi(B)\cap V(W^{0})=\emptyset$ and since $\\{a^{*},c^{*}\\}\subseteq
B^{*}$, the claim (7) can only be violated if $b^{*}\in\Phi(B)\setminus B^{*}$
or if $d^{*}\in\Phi(B)\setminus B^{*}$. While $b^{*}$ and $d^{*}$ are not
exchangeable, they are largely symmetric for the purpose of the proof of (7).
Therefore, we only concentrate on $b^{*}$ and consider the case that
$b^{*}\in\Phi(B)$ and then show that this implies $b^{*}\in B^{*}$. The proof
for $d^{*}$ is similar.

From $b^{*}\in\Phi(B)$ it follows that there are three paths
$P_{1},P_{2},P_{3}$ in $\Phi(H)$ from $b^{*}$ to proper branch vertices of
some $10$-wall’ $R\subseteq\Phi(H)$ such that $P_{1},P_{2},P_{3}$ are disjoint
except for $b^{*}$. Note that all proper branch vertices of $R$ lie in
$Z-W^{0}$ as $\Phi(B)$ is disjoint from $W^{0}$. Therefore, $R$ may only
intersect $W^{0}$ in at most two paths. (Here, we also use that every terminal
in $\Phi(B)$ has degree at most $1$ in $\Phi(H)\cap W$.) Let $Q_{1},Q_{2}$ be
the paths in $R$ between proper branch vertices of $R$ that are incident with
$W^{0}$ (if they exist at all).

Let $P\in\\{P_{1},P_{2},P_{3},Q_{1},Q_{2}\\}$, and observe that
$P\subseteq\Phi(H)$. As the endvertices of $P$ are either proper branch
vertices of $R$ or $b^{*}$, it follows that they lie in $V(H)^{*}$. We denote
them by $g^{*}$ and $h^{*}$. Moreover, as we assume $b^{*}\in\Phi(B)$ it
follows that $\Phi(H)$ contains three internally disjoint disjoint
$g^{*}$–$h^{*}$ paths. Only two of these may intersect $W^{0}$. As a
consequence, the endvertices $g^{*}$ and $h^{*}$ are contained in the same
component of $\Phi(H)-W^{0}$. Therefore, if $P\cap W$ contains exactly one
non-trivial $\\{a^{*},b^{*}\\}$–$\\{c^{*},d^{*}\\}$ path $Q$, then, with the
help of $P-W^{0}$, we see that the endvertices of $Q$ are in the same
component of $\Phi(H)-W^{0}$. As, moreover, $P\cap W$ contains a path between
the endvertices of $Q$, we have found a path as in the statement of the lemma
and are done.

If, on the other hand, $P\cap W$ contains two non-trivial
$\\{a^{*},b^{*}\\}$–$\\{c^{*},d^{*}\\}$ paths, we can use $e_{1}$ and $e_{2}$
to find a $g$–$h$ path $I_{P}$ in $H$ with $V(I_{P})^{*}\subseteq V(P)$. If
$P\cap W$ contains an $a^{*}$–$b^{*}$ path or a $c^{*}$–$d^{*}$ path (or
both), we can again use $e_{1}$ or $e_{2}$ to find a $g$–$h$ path $I_{P}$ in
$H$ with $V(I_{P})^{*}\subseteq V(P)$. (If $P\cap W$ contains both an
$a^{*}$–$b^{*}$ path and a $c^{*}$–$d^{*}$ path, we can actually stop as then
we have the desired linkage.) Finally, if $P\cap W$ contains no non-trivial
path then, too, we easily find a $g$–$h$ path $I_{P}$ in $H$ with
$V(I_{P})^{*}=V(P)\cap V(H)^{*}$.

Since $R$ intersects $W^{0}$ only in $Q_{1}$ and $Q_{2}$ (if these exist at
all), using $I_{Q_{1}}$ and $I_{Q_{2}}$, we find a $10$-wall’ $M^{\prime}$ in
$H$ such that $V(M^{\prime})^{*}\subseteq V(R)$. In the same way, we note that
the $b$–$M^{\prime}$ paths $I_{P_{1}},I_{P_{2}},I_{P_{3}}$ in $H$ satisfy
$V(I_{P_{j}})^{*}\subseteq V(P_{j})$ for $j=1,2,3$. In particular,
$I_{P_{1}},I_{P_{2}},I_{P_{3}}$ are pairwise disjoint except for $b$. In
total, we have found a $3$-fan from $b$ to a $10$-wall’, which implies that
$b\in B$ and thus $b^{*}\in B^{*}$. This proves (7).

By Lemma 9, it follows from (7) and $|B|=|\Phi(B)|$ that

$B^{*}=\Phi(B).$ (8)

In particular, the terminals $a^{*}$ and $c^{*}$ lie in $\Phi(B)$, which
implies that there is, for every terminal $v\in\\{a^{*},c^{*}\\}$, a $3$-fan
$T\subseteq\Phi(H)$ from $v$ to proper branch vertices of some $10$-wall’
$R\subseteq\Phi(H)$. Note that all proper branch vertices of $R$ lie in
$\Phi(B)$ and thus outside $W^{0}$. Therefore, there is for every
$v\in\\{a^{*},c^{*}\\}$ a path $Q_{v}$ that starts in $v$, that ends in
another terminal and that is completely contained in $W$. Moreover, via the
$3$-fan $T$, there is a path between the endvertices in $\Phi(H)-W^{0}$.
(Observe that the paths $Q_{a^{*}},Q_{c^{*}}$ do not have to be disjoint, nor
distinct.)

If $Q_{a^{*}}$ ends in $\\{c^{*},d^{*}\\}$ or if $Q_{c^{*}}$ ends in
$\\{a^{*},b^{*}\\}$, we observe that $Q_{a^{*}}$ or $Q_{c^{*}}$ is an
$\\{a^{*},b^{*}\\}$–$\\{c^{*},d^{*}\\}$ path in $\Phi(H)\cap W$ whose
endvertices are in the same component of $\Phi(H)-W^{0}$ and we are done. Thus
we may assume that $Q_{a^{*}}$ is an $a^{*}$–$b^{*}$ path and $Q_{c^{*}}$ is a
$c^{*}$–$d^{*}$ path. If $Q_{a^{*}}$ is disjoint from $Q_{c^{*}}$, they form
an $(a^{*}$–$b^{*}$, $c^{*}$–$d^{*}$) linkage in $\Phi(H)\cap W$, which was
what we wanted. Thus, we may assume that $Q_{a^{*}}$ intersects $Q_{c^{*}}$,
which implies that $Q_{a^{*}}\cup Q_{c^{*}}$ contains an $a^{*}$–$c^{*}$ path
$P$. We then apply Lemma 12 to $a^{*},c^{*}$ in the role of $g^{*},h^{*}$, and
to some $a$–$c$ path $L$ in $M-e_{1}-e_{2}$. Note that $(V(L))^{*}$ is
automatically disjoint from $B^{*}\setminus\Phi(B)$, as the latter set is
empty, by (8). The path we obtain from the lemma then shows that the
endvertices of $P$ lie in the same component of $\Phi(H)-W^{0}$, and we are
done. ∎

In the next lemma we will use planarity arguments. To this end, if $G$ is a
planar graph that is drawn in the plane, ie, if $G\subseteq\mathbb{R}^{2}$,
then we define the _interior_ $\operatorname*{int}(G)$ as the set
$\mathbb{R}^{2}\setminus F$, where $F$ is the outer face (the unbounded face)
of $G$.

We have reached the final lemma that concludes the proof of Theorem 2.

######  Lemma 5.

$\Phi(H)$ contains an ($a^{*}$–$b^{*}$, $c^{*}$–$d^{*}$) linkage in $W$.

###### Proof.

Suppose that $\Phi(H)\cap W$ does not contain any ($a^{*}$–$b^{*}$,
$c^{*}$–$d^{*}$) linkage. Then Lemma 13 yields $v_{1}\in\\{a^{*},b^{*}\\}$,
$v_{2}\in\\{c^{*},d^{*}\\}$ and $v_{1}$–$v_{2}$ paths $P$ and $Q$ such that
$P\subseteq\Phi(H)\cap W$ and $Q\subseteq\Phi(H)-W^{0}$.

Set $D=\\{h\in B:h^{*}\not\in\Phi(B)\\}$ and observe that Lemma 10 implies
that $|D|\leq 52$. Every vertex is incident with at most one row and one
column of the wall’ $M$. Thus, there is a wall’ $M^{\prime}\subseteq
M-D-\\{a,b,c,d\\}$ that contains all but at most $56$ rows and columns of $M$,
and that is disjoint from $D$ and from the terminals $a,b,c,d$. We write
${M^{\prime}}^{*}\subseteq Z$ for the subwall’ of $M^{*}$ that contains all
images of the branch vertices of $M^{\prime}$ under $*$.

As all proper branch vertices of $M^{\prime}$ are in $B_{M}$ and as
${M^{\prime}}^{*}$ is disjoint from $B^{*}\setminus\Phi(B)$ we can apply Lemma
12 to every (subdivided) edge $gh$ of $M^{\prime}$ to see that there is a
$g^{*}$–$h^{*}$ path in $\Phi(H)-W^{0}$. Moreover, as such a path is a
$B^{*}_{M}$-path (and thus in $\mathcal{S}$ with respect to the lemma), the
obtained paths are all internally disjoint. Replacing the subdivided edges of
${M^{\prime}}^{*}$ one by one in this way, we obtain a wall’ $R$ in
$\Phi(H)-W^{0}$ whose proper branch vertices are identical with those from
${M^{\prime}}^{*}$. In particular, for every row (resp. for every column) of
${M^{\prime}}^{*}$ there is a row (resp. a column) of $R$ with the same proper
branch vertices.

We note for later that

$R\subseteq\Phi(H)-W$ (9)

We make a second observation. The graph $Z-W^{0}$ is planar as $H$ is planar,
and, in what follows, we consider a fixed drawing of $Z-W^{0}$. Then, the
interior $\operatorname*{int}(S)$ of any brick $S$ of $M^{*}$ is well-defined.
We may assume that $Z-W^{0}$ is drawn in such a way that no brick interior
contains the outercycle of $M^{*}$. We use this to observe that if
$S^{\prime}$ is a brick of ${M^{\prime}}^{*}$ and if $S$ is the corresponding
brick of $R$ with the same proper branch vertices then any vertex in
$\operatorname*{int}(S^{\prime})$ lies in the interior
$\operatorname*{int}(S)$ or in the interior of a brick of $R$ that is adjacent
to $S$, ie, that shares a subdivided edge with $S$.

Recall the $v_{1}$–$v_{2}$ path $Q$ contained in $\Phi(H)-W^{0}$. We claim:

$Q$ meets $R$, and if $q_{1}$ is its first and $q_{2}$ its last vertex in $R$
then $q_{1},q_{2}$ are $8$-apart in $R$. (10)

As each pair of one vertex from $\\{a,b\\}$ and one of $\\{c,d\\}$ is
$70$-apart in $M$, it follows that $v_{1},v_{2}$ are $70$-apart in $M^{*}$.
(Recall that $M^{*}$ is a subdivision of $M-e_{1}-e_{2}$ in $Z-W^{0}$.) As
every path in $M^{*}$ from $v_{1}$ or from $v_{2}$ to the outercycle of
$M^{*}$ meets at least $70$ rows or columns, and as ${M^{\prime}}^{*}$
contains all but $56$ rows and all but $56$ columns of $M^{*}$ it follows that
there are bricks $S^{\prime}_{1},S^{\prime}_{2}$ of ${M^{\prime}}^{*}$ such
that $v_{i}\in\operatorname*{int}(S^{\prime}_{i})$ for $i=1,2$.

Consider a path $Q^{\prime}\subseteq{M^{\prime}}^{*}$ from a vertex of
$S^{\prime}_{1}$ to a vertex of $S^{\prime}_{2}$ and suppose that $Q^{\prime}$
meets ${M^{\prime}}^{*}$ fewer than 10 times. Then follow $Q$, which is a path
in $Z-W^{0}$, from $v_{1}$ to the first vertex in $S^{\prime}_{1}$, then along
$S^{\prime}_{1}$ to the first vertex of $Q^{\prime}$, then along $Q^{\prime}$
to $S^{\prime}_{2}$, from there to the last vertex of $Q$ in $S^{\prime}_{2}$
and along $Q$ to $v_{2}$. The resulting $v_{1}$–$v_{2}$ path
$Q^{\prime\prime}\subseteq Z-W^{0}$ meets fewer than $14$ rows and columns of
${M^{\prime}}^{*}$ (each of the bricks $S^{\prime}_{1}$ and $S^{\prime}_{2}$
may contribute at most two more rows and columns). As ${M^{\prime}}^{*}$
contains all but $56$ rows and columns of $M^{*}$ we see that
$Q^{\prime\prime}$ meets fewer than $70$ rows and columns of $M^{*}$, which is
impossible as $v_{1},v_{2}$ are $70$-apart in $M^{*}$. In a similar way, we
see that each path from $v_{1}$ or from $v_{2}$ to the outercycle of
${M^{\prime}}^{*}$ meets $10$ rows or columns of ${M^{\prime}}^{*}$.
Therefore, $S^{\prime}_{1},S^{\prime}_{2}$ are $10$-apart in
${M^{\prime}}^{*}$.

As we had observed that the interior of each brick of $R$ is contained in the
interior of the corresponding brick in ${M^{\prime}}^{*}$ together with the
interiors of adjacent bricks, it follows that there are bricks $S_{1}$ and
$S_{2}$ of $R$ such that $v_{i}\in\operatorname*{int}(S_{i})$ for $i=1,2$ and
such that $S_{1},S_{2}$ are $8$-apart in $R$.

As a consequence, the path $Q$, which is entirely contained in the plane graph
$Z-W^{0}$, meets $R$ (in at least eight vertices). Denote by $q_{1}$ the first
vertex of $Q$ in $R$, and let $q_{2}$ be the last vertex of $Q$ in $R$. Then
$q_{1}$ lies in the brick $S_{1}$, and $q_{2}$ lies in $S_{2}$. Therefore,
$q_{1},q_{2}$ are $8$-apart in $R$. This proves (10).

Recall the $v_{1}$–$v_{2}$ path $P$ contained in $\Phi(H)\cap W$. As $H$ is
planar, and as as $Q\cup P\cup R\subseteq\Phi(H)$, it follows that $Q\cup
P\cup R$ is planar, too. Consider $q_{1}Qv_{1}\cup P\cup v_{2}Qq_{2}$: this is
a $q_{1}$–$q_{2}$ path that meets the wall’ $R$ only in its endvertices since
$P\subseteq W$, while $R$ is disjoint from $W$, by (9). However, $q_{1},q_{2}$
are $8$-apart, by (10). Clearly, this is impossible in a planar graph. The
final contradiction proves the lemma. ∎

## References

  * [1] Henning Bruhn and Matthias Heinlein, _$K_{4}$ -subdivisions have the edge-Erdős-Pósa property_, SIAM Journal on Discrete Mathematics 35 (2021), no. 1, 392–430.
  * [2] Henning Bruhn, Matthias Heinlein, and Felix Joos, _Long cycles have the edge-Erdős-Pósa property_ , Combinatorica 39 (2019), 1–36.
  * [3] Henning Bruhn, Matthias Heinlein, and Felix Joos, _The edge-Erdős-Pósa property_ , Combinatorica 41 (2020), 147 – 173\.
  * [4] Alexander Grigoriev, _Tree-width and large grid minors in planar graphs_ , Discrete Mathematics & Theoretical Computer Science 13 (2011), 13–20.
  * [5] Jean-Florent Raymond, _Dynamic Erdős-Pósa listing_ , https://perso.limos.fr/~jfraymon/Erd%c5%91s-P%c3%b3sa/, Accessed: 2023-05-04.
  * [6] Jean-Florent Raymond and Dimitrios M. Thilikos, _Recent techniques and results on the Erdős–Pósa property_ , Discrete Applied Mathematics 231 (2017), 25 – 43, Algorithmic Graph Theory on the Adriatic Coast.
  * [7] Neil Robertson and P.D Seymour, _Graph minors. V. Excluding a planar graph_ , Journal of Combinatorial Theory, Series B 41 (1986), no. 1, 92 – 114.
  * [8] Raphael Steck, _On the edge-erdős-pósa property of walls_ , 2023.