Connectedness

Let G be a graph of order n such that deg(v)>=(n-1)/2. Prove that G is connected.

Vertex-arboricity

Let G be k-critical graph with respect to vertex-arboricity (k>=3). Prove that for each vertex v of G, the graph G-v is not (k-1)-critical with respect to vertex-arboricity.

Euler's Formula

IF G is a connected plane graph with n vertices, m edges and r regions, then n-m+r=2

Domination number

Determine (without proof) a formula for the domination number of path Pn.

Prove Connectedness

Prove that G with at least (n-1)(n-2)/2+1 edges is connected, where n is the order of G.