Suppose G=(V,E) is a simple undirected graph with no self-loop; moreover, the graph G has n=|V| $\ge$ 1 vertices, m=|E| edges, k connected components, p odd cycles, q even cycles and chromatic number X. Determine if the following is true. (1) if p+q = 0, then m $\le$ n-1 (2) if p+q = 0, then the graph is planar (3) if p=3, then X=2 (4) if the graph is planar, then X$\ge$k (5) if X=n, then m=$\frac{n(n-1)}{2}$

Question

<Graph theory>
Suppose G=(V,E) is a simple undirected graph with no self-loop; moreover, the graph G has n=|V| $\ge$ 1 vertices, m=|E| edges, k connected components, p odd cycles, q even cycles and chromatic number X.

Determine if the following is true.
(1) if p+q = 0, then m $\le$ n-1
(2) if p+q = 0, then the graph is planar
(3) if p=3, then X=2
(4) if the graph is planar, then X$\ge$k
(5) if X=n, then m=$\frac{n(n-1)}{2}$

anonymous · Answer

(1) p+q =0 -> there is no cycle
So, the graph may look like this:
|dw:1387287918900:dw|

experimentx · Answer

i) looks true

anonymous · Answer

In the above example, m=6, n=7
m = n-1
Looks true

anonymous · Answer

For (2), I think I can find a counter-example:
|dw:1387288135412:dw|
No cycle, but the two line cross each other => not planar

experimentx · Answer

this graph is same as |dw:1387288352393:dw|