Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
The complete bipartite graph joins each of left vertices to each of right vertices. Consider all pairs with , which is graphs.
Find the degrees in . Find how many of the graphs have an Euler circuit. Then find how many have an Euler trail that is not a circuit, and list them. Every is connected, so only the degrees matter.
A tree on vertices has edges; a forest with components has . Bipartite means no odd cycle; with no triangle, . A connected graph has an Euler circuit when all degrees are even, and an Euler trail when exactly two are odd.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Step 1. Degrees. Each left vertex has degree ; each right vertex has degree .
Step 2. Circuits. All degrees are even when and are both even: , , , , , . That is graphs.
Step 3. Exactly two odd vertices. If is odd, the left vertices are odd; if is odd, the right vertices are odd.
Step 4. Count. graphs: , , and .
Answer: graphs with an Euler circuit and with a trail only.
Log in to join the discussion.
Loading…