Examples based on a 2-connected graph.

233 Views Asked by At

According to Scott Smith 1984 Conjecture: In a $k$-connected graph, where $k \ge 2$, any two longest cycles have at least $k$ vertices in common.

A 2-connected graph: every pair of longest cycles have exactly two vertices in common does not exist. I claim this statement to be invalid because from the conjuncture the bound is not strictly greater than $k$. It is possible for $k=2$, so that we could have every pair of longest cycles having exactly two vertices in common. Any such examples of graphs?

1

There are 1 best solutions below

0
On BEST ANSWER

This is not possible for a simple graph. Let $g$ be a simple graph, let $C_1$ and $C_2$ be two longest cycles, and let $u$ and $v$ be two common vertex. We can suppose $C_1$ and $C_2$ do not share any other common vertices, otherwise we are already answered. $u$ and $v$ split each cycle in two paths, the four are disjoint. Each path must have the same size, otherwise by taking the two longest one, we would end up with a longer path than our two longest cycles. As the graph is simple, these paths should be of length greater than $2$. Now, take one of the path of each cycle. It gives a new cycle of the same size as $C_1$ and $C_2$, which intersect $C_1$ in at least $3$ vertices. If the graph is not simple, a 4-edges link works.