Thread: 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.

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.

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

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.

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

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.

Spasibo.
P.S. Are you russian?

Pozhaluista. Yes.

ochen' prijatno poznakomitsja s takim ymnym chelovekom:-)