Discrete Structures Homework 3

COT-3100 Discrete Structures, Fall 2017

Assignment 4: Chapter 10

Due Date: 4/17/2018 at 11:55 PM

1. Let G be a graph such that V (G) = {v1, v2, v3, v4} and E(G) = {e1, e2, e3}. If e1 is incident on v1 and v4, e2 connects v3 and v4, and v2 is the only endpoint of e3, answer the following question:

(a) (5 points) Draw the graphical representation of graph G.

(b) (9 points) Find three different walks from v1 to v3 and specify whether each one of them is a path/trail from v1 to v3.

(c) (10 points) Construct the adjacency matrix of G.

(d) (9 points) Draw three different subgraphs of G.

(e) (6 points) Find all of the connected components of G. Is G connected?

2. (21 points) Find 7 non-isomorphic graphs with three vertices and three edges.

3. (10 points) Prove that the complete bipartite graph K4,6 has an Euler circuit.

4. (10 points) Prove that the complete bipartite graph K5,5 has a Hamiltonian circuit.

5. (10 points) Prove that the complete bipartite graph K3,5 has no Hamiltonian circuit.

6. (10 points) Prove that for every positive integer n, the complete graph Kn has an Euler circuit if and only if n is odd (Prove both directions).

1