Does there exist an infinite class two graph with no leaves?

Question

In this question I will be talking about both finite and infinite graphs. All graphs are assumed to be simple (i.e. undirected and contain no loops or double edges) and connected. It is also assumed for the entirety of this question that every graph $G=(V(G),E(G))$ satisfies the property that $\Delta(G):=\sup\{\mathrm{deg}(v):v \in V(G) \}<\infty$, where $\mathrm{deg}(v)$ denotes the degree of a vertex $v \in V(G)$.

An edge colouring of a graph is called proper if no two adjacent edges are assigned the same colour.

Given a graph $G$, the chromatic index of $G$, denoted $\chi'(G)$, is the minimum number of colours required for a proper edge colouring of $G$. By Vizing's theorem, if $G$ is a finite graph, then either $\chi'(G) = \Delta(G)$ or $\chi'(G) = \Delta(G)+1$.

Now suppose that $G$ is an infinite graph. By the De Brujin-Erdős theorem, if every finite subgraph of $G$ can be properly edge coloured with $k$ colours, then $G$ can also be properly edge coloured with $k$ colours. Thus, when $G$ is infinite, by combining the theorems of Vizing and De Brujin-Erdős, we also have that $\chi'(G) = \Delta(G)$ or $\chi'(G) = \Delta(G) +1$.

For an arbitrary (finite or infinite) graph $G$, $G$ is called class one if $\chi'(G) = \Delta(G)$, and is called class two if $\chi'(G)=\Delta(G)+1$.

In the context of my own research, which is studying locally compact groups acting on infinite graphs, one typically wants to study such actions which are 'highly transitive' in some sense. Thus regular infinite graphs arise naturally in this theory, and although it may not be obvious why, proper edge colourings of such graphs also arise naturally in this context.

At the time of writing this, I am not aware of any examples of infinite graphs that are class two, and I cannot find much research on the topic that is useful for finding an example of such a graph. It is also known that the proportion of finite graphs of order $n$ that are class two converges to $0$ as $n \rightarrow \infty$, so this may suggest that finding a class two infinite graph could be challenging, especially if I am looking in the wrong direction.

I thus pose the following two questions:

(i) Does there exist an infinite class two graph with no leaves?
(ii) Does there exist an infinite regular class two graph?

If the answer is yes to one or both of these questions, I would like to know an example of a graph satisfying the specified properties.

Answer 1

We can get a class two graph just by having a finite piece of the graph be poorly behaved, so having infinitely many vertices doesn't impede us much in finding an example.

Start with the standard $16$-vertex example of a $3$-regular graph with no perfect matching:

Why doesn't it have a perfect matching? Because each $5$-vertex petal does not have a perfect matching on its own, and the center vertex can only help one of the three petals.

This is a finite graph, but we can hook it up to any infinite $3$-regular graph we like. Let $G$ be the graph above, and let $H$ be your favorite infinite $3$-regular graph. To make $G \cup H$ connected, just:

1. Subdivide an edge of $G$ (that is, replace an edge $vw$ by edges $vx, wx$ where $x$ is a new vertex;
2. Subdivide an edge of $H$;
3. Join the resulting degree-$2$ vertices by a new edge.

When we do this, one of the three petals of $G$ is connected to $H$, so we have no control over what kind of matchings exist there. However, the other two petals still have the old problem: each one of them has no perfect matching on its own, and the central vertex of $G$ can only help one of the petals.

Since this infinite $3$-regular graph has no perfect matching, it cannot be $3$-edge-colorable: any color class in a $3$-edge-coloring of a $3$-regular graph has to be a perfect matching. So there you are: class two.