Question

Prove that, if even degree, then the edge conn G is a nontrivial connected graph in which every vertex has

Answer 1

To prove this we will require some definitions and results.

Definitions :

Cyclic Edge : The edge which lies on the cycle is called cyclic edge otherwise it is called acyclic edge.

Bridge : An edge e of a connected graph G is called bridge if G-e is disconnected.

Results :

1) If minimum degree of a graph G is greater than or equal to 2 then G is Cyclic or it contains cycles.

S(G)

2) If an edge of a graph is cyclic then it cannot be a bridge.

In the given problem, G is non trivial connected graph in which every vertex has even degree.

We have to prove edge connectivity of G is no less than 2.

i.e. To prove

K ' (G)丈2

As graph G is connected and degree of every vertex in graph G is even degree

$\Rightarrow$ minimum degree of a graph is definitely greater than or equal to 2.

i.e. $\delta (G) \geq 2$

Thus by result 1) Graph G is itself Cyclic graph or it contains cycles.

$\Rightarrow$ In any of the above case, every edge in such Graph G is cyclic edge.

$\therefore$ every edge in graph G is not a bridge. ........................From result 2)

$\Rightarrow$ If we delete any edge e from graph G then there is no effect on connectedness of a graph G.

i.e G is still be the connected graph.

$\Rightarrow$ If we want to disconnect a Graph G then we have to delete at least 2 edges from G.

We know that edge connectivity of a graph G, means minimum number of edges required to delete so that resulting graph is disconnected.

K'(G

Thus here edge connectivity of a graph G is greater than or equal to 2.

i.e.

K'(G)2

i.e

K ' (G)丈2

Thus the edge connectivity of a G is not less than 2.

Hence the proof.