LINK1) a)

In every simple graph having at least two vertices,we can always find two distinct vertices having same degree.

Pigeonhole principle:

The pigeonhole principle is one of the simple principle that is used in mathematics.

We can understand this principle using a simple example stated below.Suppose consider we have 20 pigeons.

There are 19 pigeonholes.These 20 pigeons needs to be set into these 19 pigeonholes.To obtain this, at least one of the pigeonhole must have 2 pigeons in it.

This is called as pigeonhole principle.

Proof:

We will generalize the theorem now and understand with 2 vertices later.

Consider a connected graph G having n vertices.

So every vertex has degree ranging between 1 and n-1.

See that there are n vertices in the graph G with degree ranging between 1 and n-1.

Using pigeon hole principle that is stated above, we can conclude that there is some value k between 1 and n-1 which has two or more vertices.

Now, consider a simple graph G(need not be connected).

If G graph has connected component with two or more vertices as a part, then the above result states that the component has two vertices with same degree.

If G graph has no connected components in it, then every vertex in G has degree zero.So there are multiple vertices with same degree.

B)

If G is a simple connected graph with degree of every vertex even,we can delete any edge and it is always connected.

Proof:

Consider a connected graph G which has n vertices.

The minimum number of edges turns out to be 2n.

Analyse the situation in which each vertex has at least two edges that are associated with it.

Now even if one of the edge of that vertex is removed it still has one more edge that is connected to some other vertex of graph.

Hence we can say that a connected graph G having degree of each vertex even is always connected even if we remove one edge.

Example:

The screenshot shows the connected graph with 3 vertices.

https://media.cheggcdn.com/media/8db/8db85e8f-8c48-4dba-b82e-e82a8aa4d376/phpbv2il0.png

LINK2)https://media.cheggcdn.com/media/672/67226aaa-0108-4037-aa20-f466e28ecaaa/php1IPP75.png

https://media.cheggcdn.com/media/e80/e80450a4-6e4e-4b3f-bf6c-b754427b4b0c/phputPIKT.png

LINK3)https://media.cheggcdn.com/media/882/882dec3f-b1bb-41e6-82fe-9de6adf77045/phpqlGgvC.png

LINK4)https://media.cheggcdn.com/media/1ac/1ac3e3f8-9607-457a-b934-2d204fcf244d/phpdcSBAg.png

https://media.cheggcdn.com/media/072/072a7eb6-79d3-4214-8574-dd5aa04f0b53/phpAgPdJ9.png

https://media.cheggcdn.com/media/6e3/6e32d589-bb86-4f1e-bb68-f18e67ac4446/phps5CNGz.png

LINK5)https://media.cheggcdn.com/media/5c2/5c2a092c-8476-4c68-b865-af56a1b98886/phpTXgiDi.png