Connectivity Graph Theory

Question

Which of the following statements are true . Please explain why each statement is true/false..

S1 : If a simple graph G is not connected then it's complement G is not connected

S2 : If a simple graph G is connected them it's complement G is not connected

S3 : A simple graph with n vertices is necessarily connected if min degree of a vertex = (n-1)/2

S4 : If a simple graph has exactly two vertices of odd degree then there exists a path between two vertices of odd degree

Comments

S1 is False. Here is the proof.

S2 is True. You can refer above proof for the same.

Here is the generalized theorem for the above two.

Theorem: If G is disconnected, then its complement is connected and vice versa.

Proof: True. Let G'' denote the complement of G. Consider any two vertices u, v in G. If u and v are in different connected components in G, then no edge of G connects them, so there will be an edge {u, v} in G''. If u and v are in the same connected component in G, then consider any vertex w in a different connected component (since G is disconnected, there must be at least one other connected component). By our first argument, the edges {u, w} and {v, w} exist in G'', so u and v are connected by the path (u, w, v). Hence any two vertices are connected in G'', so the whole graph is connected.

**Read these two, I will update this later.

---

s3 is false .

if a graph is connected then graph have minimam degree  atleast (n-1)/2 .

Answer 1

S1 : False

S2 : False

S3 : True

S4 : True

For S1 and S2 , it is established that for a simple graph G atleast one of G and G(complement) is connected , i.e. both can be connected as well. Consider the graph with 4 vertices. Let G have edges (1,2),(2,3) and (3,4) , then Gcomp will have the edges (1,3) ,(1,4),(2,4) resulting them both to be connected

S4 is also known as unicursal, i.e. the graph will have an Euler path but not circuit

Comments

Why s3 is true ?