Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

It seems the following.

  1. You already answered.

  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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.