MAT202: Introduction to Discrete Mathematics

1.

Write the definitions for each of the following terms: graph, simple graph, vertex, edge, degree, degree sequence, trail, path, cycle, complete graph, Eulerian, subgraph, graph isomorphism, complement, connectedness, tree, forest, leaf, bipartite graph, Hamiltonian graph.

2.

List all vertices and edges of the graphs $G_1\text{,}$ $G_2\text{,}$ and $G_3\text{:}$

3.

Determine the degree sequences of the graphs $G_1\text{,}$ $G_2\text{,}$ and $G_3\text{.}$

4.

Determine which of the graphs $G_1\text{,}$ $G_2\text{,}$ $G_3$ are Eulerian, and for each one that is, find an Eulerian trail.

5.

For each nonincreasing sequence of numbers below, draw a simple graph with that degree sequence, or explain why it is impossible to do so.

1. 1,1,1,1,1
2. 1,1,1,1,1,1
3. 2,2,2,2,2,2
4. 9,3,3,2,1
5. 4,4,2,2,2
6. 4,4,3,2,1

6.

You meet with six other friends for lunch, and because you had just learned about Checkpoint 5.2.14 in class, you ask each of your friends how many in the group they shook hands with before eating. You are surprised to hear each friend reply with a different number from 1 to 6. How many hands did you shake at that lunch?

7. Winter 2016 Final.

In a group of two or more people, must there always be at least two people who are acquainted with the same number of people within the group? Explain your answer.

8.

For which natural $n\ge 3$ is $C_n$ Eulerian? How about $K_n\text{?}$ $P_n\text{?}$

9.

How many different Eulerian trails does $C_n$ have for $n\ge 3\text{?}$

10.

Find two nonisomorphic simple graphs w/ degree sequence 3,3,3,3,2,2,2,2.

11. Winter 2017 Final.

Let $G$ be a graph on $n$ vertices. It is known that there are 6 vertices which have degree 3, and all of the remaining vertices are of degree 4. Show that $G$ cannot be disconnected with exactly two isomorphic connected components.

12.

Prove that the following graphs $P$ and $Q$ are isomorphic.

13.

Are there any isomorphic graphs among $G_4\text{,}$ $G_5\text{,}$ and $G_6\text{?}$

14.

Prove that graph isomorphism is an equivalence relation on the set of all simple graphs.

15.

There are eleven simple graphs on four vertices (up to isomorphism). Find all of them.

16.

Show that the following two graphs are not isomorphic:

17.

Are there any isomorphic graphs among the following graphs?

18.

Suppose that a graph $G$ has degree sequence 3, 3, 2, 2, 2, 1, 1. What is the degree sequence of $\bar{G}\text{?}$

19.

Generalize Exercise 5.8.18. How are the degree sequences of a graph $G$ and its complement $\bar{G}$ related?

20.

Can a graph $G$ be isomorphic to its complement $\bar{G}\text{?}$ Either find an example (if yes) or prove it cannot happen (if no).

21.

Prove that $C_n$ is connected for $n\ge 2\text{.}$

22.

Prove that $K_n$ is connected for $n\ge 2\text{.}$

23.

In a graph $G=(V,E)\text{,}$ explain why a $u$-$v$ path and a $v$-$w$ path, when connected at the point $v\text{,}$ may not necessarily result in a path.

Prove that a $u$-$v$ path and a $v$-$w$ path together must contain a $u$-$w$ path.

24.

Let $G=(V,E)$ be a simple graph. Prove that the relation $\sim$ on $V$ given by

is an equivalence relation. This is called the connectedness relation on the vertices of a graph.

25.

Describe the equivalence class $[1]$ of the vertex 1 in the graph below, based on the connectedness relation defined in Exercise 5.8.24.

26.

Draw an example of each of the following graphs or explain why it is impossible:

1. A bipartite Eulerian graph
2. A forest on 7 vertices and 4 edges
3. A tree on 6 vertices that has 5 leaves
4. A connected graph whose complement is connected
5. A disconnected graph whose complement is disconnected

27. Fall 2016 Final.

Prove that any simple graph whose vertices all have degree at least ${\displaystyle \frac{n-1}{2}}$ must be connected.

28. Fall 2020 Final.

Let $n,k\in \mathbb{N}\text{,}$ and define the family of graphs $G_{n,k}=(V_n,E_{n,k})$ on the vertex set

and with edge set

In other words, two vertices $i$ and $j$ are adjacent if they are congruent modulo $k\text{.}$

1. Draw $G_{4,2}$ and $G_{7,3}$ and show they are both disconnected.
2. Show that $G_{n,k}$ is connected if and only if $k=1\text{.}$
3. Show that $G_{n,k}$ is the empty graph if and only if $n\le k\text{.}$

29.

Find an Eulerian trail in $K_{2,4}\text{.}$

30.

Prove that $K_{m,n}$ is connected for any $,n\in \mathbb{N}\text{.}$

31.

Find all pairs of natural numbers $(m,n)$ for which $K_{m,n}$ is Eulerian.

32.

Find all pairs of natural numbers $(m,n)$ for which $K_{m,n}$ is Hamiltonian.

33.

Find a Hamiltonian cycle in each of the graphs in Exercise 5.8.17.

34.

Find a Hamiltonian cycle of least cost in each of the following graphs:

35.

The graph $K_n$ is Hamiltonian for any $n\ge 3\text{.}$ How many different Hamiltonian cycles are contained in $K_n$ for $n\ge 3\text{?}$

Hint

\(K_3\) has only one, while \(K_4\) has three, shown here.

36.

For the pairs $(m,n)$ you found in Exercise 5.8.32, how many different Hamiltonian cycles are contained in $K_{m,n}\text{?}$