1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

A simple counter Example is the path 4 graph denoted $P_4$ which is just this :

$* -- * -- * -- *$ so the graph diameter is $3$ and edge connectivity is $1$ since removing any edge will result to disconnect the graph but also the first and last vertex has degree $1$.

$\endgroup$
  • $\begingroup$ So minimum degree = edge connectivity in your example - I improved the question title to show that what is desired is a graph where that is not true. $\endgroup$ – Joffan Mar 15 '17 at 15:25
  • $\begingroup$ And now, this does not answer the question. $\endgroup$ – Parcly Taxel Mar 15 '17 at 15:55
  • $\begingroup$ @ParclyTaxel It never answered the text of the question. $\endgroup$ – Joffan Mar 15 '17 at 16:06

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.