EECS 203: Discrete Mathematics

Fall 2024

Homework 5

Reminders

• A graph (with no other descriptors) means a graph with no edge weights or edge directions. We will say weighted graph or directed graph if we wish to discuss a graph that does have these (and you should do the same in your answers).

• The graph Cn is the cycle on n nodes. The graph Kn is the clique on n nodes. The graph Ka,b is the a × b biclique. There are pictures of these graphs at the beginning of Lecture 10.

• The degree of a node v in a graph, written deg(v), is the number of edges that contain v. In a directed graph, the out-degree deg+ (v) is the number of directed edges that contain v as their first node (pointing out of v), and the in-degree deg− (v) is the number of directed edges that contain v as their second node (pointing into v).

• A k-coloring of a graph is an assignment of one of k different “colors” to each node of the graph, in such a way that for every edge (u, v), u and v are assigned different colors. A graph is k-colorable if there exists a k-coloring. A graph is bipartite if it is 2-colorable.

• A path is a contiguous sequence of nodes and edges in a graph. A path is simple if it does not repeat nodes or edges. An Euler path is a path that contains every edge in the graph exactly once. A graph is connected if there exists at least one path between any pair of nodes. A tree is a graph with exactly one simple path between each pair of nodes. The distance between two nodes u, v in a graph G, written distG(u, v), is the length of the shortest path from u to v.

• An isomorphism between graphs G and H is a relabeling of the nodes of G that makes it equal to H. An invariant is a graph property that does not change under isomorphism.

• The notation H ⊆ G means that H is a subgraph of G, and H G means that H is not a subgraph of G.

• A graph is planar if it can be drawn in two dimensions without any of its edges crossing each other.

Mechanical Problems

1. All Over The Map [10 points]

Let G = (V, E) be a graph of the United States where V is the set of all 50 states, and E contains all pairs of states that share a border. For reference, a map is given below.

Note: AZ and CO do not share a border, nor do UT and NM, nor do CT and NJ.

(a) Is G connected?

(b) Is G bipartite?

(c) Is G 3-colorable?

(d) Show that C43 ̸⊆ G. (Hint: could a C43 subgraph include the node corresponding to ME? What about MA?)

Briefly explain your answers, but a formal proof is not required.

2. Mighty Morphin’ [12 points]

For each of the following pairs of graphs, either state an isomorphism from the first graph to the second, or state and briefly explain an invariant satisfied by one graph but not the other.

(a)

(b)

(c)

3. Quick Draw [16 points]

For each of the following, either draw a graph satisfying the description or explain why one cannot exist.

(a) A planar graph with at least 1 node, in which all nodes have degree at least 4

(b) A graph with exactly 8 nodes, two non-intersecting independent sets of size 4, and a C5 subgraph

Note: An independent set is a set of nodes with no edges between any two nodes in the set.

(c) A tree with exactly 1 node of degree 5 and exactly 4 nodes of degree 1 (and possibly some additional nodes beyond these)

(d) A graph with exactly 10 nodes, exactly 24 edges, and four K2,3 subgraphs that do not share edges with each other.

Bad Proofs

We have given an incorrect “proof” of the following proposition that attempts to show that it is true. Identify the specific logical error made by citing a sentence, equation, step, or missing part of the argument, and briefly explain why it is wrong.

4. Eulerian Error [8 points]

Proposition. There exists a connected graph with two or fewer nodes of odd degree, but which does not have an Euler path. (Note: this proposition contradicts Euler’s Theorem, covered in lecture.)

Incorrect Proof. Let G = (V, E) be a connected graph that has only one node of odd degree, called u. Suppose for contradiction that there is an Euler path P in G.

Since u has odd degree, and all of the edges that contain u are used exactly once by P, it must be that u acts as one but not both endpoints of P. So the other endpoint of P is a different node v ≠ u, and since u is the only node with odd degree, that means deg(v) is even.

The last edge of P must contain v, and every other instance of v in P uses two of the edges that contain v. Therefore P uses an odd number of edges in total that contain v. Since deg(v) is even, this means there is at least one edge that contains v, but which was not used by P. This contradicts that P is an Euler path, completing the proof.

Discovery Problems

5. Light Work [16 points]

You have 6 batteries, among which exactly 3 are currently charged, but you can’t remember which ones they are. Your flashlight takes two batteries. If both batteries are charged, then the flashlight will turn on. If either battery is uncharged, then it will not turn on.

Proposition. It is possible to guarantee that the flashlight will turn on by trying only 6 battery pairs.

(a) Rephrase the proposition as a statement about graphs by filling in the blank:

“There exists a graph with 6 nodes, 6 edges, and                                                   .”

Explain why your proposition is equivalent to the one about flashlights above.

(b) Prove the proposition about graphs that you stated in the previous part.

6. Competitive Edge [20 points]

A round-robin tiddlywinks tournament is held, meaning that every pair of players plays one match against each other, and one player or the other wins each match (there are no draws).

• A player is a winner if they won the most games of any player. There can be multiple winners, if they are all tied for the most games won.

• A player p is dominant if for every other player q, either p beat q, or there exists a player r such that p beat r and r beat q.

Proposition. Every winner is dominant.

(a) Rephrase the proposition as a statement about graphs by filling in the blanks:

“Let T = (V, E) be                                                                    .

Then for any node w satisfying                                                  ,

and for any other node x, we have distT (w, x) ≤ 2.”

Explain why the proposition you completed is equivalent to the one about tournaments above.

(b) Prove the proposition about graphs that you stated in the previous part.

7. VIP Section [18 points]

A group of n people is called a club if every person in the group is friends with at least √ n other people in the group. (We assume that friendship is symmetric—if x is friends with y, then y is friends with x.)

Proposition. Within any club of size ≥ 9, there exists a group consisting of only 3 or 4 of its members who form. a club with each other.

(a) Rephrase the proposition as a statement about graphs by filling in the blanks. (In each “graph name” blank, you must write the name of one graph mentioned in class; e.g., do not write “a three-person club.”)

“Let G be a graph with n ≥ 9 nodes in which                                   .

Then G has           graph name         or          graph name          as a subgraph.”

Explain why your proposition is equivalent to the one about clubs above.

(b) Prove the proposition about graphs that you stated in the previous part. (Hint: in order to build intuition, it might help to draw a graph from your proposition with n = 9.)