Question

a. Write down all the automorphisms of a 4–cycle.

b. Prove that in each graph the number of vertices of odd degree is even.

c. Some pairs of the people at a party shake their hands. Prove that at least two persons shook the same number of hands. 9. Is it true that the complement of a connected graph is connected? Prove or disprove it. Is it true that the complement of a connected graph is not connected? Prove or disprove it.

Answer 1

(b) TO PROVE THAT IN EACH GRAPH NUMBER OF VERTICES OF ODD DEGREE IS EVEN:

Let G be a graph with "e" edges and "n" vertices V₁,V_2,...,V_n.​ Since each edge is incident on two vertices, it contributes 2 to the sum of degree of vertices in graph G. Thus the sum of degree of all vertices in graph G is twice the number of edges in graph G. Hence,

Let the degree of first "r" vertices be even and the remaining (n-r) vertices have odd degrees, then clearly,   

Since   

For i=r+1,r+2,..n, each ​ is odd. So the number of terms in ​ must be even.

In other words (n-r) is even.

Hence in each graph the number of vertices of odd degree is even.

(c) Some pairs of the people at a party shake their hands. Prove that at least two persons shook the same number of hands.

This can be easily proved by "Pigeon Hole Principle" which is stated as "IF YOU HAVE N ITEMS WHICH ARE TO BE PUT INTO M<N BOXES THEN THERE IS ATLEAST TWO ITEMS IN ONE OF THE BOXES".

Let us consider that there are "n" persons attending the party. Obviously this will make sense only when ​. If no two person have shaken hands with equal number of people then their handshake count differ must differ atleast by 1. So the possible choices for handshake count would be 0,1,...(n-1). There are exactly n choices and n people. If there exists a person with (n-1) handshake count, there cant be a person with 0 handshake count. Thus reducing the possible choices to (n-1). Now due to pigeonhole principle we have that atleast two person will have the same number of handshake count.

(c) SECOND PART:

The complement of connected graphs are not connected. Only when the graph is disconnected its complement is connected.

PROOF:

   To prove that the complement G* of disconnected graph G is connected.

Suppose G is a disconnected graph. We want to show that its complement G* is connected. Suppose V and W are vertices. If VW is not an edge in G then it is an edge in G*, and so we have a path fron V to W in G*.

On the other hand if VW is an edge in G, then this means V and W are in the same component of G. Since G is disconnected we can find a vertex U in a different component, so that neither UV nor VW are edges of G. Then VUW is a path from V to W in G*.

This shows that any two vertices in G* have a path between them in G*, so G* is connected.

Thus the complement G* of disconnected graph G is connected.

Conversely if G*, the complement of G, is not connected, then tehre exists a partitioning of vertices into two disjoint sets V1 and V2 such that no edge of the complement is between them. (i.e) for all ​ and ​ we have ​ does not belong to E*.However this means that for all v1 and v2 from V1 and V2 respectively, ​. Hence the graph G is connected.

The graph G whose complement G* is disconnected, is connected.