Graphs and Trees
(5) Draw the picture of the specified graph (including any isolated vertices): Graph H has vertex set and edge set with edge-endpoint function as follows:
(6) Are the sequences in parts a and b graphic? Explain your answer.
4, 3, 3, 2, 1.
6, 3, 2, 2, 1, 0.
(6) Suppose a graph has vertices of degrees 0, 2, 2, 3, and 3. How many edges does the graph have? Explain your answer.
(8) Definition: denotes a complete bipartite graph of (m, n) vertices. A Kn is a complete undirected graph of n vertices.
How many vertices are there in a Km,n?
How many edges are there in the graph ?
What is the total degree of the graph ?
Draw K3,3
(6) Consider the following graph:
Does a Hamiltonian path exist? If so describe it. If not say why not.
Does an Eulerian path exist? If so describe it. If not say why not.
(7) For each graph, determine whether an Eulerian circuit exists. If the graph does not have an Eulerian circuit, explain why. If it does have an Eulerian circuit, describe one by listing all vertices in the circuit.
(4) What is the minimum number of colors that are needed to color the vertices of a K5 graph such that no adjacent vertices have the same color? Why?
(8) Let the undirected graph G = (V, E) be a tree. Prove that by adding one edge to G you create a cycle in G.
