MTH4140 Home

MTH 4140: Midterm 1 Practice 2

Problem 1

  • (a) Provide an example of a simple graph that has \(5\) vertices and \(7\) edges;

  • (b) Determine the complement of the graph you created in part (a) of the problem.

Problem 2

Which of the pictures below can be drawn without lifting the pen from the paper and without tracing the same line twice?

\(\quad\) \(\quad\)

Problem 3

Determine which pairs of graphs below are isomorphic.

\(\quad\) \(\quad\)

Problem 4

Provide example of two relations on the set \[ G=\{{a},{b},{c},{d}\}\] such that one of them is transitive and the other is not transitive.

Problem 5

The sequence \( (R_n)_{n=0}^{\infty} \) satisfies \( R_1=6 \) and \[ R_{n+1}=9R_n+24,\quad\mbox{for }n\geq 1.\] Use the principle of mathematical induction to prove that \( R_n=9^n-3 \) for every integer \( n\geq1 \).

Problem 6

Does there exist a simple graph with \( 42 \) vertices \( V_1 \), \( V_2 \), \( V_3 \), \( \dots \), \( V_{42} \) such that the degree of each of the vertices \( V_6 \), \( V_7 \), \( \dots \), \( V_{42} \) is \( 1 \), while the degrees of \( V_1 \), \( V_2 \), \( V_3 \), \( V_4 \), and \( V_5 \) are \( 21 \), \( 12 \), \( 6 \), \( 5 \), and \( 8 \), respectively?

Problem 7

Prove that for each integer \(k\geq 2\) there exists a triangle-free simple graph \(G\) that is not bipartite and whose each vertex has degree \(k\).