# Some relation about a simple graph

I have seen some relation about the simple graph $G$ which is not directed.

Suppose $G$ has $n=|V|\ge1$ vertices, $m$ edges, $k$ connected components, $p$ odd cycles, $q$ even cycles. Do the following hold?

1. $p+q\ge 1$ then $m\ge n$

2. $p+q=1, k=1,$ then $m=n$

3. $k\ge n-m$

4. If $p = 0$, then $G$ is bipartite.

5. If $q = 0$, then there are $2k$ proper colorings of $G$ using $2$ colors.

Attempts: For question i, I believe it is False as we may have many isolated vertices. for question 2 i think it is true. $p+q=1$ mean there exist cycle and k=1 mean that it is a connected graph. I believe it is true but then i have no idea how to show m=n.

for Q4, i think that it is true as it may a graph with no cycle is bipartile and also a graph with even with even cycle only seems to be a bipartitle too.

For question 5 i think it is false as for the case that the graph has no cycle, q=0 but we cna actually colour with 2 colours.

Is my interpretation or guess true? and is there any hints about the proof of some details?

-
What have you tried so far? Also, what is $q$? If this is homework, please tag it as such. –  01000100 May 26 '13 at 4:37
@DanielPietrobon See edited –  johnny May 26 '13 at 7:00

It seems the following.

2. When you delete one edge from the cycle you should obtain a tree. By induction you can show that $|V(T)|=|E(T)|+1$ for each three $T$.
3. For each connected component $G_i$ of the graph $G$ should be $|V(G_i)|\ge|E(G_i)|+1$. Adding these inequalities for all components, we obtain the inequality $k\ge n-m$.
4. For each $i$ fix a vertex $v_i\in G_i$, and let $A_0$ be the set of all $x_i$. Put $A=\{u\in V(G): \exists v\in A_0$ and a path from $v$ to $u$ with even length $\}$ and $B=V(G)\backslash A$. Show that $V(G)=A\cup B$ is the required partition.
5. The triangle graph $K_3$ has no even cycles and no vertex 2-colorings.