Graph Theory: Discrete Math

Question

I am a student from Iraq studying Graph to get in to a college in Georgia. I have trouble understanding this question.

Show that the two definitions below are logically equivalent. Definition 1. A graph G = (V, E) is disconnected if there exist non-empty subgraphs H1 = (V1,E1) and H2 = (V2,E2) such that V1 and V2 partition V and E1 and E2 partition E. A graph is connected if it is not disconnected. Definition 2. A graph G is connected if for any two vertices v, w there is a walk between v and w.

Can someone kindly explain this situation???

Answer 1

Suppose the edge $DE$ is there in the graph. Then any two points can be connected by a walk. Also note that you cannot split the graph into two.

Suppose $DE$ isn't there, then you cannot connect $B$ and $G$ by any walk. Also in this case, you can split the graph into two. (The two black figures G and G')

Answer 2

first we prove 1=>2 this is equal to !2=>!1, !2 means that there exists two vertices v,w and there is not any walk between them,so we let all the vertices k which w can walk to are V2,and the edges on the walks are E2,of course,(V2,E2) is a non-empty subgraphs H2,and we let G-H2=H1,of course ,H1 is a subgraph of G ,and since v is in G-H2,H1 is not empty (G-H2 means all the verticals in G but not in H2,and all the walks in G but not in H2);and of course,le H1=(V1,E1)and H2=(V2,E2),then V1 and V2 partion V,then E1 and E2 partion V is because there exits no walks between V1 and V2(if there exist,w can walk to a vertical v1 in V1,so v1 should be in V2,this is a contradiction that v1 is in V1!);

sceond we prove 2=>1,we can prove !1=>!2 ,!1 means that there exist non-empty subgraphs H1 = (V1,E1) and H2 = (V2,E2) such that V1 and V2 partition V and E1 and E2 partition E. so we choose v in V1 and w in V2 ,then we assert that there is no walk between v and w(because if there a walk,asumee it is v1(v)->v2->v3->...->vn(w),then bacause v1 is in V1,so if edge(v1->v2)is in E1,then v2 must in V1,then if edge(v2->v3) is in E1,v3 must in v1,we can continue this process util edge vi->vi+1 is not in E1 but in E2(this is true because vn(w) is not in V1),but edge vi-1->vi is in E1,so vi is in V1 ,but vi is also in V2 because vi->vi+1 is in E2!,this is a contradiction!)so there is no walk between v and w,so !2 we have prove it!!!

Answer 3

There exists some mistake in the proof of $1$, we should prove that $G\setminus H2$ is a subgraph of $G$; if $(V1,E1)=G\setminus H2$ is a subgraph, of course $V1$ and $V2$ partition $V$ and $E1$ and $E2$ partition $E$.

To prove $(V1,E1)=G\setminus H2$ is a subgraph, the key point is to prove that if an edge $e$ is in $E1$ then the vertices of $e$ are both in $V1$; this is true because if one of the vertices is not in $V1$ it must be in V2, so $w$ can walk to it. Then the other vertex must be in $V2$ because there is an edge $e$ between them so $w$ can walk to the other vertex; this is a contradiction because if the other vertex is in $V2$ then the edge $e$ must be in $V2$ -- but we have assumed that $e$ is in $E1$ and this is a contradiction! So we prove it!!