GRAPH THEORY and CRITICAL THINKING Jason Molitierno Sacred Heart University

GRAPH THEORY AND CRITICAL THINKING
Jason Molitierno
Sacred Heart University

1. a. A room has 7 people. Some pairs of people shake hands and some do not. Is it possible that each person shakes hands with exactly three people?
   

b. Prove that the sum of the degrees of the vertices of any graph must be even.

1. Suppose that n people attend a party and some shake hands with others (but not with themselves) . Prove that there must be at least two people who have shaken hands with the same number of people.
   
2. A man and his wife invite 5 other couples to a party, for a total of 12 people. During the party, some pairs of people shake hands, but nobody shakes his or her spouse’s hand. Later in the party, the host asks each of the others (including his wife) how many people they have shaken hands with. He gets a different answer for each person. With how many people did the host shake hands?
   
3. a. Six people are in a room. Some of the pairs shake hands. Prove that either there is a set of three people each of whom have shaken hands with the other two, or a set of three people each of whom have not shaken hands with the other two.
   

b. You are given a complete graph on six vertices. You color each edge either red or blue. Prove that there will always be a triangle all of whose sides are the same color.

c. You are given a complete graph on 17 vertices. You color each edge red, blue, or green. Prove that there will always be a triangle all of whose sides are the same color.

1. a. What criteria, in terms of the degrees of the vertices, guarantees that a graph has an Eulerian circuit?
   

b. What criteria, in terms of the degrees of the vertices, guarantees that a graph has an Eulerian path (but not an Eulerian circuit)?

1. A cat C chases a mouse M on the graph below. The cat goes first and can move to any neighboring vertex. The mouse then moves and can also move to any neighboring vertex. The cat wins if it can reach the mouse. Assuming the mouse doesn’t commit suicide by running into the cat, can the cat catch the mouse?

DEFINITIONS

A graph is an object consisting of points, called vertices, and lines, called edges, joining pairs of the vertices.

Pairs of vertices with an edge joining them are said to be adjacent.

A graph is complete if all pairs of vertices are adjacent.

The degree of a vertex is the number of edges incident to a vertex.

An Eulerian circuit exists if you can traverse the graph by beginning at a vertex, and traverse each edge exactly once, and end at the vertex you at which you began.

An Eulerian path exists if you can traverse the graph by beginning at a vertex, and traverse each edge exactly once, but you end at a different vertex than which you began.

A graph is bipartite if the vertex set can be divided into two subsets U and V so that each vertex belongs to exactly one of U or V, no two vertices in U are adjacent, and no two vertices in V are adjacent.

SOURCES

A Mathematical Mosaic, by Ravi Vakil