edited by
4,422 views
4 votes
4 votes
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
edited by

1 Answer

1 votes
1 votes
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

Related questions

1 votes
1 votes
1 answer
1
3 votes
3 votes
0 answers
3