# 2 math questions about graph.

• Dec 6th 2012, 09:06 AM
kakatomy
2 math questions about graph.
1. If G is a simple graph with 18 edges and its complement G also has 18 edges, how many vertices does G have?

2. Fix a constant integer k 3. Suppose that a connected planar simple graph with e edges and v vertices contains no simple circuits of length k or less.
Show that
e ≤ [(k+1)/(k-1)](v 2) if v ≥ ⌈ (k+3)/2.

I have weak basis on graph.. sigh.. thanks much
• Dec 6th 2012, 09:53 AM
emakarov
Re: 2 math questions about graph.
1. Note that if you take edges from G and its complement, you'll get a complete graph.

2. This seems to be a generalization of the problem considered in this thread (where k = 3).
• Dec 6th 2012, 09:55 AM
Plato
Re: 2 math questions about graph.
Quote:

Originally Posted by kakatomy
1. If G is a simple graph with 18 edges and its complement G also has 18 edges, how many vertices does G have?

If $\displaystyle G$ has $\displaystyle n$ vertices and so does its complement, $\displaystyle \overline{G}$.

We know that $\displaystyle G\cup\overline{G}=K_n$.

Thus $\displaystyle \binom{n}{2}=36.$ Solve for $\displaystyle n$.