Find simple graphs of diameter 3 where edge connectivity doesn't equal minimum degree

234 Views Asked by At

I've seen a question here which is about

Prove that in a simple graph of diameter 2 the edge connectivity is equal to the minimum degree

But I would like to show that this is the best bound by finding an infinite class of connected graphs of diameter 3 where the minimum degree doesn't equal the edge connectivity.

1

There are 1 best solutions below

0
On BEST ANSWER

Consider the graphs obtained by joining two complete graphs on at least three vertices by a bridge; the number of vertices on each side need not be equal. The simplest case, with two copies of $K_3$, is

*     *
|\   /|
| *-* |
|/   \|
*     *

(MathWorld calls such graphs, with equal vertex counts on each side, barbell graphs). All such graphs, by virtue of the bridge, are only 1-edge-connected; they are also easily seen to have diameter 3 and minimum degree at least 2. Therefore, this is an infinite set of diameter-3 graphs where edge connectivity and minimum degree are unequal.