Actual responses to actual questions from students of Math 344, Introduction to Combinatorics (Spring 2004).
What was that extra question from class about Problem 3?
Is it possible to find such a G (as in Problem 3) whose complement does not have an Euler cycle?
I know how to get a graph G and its complement both have an Euler cycle, but no clue how to find the one does not have an Euler cycle. Can you help?
When does a graph have an Euler cycle? If this condition is true for G, must it also be true for G's complement?
What does this question really mean? I don't understand it, could you tell me how to solve this problem?
The question asks about the definition of an Euler cycle. Remember that we say a cycle is an Euler cycle if (a) it passes through every edge precisely once, and (b) it passes through every vertex. Part (b) seems like an extraneous requirement -- doesn't (a) ensure that (b) holds? No, it doesn't, and this problem asks you to explain why.
I have difficult to understand the question regarding subsequence. Could you just tell me what the graph looks like and hint how to solve this problem?
Each vertex represents a sequence of two binary digits, so our vertices are {00,01,10,11}. The edges are directed, with each edge representing a sequence of three binary digits. Thus 010 is an edge from 01 (the first two digits) to 10 (the last two digits). This is what the graph looks like.