代写COMP2121A、代写Java/Python程序

日期：2022-12-04 02:47

COMP2121A: Discrete Mathematics

Homework 3 Due Date: Dec 2, 2022

Rules: Discussion of the problems is permitted, but writing the assignment together is not

(i.e. you are not allowed to see the actual pages of another student).

Course Outcomes

[O1. Abstract Concepts]

[O2. Proof Techniques]

[O3. Basic Analysis Techniques]

1. (10 points) [O3] A path of a graph G = (V,E) is a sequence of distinct vertices

(v1, v2, ...vk) such that (vi, vi+1) ∈ E for i = 1, 2, · · · , k ? 1. A longest path is a path

P such that no other path has more vertices than P . In this problem, we suppose G

is a connected graph with |V | ≥ 3.

(a) If G has 2 longest paths, will they share at least one common vertex? Does there

exist some s > 2 such that s longest paths in a connected graph do not share

a single common vertex? (Hint: you can consider the following graph, trying to

prove that all of the longest paths of this graph do not share a common vertex.)

(b) If each vertex v ∈ V has degree at least |V |2 , what is the minimum possible length

of the longest path of G?

2. (10 points) [O3] In a graph G = (V,E), a matching M in G is a set of pairwise

non-adjacent edges, no two edges share common vertices. A vertex cover V ′ of G is

a subset of V such that (u, v) ∈ E ? u ∈ V ′ ∨ v ∈ V ′, that is to say, it is a set of

vertices V ′ where every edge has at least one endpoint in the vertex cover V ′. We

denote α the maximum size of the matching of G while β the minimum size of the

vertex cover.

(a) Prove that for any G, α ≤ β.

(b) Find an example that the equality holds in 2a.

(c) Prove that for any G, β ≤ 2α.

(d) Find an example that the equality holds in 2c.

(e) Find all situations that the equality holds in 2c (Hint: you may use the following

advanced theorem (Tutte-Berge’s Formula): If k is the minimum number of

1

vertices not covered by a matching, then there exists a subset U ? V such that

the induced subgraph on G ? U has |U | + k connected components with odd

vertices.)

3. (10 points) [O3] Let G be a k-regular graph with n vertices.

(a) If k = 3, what values can n take? For any fixed positive integer k, what values

can n take?

(b) If k = 3, will G always be Hamiltonian if n = 6? Will G always be Hamiltonian

if n = 8? Please explain your reasons or give a counterexample.

(c) A perfect matching M of a graph G = (V,E) is a matching that covers all

vertices, i.e., a subset of E such that each vertex v ∈ V appears exactly once as

an endpoint of one of the edges in M . If k = 3 and G is Hamiltonian, show that

E can be partitioned into a union of three perfect matchings.

(d) Let k = 3 and G be Hamiltonian. Assume every edge in G under this case lies

on an even number of Hamilton cycles. Using this fact, deduce that if k = 3 and

G is Hamiltonian, then G has at least three different Hamilton cycles. In this

question, a cycle is identified solely by the collection of edges it contains; there

is no particular orientation or starting point associated with a cycle.

4. (10 points) [O3] A graph G has n vertices. For every 4 vertices in G, there is a vertex

serving as the neighbor of the remaining 3 vertices. At least how many vertices are

there neighboring all other vertices in G (i.e., vertices with degree n ? 1)? Please

explain your answers.

5. (10 points) [O3] Let m and n be two positive integers. We construct a graph Gm,n

as follows:

draw m disjoint copies of K2 , each containing a red vertex and a blue vertex;

add n yellow vertices and n green vertices;

join each red vertex to every yellow vertex by an edge;

join each blue vertex to every green vertex by an edge.

(a) What is the chromatic number of Gm,n?

(b) Find all m and n for which Gm,n is Eulerian.

(c) Determine whether each of G4,5, G6,6 and G7,4 is Hamiltonian.

6. (10 points) [O3] Let G be a connected planar graph with 120 edges. We can partition

the edges into two sets, S1 and S2 with |S1| = 90 and |S2| = 30. Suppose that,

e ∈ S1, the face on one side of e has 3 edges; and the face on the other side has 10

edges. Also, suppose that, ?e ∈ S2, the two faces on each side of e are distinct from

each other and both have 10 edges. How many vertices does G have?

2

7. (10 points) [O3] Amy has a lamp in the bedroom, which shows n different colors and

the color of the lamp is decided by the states of 2 switches. Each switch has n different

states. The color of the lamp would change when both of the two switches change

their states. However, how the color of the lamp changes when one switch changes

its state while the other does not is temporarily unknown. Amy conjectures that the

color of the lamp is actually only dependent on exactly one of the switches. Please

prove or disprove the conjecture.

8. (10 points) [O3] The graph of the cube C3, sometimes called the 3-cube, can be

described as the graph whose vertices are the binary strings 000, 001, 010, 011, 100,

101, 110, 111 where two vertices are adjacent if and only if they differ at exactly one

digit. For instance 010 and 110 are adjacent because they differ only in the left-hand

digit. The vertices 010 and 100 are not adjacent because they differ at both the

left-hand digit and the middle digit.

(a) Does C3 have an Euler circuit? Is C3 a planar graph?

(b) Let C4 be the graph described similarly but with binary strings of length 4.

Thus, for instance, the vertices 0110 and 1110 are adjacent because they differ

at only one digit, but 0110 and 1100 are not adjacent because they differ at 2

digits. Does C4 has an Euler circuit? Is C4 a planar graph?

(c) Let C8 be the graph described as above, but now with binary strings of length 8

(so that there are now 256 vertices and each vertex has 8 edges). Does C8 have

an Euler circuit? Is C8 a planar graph?

9. (20 points) [O1,O3] Suppose Km,n is a complete bipartite graph whose vertices on

the left are indexed by {l1, l2, l3, ..., lm} and those on the right by {r1, r2, r3, ..., rn},

where m ≥ n ≥ 3. In this question, a cycle is identified solely by the collection of

edges it contains; there is no particular orientation or starting point associated with

a cycle.

(a) Let the size of a graph be the number of vertices in the graph. What is the max-

imum possible size of the induced subgraphs of Km,n that are Hamiltonian? Let

S be the set of all induced subgraphs with maximum size that are Hamiltonian,

what is the cardinality of S? Give your answer in terms of m and n.

(b) What is the maximum number of Hamiltonian cycles contained in any element

in S? Give your answer in terms of m and n.

(c) Let m = 10, n = 10. How many Hamiltonian cycles in Km,n contain the edge

{l1, r1}? How many Hamiltonian cycles in Km,n contain both the edges {l1, r1}

and {r1, l2}? How many Hamiltonian cycles in Km,n contain both the edges

{l1, r1} and {l2, r2}?

(d) Let m = n. How many Hamiltonian cycles in Km,n do not contain any edge

from {l1, r1}, {r1, l2} and {l2, r2}? Give your answer in terms of m and n.

(e) Let m = n. Suppose that M is a set of k ≤ n2 edges in Km,n with the property

that no two edges in M share a vertex. How many Hamiltonian cycles in Km,n

contain all the edges in M? Give your answer in terms of n and k.