1
$\begingroup$

Prove that a simple graph G is 2-connected if and only if for every triple (x, y, z) of distinct vertices, G has an x, z-path through y

Thanks!

$\endgroup$
9
  • $\begingroup$ Where, what,when? Would you mind defining what you're talking about? That's the first rule I'd write in a proof-writing seminar... $\endgroup$
    – DonAntonio
    Feb 13, 2018 at 10:20
  • 1
    $\begingroup$ Assuming $G$ is finite, the only way it can have infinite diameter is to be disconnected. If infinite graphs are allowed, there are other ways to have infinite diameter (e.g. the graph consisting of a path extending infinitely in both directions). $\endgroup$
    – Especially Lime
    Feb 13, 2018 at 10:26
  • $\begingroup$ @EspeciallyLime Suppose that G is disconnected, how would I prove the statement. I have a counter example for it. $\endgroup$
    – user529756
    Feb 13, 2018 at 10:29
  • 1
    $\begingroup$ Duplicate of Given a simple graph and its complement, prove that either of them is always connected. In the accepted answer you have a proof that every two points in a graph $G$ can be connected by a path of length at most 2 in the complement of $G$ is $G$ is disconnected. $\endgroup$
    – freakish
    Feb 13, 2018 at 10:37
  • $\begingroup$ @freakish I don't think so. Proving connectivity does not prove the diameter length. $\endgroup$
    – user529756
    Feb 13, 2018 at 10:39

1 Answer 1

Reset to default
4
$\begingroup$

Since I derive my definiton of Diameter from shortest paths I don't worry about disconnected Graphs in this answer. Let $G$ be connected and infinite, that means its vertex set is infinite.

Now for every pair of vertices $v,w$ we have 3 cases:

  1. $d(v,w)=1$

  2. $1<d(v,w)<\infty$

  3. $d(v,w)=\infty$

We now need to prove that in any case the shortest path between $v$ and $w$ in the complement of $G$ is at most $2$. Cases 2&3 are easy, because edge $vw$ is in the complement.

Now case 1: Two cases again:

Case 1a: there is a vertex $x\in G$, so that $vx,xw$ are not in $G$. Then both are in the complement, and the shortest path has length two.

Case 1b is clearly not possible: If $d(v,w)=1$ and $vx$ or $wx$ is in the Graph for every vertex $x$, then $G$ doesn't have a infinite diameter.

(EDIT: This answers the original question of OP: If the diameter of a graph $G$ is infinite then the diameter of its complement is ≤2)

$\endgroup$