1

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!

  • 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... – DonAntonio Feb 13 '18 at 10:20
  • 1
    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). – Especially Lime Feb 13 '18 at 10:26
  • @EspeciallyLime Suppose that G is disconnected, how would I prove the statement. I have a counter example for it. –  Feb 13 '18 at 10:29
  • 1
    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. – freakish Feb 13 '18 at 10:37
  • @freakish I don't think so. Proving connectivity does not prove the diameter length. –  Feb 13 '18 at 10:39
  • @user1944 Read Chris Eagle's proof. Ask questions afterwards. – freakish Feb 13 '18 at 10:40
  • That's of course under the assumption that G is disconnected. I'm not sure about the case when G is connected (and thus infinite). – freakish Feb 13 '18 at 10:50
  • @freakish You are right, it does answer my question. I was being able to find a counter example before, because that is because I did not correctly understand the definition of diameter of a graph. It is longest shortest possible path between 2 vertices. Thank you! –  Feb 13 '18 at 11:03
  • The new edit of the question does not make sense to me. And now the accepted answer below doesn't make sense to nobody. The earlier question was clear to me, I don't know why clarification was needed and why everybody was talking about connectivity... – Max Punck-Institut Feb 14 '18 at 08:01

1 Answers1

4

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)

Max Punck-Institut
  • 193