4
$\begingroup$

The homeomorphism class $ \mathcal{H}(G) $ of a graph $G$ is the set of isomorphism classes of graphs that are topologically homeomorphic to $G$. It is natural to ask: Is there a "smallest" representative in the homeomorphism class? If yes, how to find it? Unfortunately, I found no useful result on this problem after a quick google search.

Nevertheless, guided by intuition, I have the following hypothesis:

The smallest graph homeomorphic to a graph is obtained by smoothing every maximal ear.

In this post I attempt to sketch a proof, but there is a gap in the proof, so I don't know whether my hypothesis is actually correct. I would appreciate anyone for pointing out my mistakes and filling out the gap.

Warning: this would be a long post

First, let's clear up some terminology. The term "ear" means different things in different graph theory textbooks. In this post, we adopt the following definition:

Definition 1

An ear in a graph is either:

  • a cycle whose all except possibly one vertices are of degree $2$, or
  • a path whose all internal vertices are of degree $2$.

A maximal ear is an ear that is not a proper subgraph of a larger ear. Equivalently, a maximal ear is one of the following:

  • a cycle that is a whole connected component on its own
  • a cycle in which exactly one vertex is of degree $ \geq 3 $, while all other vertices are of degree $2$
  • a path in which all internal vertices are of degree $2$, while both end vertices are of degree $ \neq 2 $

Two common operations that preserve topology on graphs are subdividing and smoothing:

Definition 2

Subdividing an edge means replacing it by an ear. More precisely, let $e = uv$ be an edge.

If $u = v$, then subdividing the self-loop $e$ means replacing it by a cycle $C$, and $u = v$ becomes a vertex on $C$, which may or may not have degree $2$, depending on whether $e$ is isolated.

On the other hand, if $u \neq v$, then subdividing $e$ means replacing it by a path $P$, and $u, v$ become the end vertices of $P$.

Subdividing a graph means preforming a sequence of subdividing on edges.

Definition 3

Smoothing an ear means replacing it by a single edge. More precisely, let $C$ be an ear.

If $C$ is a cycle, then smoothing $C$ means replacing it by a self-loop $e$, and the vertex of degree $ \neq 2 $ on $C$ becomes the only vertex incident on $e$ (if all vertices on $C$ are of degree $2$, just choose any vertex).

On the other hand, If $C$ is actually a path $P$, then smoothing $P$ means replacing it by a loopless edge $e$, and the end vertices of $P$ become the end vertices of $e$.

Smoothing a graph means preforming a sequence of smoothing on ears.

Next, we have the following classic result on topology of graphs:

Theorem 1

Two graphs are homeomorphic if and only if one of them can be obtained from a sequence of subdividing and smoothing operations on the another.

Proof: See this post.

Theorem 2

Let $G$ and $H$ be two homeomorphic graphs. Then $ |V(G)| = |V(H)| $ if and only if $ |E(G)| = |E(H)| $.

Sketch of proof: Subdividing (resp. smoothing) always increases (resp. decreases) the number of vertices and edges by the same number. $\square$

In light of Theorem 2, we can define an ordering on the homeomorphism class of a graph:

Definition 4

Let $ \mathcal{H}(G) $ be the homeomorphism class of a graph $G$. Define the ordering $\preceq$ on $ \mathcal{H}(G) $ by: $$ G_1 \preceq G_2 \iff |V(G_1)| \leq |V(G_2)| $$ for any $ G_1, G_2 \in \mathcal{H}(G) $.

If $ G_1 \preceq G_2 $ and $ G_2 \preceq G_1 $, then we denote $ G_1 \sim G_2 $.

The ordering $\preceq$ is a total preorder, meaning it is transitive and any two homeomorphic graphs are comparable. Unfortunately it is not a total order, since $ G_1 \sim G_2 $ does not imply $ G_1, G_2 $ are isomorphic, even through Theorem 2 implies $ |E(G_1)| = |E(G_2)| $.

Theorem 3

Any graph without isolated vertex can be uniquely decomposed into an edge-disjoint union of maximal ears.

Sketch of proof:

Let $G$ be a graph without isolated vertex. Define the relation $R$ on $E(G)$ by: $$ eRf \iff \exists \text{ ear } C \subseteq{G} \text{ s.t. } e, f \in E(C) $$ for any $ e, f \in E(G) $.

Then $R$ is an equivalence relation on $E(G)$, in which each equivalence class contains the edges of exactly one maximal ear. Thus, $R$ induces a decomposition of $G$ into an edge-disjoint union of maximal ears. Conversely, any such decomposition must be induced by $R$, so the decomposition is unique. $\square$

Based on the above decomposition, we can define the following:

Definition 5

A graph without isolated vertex is called smooth if every maximal ear is of length $1$. For a graph $G$ without isolated vertex, the smooth graph obtained from smoothing every maximal ear in $G$ is denoted as $ \text{Smooth} (G) $.

The term "smooth graph" is not standard, but I could not find any existing term for such a graph, so I just make it up on my own.

Theorem 4

Let $G$ be a smooth graph without isolated vertex and $ H \in \mathcal{H}(G) $, then $ G \preceq H $. Moreover, $ G \sim H $ if and only if $H$ is a smooth graph.

Sketch of proof:

By Theorem 1, $H$ can obtained from a sequence of subdividing and smoothing operations on $G$. Each step of the operations can only change one of the maximal ear to another maximal ear of possibly different length.

