Exam 15: Graph Theory

James, Carl, Mark, Antonio, Phillip, and Brad are friends at college. Carl, Antonio and Phillip have calculus together. Brad, Carl, and Mark have the same English composition class. Draw a graph with vertices representing students and edges representing the relation "take a common class". How many components does the graph have? Identify a subgraph that is a complete subgraph with three vertices.

Determine whether the graph is a complete graph. -

Determine whether the sequence of vertices is an Euler circuit. - $\mathrm { C } \rightarrow \mathrm { D } \rightarrow \mathrm { E } \rightarrow \mathrm { B } \rightarrow \mathrm { A } \rightarrow \mathrm { E }$

Determine whether the graph is a complete graph. -

Determine how many vertices and how many edges the graph has. -

Determine whether the graph is a complete graph. -

Represent the following with a graph. -

Determine whether the two graphs are isomorphic. If they are, illustrate the isomorphism. -(a) (b)

Determine whether the sequence of vertices is i)a walk, ii)a path, iii)a circuit in the given graph. - $\mathrm { A } \rightarrow \mathrm { E } \rightarrow \mathrm { B } \rightarrow \mathrm { H } \rightarrow \mathrm { F }$

Determine whether the sequence of vertices is an Euler circuit. - $\mathrm { A } \rightarrow \mathrm { B } \rightarrow \mathrm { C } \rightarrow \mathrm { A } \rightarrow \mathrm { E } \rightarrow \mathrm { C } \rightarrow \mathrm { D } \rightarrow \mathrm { E } \rightarrow \mathrm { F } \rightarrow \mathrm { A }$

Determine whether the graph is connected or disconnected. -

Determine whether the sequence of vertices is i)a walk, ii)a path, iii)a circuit in the given graph. - $\mathrm { B } \rightarrow \mathrm { F } \rightarrow \mathrm { G } \rightarrow \mathrm { C } \rightarrow \mathrm { F } \rightarrow \mathrm { B }$

Determine how many components the graph has. -

Determine whether the sequence of vertices is i)a walk, ii)a path, iii)a circuit in the given graph. - $\mathrm { L } \rightarrow \mathrm { H } \rightarrow \mathrm { G } \rightarrow \mathrm { F } \rightarrow \mathrm { B }$

Determine whether the graph is a complete graph. -

Seven family members are planning a picnic. They work out the details with a few phone calls. One family member has 5 conversations, two have 3 conversations, and one has only 1 conversation. How many phone conversations are there?

Determine whether the sequence of vertices is i)a walk, ii)a path, iii)a circuit in the given graph. - $\mathrm { G } \rightarrow \mathrm { H } \rightarrow \mathrm { E }$

Determine whether the graph is connected or disconnected. -

Determine whether the sequence of vertices is an Euler circuit. - $D \rightarrow C \rightarrow B \rightarrow A \rightarrow E \rightarrow D$

Solve the problem. -An internet user is participating simultaneously in one-on-one chat sessions with 5 other people. Draw a graph with vertices representing users and edges representing chat sessions. How many chat sessions are occurring?