Graph theory

Question

Can someone plz explain Relative Complement of   graph and also check the validity of the statement "If G is simple n vertex graph with min degree >= (n-1)/2  then G is Connected "

Comments

I don't think statement it true. You can take a spanning tree with vertex 4. It's will give 2 vertices with degree 2 and 2 vertices with degree 1. But statement says that minimum degree ≥(n-1)/2 which will be 1.5

---

@Rishav Kumar Singh,

the statement "If G is simple n vertex graph with min degree >= (n-1)/2  then G is Connected "

but you are assuming it as converse, i mean

the statement "If G is simple n vertex graph and Connected then G should have min degree >= (n-1)/2  "

---

@shaik sir you are right.

Answer 1

Relative Complement:-

if A is a set then complement is A'

relative means we have to compare two sets let A and B

the relative complement of B = B-A

the relative complement of A = A-B

reference https://en.wikipedia.org/wiki/Complement_(set_theory)#Relative_complement

 

it is applicable to graphs also

if there a graph G, let it's subset is H

then the relative complement of G w.r.to H = G-H ( i mean delete those edges from G which are in H)

reference http://www-math.ucdenver.edu/~wcherowi/courses/m4408/gtaln2.html

---

---

If G is simple n vertex graph with min degree ≥ $\frac{(n-1)}{2}$  then G is Connected

proof by contradiction :-

let the graph is disconnected, therefore atleast two components exist.

let K1 and K2 are components with N1 and N2 vertices respectively, ( N1 + N2 = N )

given that every vertex degree ≥ $\frac{(n-1)}{2} $ ===> for minimum consider every vertex degree = $\frac{(n-1)}{2}$

in a simple graph with n vertices have maximum degree 'n-1' ===> if a vertex degree = n-1 then there exist atleast n vertices

 

in K1, every vertex degree = $\frac{(n-1)}{2}$ ===> there should exist atleast $\frac{(n-1)}{2} + 1 $ vertices

∴ N1 = $\frac{(n-1)}{2} + 1 $ = $\frac{(n+1)}{2} $

 

in K2, every vertex degree = $\frac{(n-1)}{2}$ ===> there should exist atleast $\frac{(n-1)}{2} + 1 $ vertices

∴ N2 = $\frac{(n-1)}{2} + 1 $ = $\frac{(n+1)}{2} $

 

N = N1+N2

   = $\frac{(n+1)}{2} $ + $\frac{(n+1)}{2} $

N   = N+1 ======> which leads to contradiction ==> there can't exist atleast 2 components ===> exist only 1 component ==>  Graph G should be connected