MHB Some basic questions on Graph theory

[Mathelogician]

Hello everybody!
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.

 

[caffeinemachine]

Hello everybody!
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.

Hello Mathelogician.
I can help you on a few of these.

For the first one induction on the order of $G$ can be used. There are two cases.
Case 1: There exists a cycle, say $C$, in $G$. Show that $C$ is actually a component. Delete $C$ to form $H=G-C$. Note that $H$ again satisfies $\Delta(H)\leq 2$ and has order strictly less that order of $G$. Induction sets in. Don't forget to show the base case.
Case 2: There are no cycles in $G$. Then Take any maximal path $P$ in $G$ and show that this is a component of $G$. Rest is same as in case 1.

For the third one see How many different possible simply graphs are there with vertex set V of n elements - MathOverflow

I don't understand the fourth question. Why is the term 'weighted' appearing in there?

For the fifth of course we assume that the graph is connected. So it has a spanning tree say $T$. Every tree has at least two leaf nodes. Choose any two leaf nodes in $T$. Deleting these doesn't disconnect $G$. (why?)

I will get back on the second one in some time.

P.S. Read the forum rules. I don't think one is allowed to post more than two questions in one post. Also, you are required to show your attempt when you post the questions. One more thing, try posting using LaTeX. You can read the LaTeX forum on the homepage for help on this.

 

[caffeinemachine]

Hello everybody!
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.

The second question is very hard. See https://docs.google.com/viewer?a=v&...qG6Lz7&sig=AHIEtbTPDEPPZXjMJHOtdiFvCZU4CNmUfA