# Math Help - graphs

1. ## graphs

Hello

I have a couple questions about graphs that I am not sure about...

1. If a graph contains a cycle that includes all the edges, the cycle is an Euler cycle. My answer: Yes, by the definition of the Euler cycle - a cycle in a graph G that includes
all of the edges and all of the vertices of G is called an Euler cycle.

2. Find a formula for the number of edges in Km,n . Answer: m*n. But not sure how to prove that...

3.Find a formula for the number of edges in Kn . Answer: (n(n-1))/2. But not sure how to prove that...

Thank you.

2. ## Re: graphs

Originally Posted by tinabaker
1. If a graph contains a cycle that includes all the edges, the cycle is an Euler cycle. My answer: Yes, by the definition of the Euler cycle - a cycle in a graph G that includes
all of the edges and all of the vertices of G is called an Euler cycle.
No, this is an incorrect definition of a Euler cycle.

Originally Posted by tinabaker
2. Find a formula for the number of edges in Km,n . Answer: m*n. But not sure how to prove that...
Use the rule of product: first select a vertex in one set and then a vertex in the other set to which it is connected.

Originally Posted by tinabaker
3.Find a formula for the number of edges in Kn . Answer: (n(n-1))/2. But not sure how to prove that...
Each vertex has n - 1 adjacent edges. This counts each edge twice.

3. ## Re: graphs

thank you for help with 2 and 3! but ...hm...the definition of an Euler cycle is from my book.

4. ## Re: graphs

Originally Posted by tinabaker
the definition of an Euler cycle is from my book.
Would you mind writing a direct quotation from your book? I also thought the answer to the first question is yes at first, but then I reviewed the definition and saw that there is a difference.

5. ## Re: graphs

I copied and pasted here.
"In honor of Euler, a cycle in a graph G that includes all of the edges and all of the vertices of G is called an Euler cycle." (page 391) Discrete Mathematics, Seventh Edition

6. ## Re: graphs

OK, my bad. Apparently, the definition of a cycle in your book requires that vertices are not repeated. Wikipedia says this here: "Like path, this term [cycle] traditionally referred to any closed walk, but now is usually understood to be simple [i.e., no vertices (and thus no edges) are repeated] by definition." The reason I objected was that Euler cycle includes each edge exactly once. But if a cycle includes any edge no more than once by definition, then it is possible to say that Euler cycle is a cycle that contains all edges.

7. ## Re: graphs

Spasibo.
P.S. Are you russian?

8. ## Re: graphs

Pozhaluista. Yes.

9. ## Re: graphs

ochen' prijatno poznakomitsja s takim ymnym chelovekom:-)