- Thread starter
- #1

#### Mathelogician

##### Member

- Aug 6, 2012

- 35

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.

===============================================

Regards.