On the other hand, in a smooth graph all the maximal ears already have the shortest possible length (namely, $1$), so any sequence of subdividing and smoothing can never further decrease the number of vertices. Thus, $ |V(G)| \leq |V(H)| $ and the equality holds if and only if $H$ is smooth. $\square$

The following claim is based on intuition, but I don't know how to prove it. It is where the gap of my whole proof lies.

Claim 0

Let $G$ and $H$ be two smooth graphs without isolated vertex. If they are homeomorphic, then they are isomorphic.

Finally, assuming the above claim, we can prove the main hypothesis:

Main Hypothesis

Assume Claim 0 is correct and let $G$ be a graph without isolated vertex. Then $ \text{Smooth} (G) $ is the unique smallest graph in $ \mathcal{H} (G) $ with respect to the ordering $ \preceq $.

Proof:

The fact that $ \text{Smooth} (G) \preceq H $ for all $ H \in \mathcal{H} (G) $ follows from Theorem 4.

To prove uniqueness, let $ H \in \mathcal{H} (G) $ be such that $ \text{Smooth} (G) \sim H $. Since $ \text{Smooth} (G) $ is smooth and $ H \in \mathcal{H} (\text{Smooth} (G)) $, by Theorem 4, $H$ is smooth as well. Claim 0 then implies $H$ is isomorphic to $ \text{Smooth} (G) $. $\square$

Questions:

  1. Is Claim 0 correct? How to prove it?
  2. Even if Claim 0 is wrong, is my main hypothesis still correct?
  3. Are there any other mistakes in my proof?
  4. Is there a better term for graphs whose every maximal ear is of length $1$, other than "smooth graphs"?
$\endgroup$
2
$\begingroup$

Your proof appears correct to me. I don't see why you assume that the graph has no isolated vertices – does it make a difference anywhere? Also, "smooth graph" seems to be a fancy name for a graph with no vertices of degree two. (More precisely, the only vertices of degree two are isolated vertices with a loop.)

I'll give a proof of your claim. We may assume that the graphs in question are connected and that they have at least one edge. To any graph $G$, associate a vertex-colored graph $Ear(G)$ in the following way:

  • The vertices of $Ear(G)$ correspond to the ears in the unique decomposition of $G$ into maximal ears. They are colored blue and red according to whether the ear is a path or a cycle.
  • Two vertices are adjacent if the corresponding ears have a common vertex; if they have two common vertices, then we draw two parallel edges. (This can only happen if the corresponding ears are paths.)

There are two observations to be made which are more or less implicit in your proof of Theorem 4:

  1. If $G$ and $H$ are homeomorphic, then $Ear(G)$ and $Ear(H)$ are isomorphic, with the isomorphism preserving the vertex colors. This follows from Theorem 1 after checking that both smoothing and subdividing preserve $Ear(G)$.
  2. If $G$ is smooth, then (disregarding the coloring) $Ear(G)$ is just the line graph of $G$, defined appropriately for graphs with loops and multiple edges.

Conveniently, a theorem of Whitney states that if the line graphs of two connected simple graphs isomorphic, then the graphs themselves are isomorphic, except if the graphs are the triangle $K_3$ and the claw $K_{1,3}$. Note that the triangle is not smooth. In the case of graphs with loops and parallel edges, the situation is more complicated (though not terribly so, according to this article* to which I could only find a paywalled link; funnily enough, the name of Whitney is misspelled in the title), but in our case the vertex-coloring and Theorem 4 give us enough information to uniquely reconstruct the original graph. You could probably sort this out yourself, but I'll give the details for completeness.

So suppose that $G$ and $H$ are smooth and that $Ear(G)$ and $Ear(H)$ are isomorphic. First, we deal with loops: these correspond precisely to the red vertices of $Ear(G)$ and $Ear(H)$. It follows that if we denote by $G'$ and $H'$ the graphs obtained by deleting the loops in $G$ and $H$, then $Ear(G')$ and $Ear(H')$ are obtained by deleting the red vertices from $Ear(G)$ and $Ear(H)$; in particular, they are isomorphic. Now it is enough to show that $G'$ and $H'$ are isomorphic, since then the positions of the loops are uniquely determined by $Ear(G)$: a vertex in $G'$ has a loop if and only if there is an edge incident to it which is adjacent to a red vertex in $Ear(G)$, or if $G'$ consists of this single vertex (since we assumed that our graphs have at least one edge).

Thus, we may assume that $G$ and $H$ contain no loops. Now we just have to take care of parallel edges. If two edges are parallel in $G$, then by our construction the corresponding vertices in $Ear(G)$ are connected by two parallel edges. More generally, two or more parallel edges in $G$ correspond to a clique in $Ear(G)$ in which every edge is doubled. Every vertex in $Ear(G)$ is contained in a unique maximal such "double clique" (potentially of size one), and by contracting these cliques and replacing newly formed parallel edges by single ones, we obtain the line graph of the simple graph underlying $G$. Since this works backwards as well (i.e. from the simple graph and $Ear(G)$ we can recover $G$), we may assume that $G$ and $H$ are simple.

So we are done by Whitney's theorem, right? Well, not so fast. It could happen that after leaving loops and parallel edges from $G$ and $H$, we are left with a triangle and $K_{1,3}$: after all, a triangle with doubled edges is smooth. But this is ruled out by Theorem 4: the original $G$ and $H$ had the same number of vertices, and leaving edges doesn't change that. So $G$ and $H$ are indeed isomorphic.

*Note that, as far as I can tell, the notion of line graph used in the article is different from the one used here, in that the vertices corresponding to parallel edges are still connected with only one edge.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.