Exercises

Problems that are mostly based on the main contents

Feel free to refer to the glossary as well

Ex.1 Show an example for a simple graph G so that both G and its complement have a Hamiltonian cycle.

Ex.2 Find the graph G that satisfies the conditions of the Ex.1 with a minimum order.

Ex.3 How many digraphs are there on vertex set {1, 2, 3} that have three edges? The graphs aren't necessarily simple.

Ex.4 For which values of n does there exist a balanced tournament on n vertices? (hint: Theorem 5)

Ex.5 Does there exist a tournament with exactly two Hamiltonian paths?

Ex.6 Let G be a loopless graph. Prove: there exists an orientation of G(assignment of directions to the edges) such that there is no directed cycle. (useless hint: gradient theorem)

Ex.7 Let G be a simple graph on 10 vertices and 28 edges. Prove: G contains a cycle of length 4.

Ex.8 Let G be a simple graph on 9 vertices, and assume that the sum of degrees is at least 27. Prove: there is a vertex with degree of at least 4.

Ex.9 Is there a simple graph on 6 vertices with ordered degree sequence {4, 4, 4, 2, 1, 1}?

Ex.10 Let G be a simple graph having 10 vertices and 38 edges. Prove: G contains \(K_4\) as an induced subgraph.

Ex.11 How many different simple graphs are there on the vertex set {1, 2,..., n}?

Ex.12 Prove: {4, 4, 3, 2, 1} isn't a degree sequence of a simple graph on 7 vertices.

Ex.13 Is it true that the number of people currently living on our planet and having an odd number of sibling(s) is even?

Ex.14 Prove: if in a simple graph, there is a trail or a walk from vertex A to B, then there is also a path from A to B.

Ex.15 How many Hamiltonian cycles does \(K_n\) have?

Ex.16 Ten players participate in a chess tournament. 11 games have been played. Prove: there is a player who has played at least three games.

Ex.17 Prove: a k-regular, simple graph contains a cycle of length at least k+1.

Ex.18 Several people are in a classroom. Some of them know each other. It's true that for any two people knowing the same amount of people, there is no one who they both know. Prove: there is someone in the classroom who knows exactly one other person.

Ex.19 There are 90 alumni, each has 10 friends among the other alumni. Prove: each alumnus can invite three alumni for lunch such that each of the four people at the lunch table will know at least two of the other three people.

Ex.20 At most how many edges can a simple graph G on n vertices have if G isn't Hamiltonian?

Ex.21 Is there a simple graph on 7 vertices such that it's not connected and each vertex has a degree of at least 3?

Ex.22 A tournament is "transitive" if the fact that there is an edge from vertex i to j and from vertex j to k implies the fact that there is a vertex from i to k. How many transitive tournaments are there on {1, 2,..., n} as a vertex set?

Ex.23 Prove: a tournament is transitive if and only if it has one Hamiltonian path.

Ex.24 Is it true that a directed graph with a finite order and no directed cycles has at least one vertex whose outdegree is 0?


Last updated: 7/11/2023