Some basic questions on Graph theory!
I am a real amateur in Combinatorics. So please answer in the most basic way!
1- Suppose for a graph G we have Delta=max(deg Vi : 1<=i<=n).
If Delta<=2, prove that the graph G is made up of Paths and Cycles.
2- Suppose G is a graph of size m > (n*sqrt(n-1))/2. Prove that G has a Cycle with length of 3 or 4.
3- How many graphs of order n do exists that are not isomorphic?
4- For an arbitrary graph G show that there exists a weighted bipartite sub-graph H such that:
for all v in V(G), deg H (v)>= (deg G (v))/2.
5- Suppose that G is a graph of size m>=1. Show that G has at least 2 vertices that are not cut vertex.