MATH 350 - DISCRETE MATHEMATICS Graph Theory Question Bank Set 4

MATH 350 - DISCRETE

MATHEMATICS - Graph Theory

Question Bank - Set 4

Liberty University

Question 1

Question

Let Gbe a simple graph with 7 vertices and 10 edges. Prove that Gmust

contain a cycle of length 3.

Solution

To prove that Gmust contain a cycle of length 3, we will use the Pigeonhole

Principle.

Step 1: Determine the maximum possible number of edges in a

graph with 7 vertices. For a simple graph with nvertices, the maximum

number of edges is n

2(where n

2represents the number of ways to choose

2 vertices from nvertices). So, for n= 7, the maximum number of edges is

7

2= 21.

Step 2: Consider the complement graph of G.The complement graph

of G, denoted as G, is the graph with the same vertices as Gbut with an edge

between two vertices if and only if there is no edge between them in G.

Step 3: Note the relationship between edges in Gand G.Since G

has 10 edges, Ghas 21 −10 = 11 edges.

Step 4: Apply the Pigeonhole Principle. Consider the vertices of Gas

”pigeons” and the edges of Gas ”pigeonholes”. Each edge in Gcorresponds to

a pair of vertices in Gwith no edge between them.

Since Ghas 11 edges and we have 7 vertices, by the Pigeonhole Principle

there must be a pair of vertices with no edge between them. These vertices,

together with a third vertex connected to both, form a cycle of length 3 in G.

Therefore, Gmust contain a cycle of length 3.

Question 2

Question

Let Gbe a simple undirected graph with 12 vertices and 22 edges. Prove that

Gmust contain a cycle of length 4 or less.

Solution

To solve this problem, we will use the Pigeonhole Principle.

Step 1: Determine the maximum number of edges in a graph with

no cycles of length 4 or less. Let Gbe a graph with no cycles of length 4

or less. The smallest possible cycle is a triangle (i.e., a cycle of length 3). In a

triangle, each vertex is connected to the other two vertices. Thus, the maximum

number of edges in Gis achieved when Gis a triangle-free graph. Given that G

has 12 vertices, a triangle-free graph will have at most ⌊n

2⌋edges, where nis the

number of vertices. Therefore, the maximum number of edges in a triangle-free

graph with 12 vertices is ⌊12

2⌋= 6.

Step 2: Use the Pigeonhole Principle. If Ghas more than 6 edges,

then by the Pigeonhole Principle, there must be at least two edges incident to

the same vertex which creates a cycle of length 2. If Ghas more than 11 edges

(but less than 18 edges), then there must be at least one cycle of length 3. If

Ghas more than 18 edges (but less than 24 edges), then there must be at least

one cycle of length 4. Since Ghas 22 edges, it must contain at least one cycle

of length 4 or less.

Therefore, we have proved that in any simple undirected graph with 12

vertices and 22 edges, there must be a cycle of length 4 or less.

Question 3

Question

Let Gbe a connected graph with 10 vertices and 15 edges. If each vertex of G

has degree at least 3, what can you say about the graph G?

Solution

Step 1: We know that the sum of the degrees of all vertices of a graph is equal

to twice the number of edges. Therefore, for our graph Gwith 10 vertices and

15 edges, the sum of the degrees of all vertices is 2 ×15 = 30.

Step 2: Since each vertex has degree at least 3, the sum of the degrees of

all vertices in Gis at least 10 ×3 = 30. Therefore, the sum of the degrees is

exactly 30.

Step 3: This implies that each vertex in Gmust have degree exactly 3. If

any vertex had a degree greater than 3, the sum of the degrees would exceed

30.

Step 4: Therefore, the graph Gmust be a regular graph where each ver-

tex has degree 3. Additionally, since Gis connected, Gmust be a 3-regular

connected graph with 10 vertices and 15 edges.

Step 5: An example of such a graph is a 10-vertex cycle, where each vertex

is connected to the two vertices adjacent to it on the cycle.

Question 4

Question

Let Gbe a connected graph with 16 vertices and 32 edges. Prove that Gcontains

a cycle of length at least 4.

Solution

Step 1: Use the fact that a connected graph with nvertices and n−1 edges is

a tree.

Let Gbe a connected graph with 16 vertices and 32 edges. Since Gis

connected, it must contain a spanning tree.

Step 2: Recall that a tree with nvertices has n−1 edges.

Since Ghas 16 vertices and 32 edges, it cannot be a tree because a tree with

16 vertices would have 15 edges. Therefore, Gmust contain at least one cycle.

Step 3: Assume for contradiction that all cycles in Gare of length 3 or less.

Now, let’s assume for contradiction that all cycles in Gare of length 3 or

less.

Step 4: Use the fact that the sum of the lengths of all cycles in a graph is

equal to twice the number of vertices minus the number of edges.

The sum of the lengths of all cycles in any graph is equal to twice the number

of vertices minus the number of edges.

For our graph G, with 16 vertices and 32 edges, the left side of the equation

would be 0 (since we assumed all cycles are of length 3 or less). However, the

right side would be 16.

This is a contradiction, so our assumption that all cycles are of length 3 or

less must be false.

Step 5: Conclude that Gmust contain a cycle of length at least 4.

Thus, Gmust contain a cycle of length at least 4, as required.

Question 5

Question

Let Gbe a connected graph with 10 vertices and 17 edges. If Ghas no cycles of

length less than 4, then what is the maximum possible number of edges in G?

Solution

To maximize the number of edges in a graph with no cycles of length less than

4, we will build a graph that is a tree, which is a connected acyclic graph.

Step 1: Recall that in a tree with nvertices, there are n−1 edges. Since

Ghas 10 vertices, we can start by building a tree with 10 vertices and 9 edges.

Step 2: Now, we need to add more edges to the tree to reach a total of 17

edges. To maximize the number of edges without creating cycles of length less

than 4, we will add edges to form paths of length 3.

Step 3: We can add 8 more edges to the tree to form paths of length 3.

This brings the total number of edges to 9 + 8 = 17.

Step 4: Therefore, the maximum possible number of edges in Gis 17 .

Question 6

Question

Let Gbe a connected graph with nvertices and medges such that every vertex

has degree at least n

2. Prove that Gis Hamiltonian, i.e., it contains a Hamilto-

nian cycle.

Solution

To prove that Gis Hamiltonian, we will use the Dirac’s theorem.

Step 1: State Dirac’s Theorem

Dirac’s Theorem: Let Gbe a graph with n≥3 vertices. If every vertex in G

has degree at least n

2, then Gis Hamiltonian.

Step 2: Apply Dirac’s Theorem to the given graph

Since every vertex in Ghas degree at least n

2, we can apply Dirac’s Theorem to

conclude that Gis Hamiltonian.

Step 3: Conclusion

Therefore, the connected graph Gwith nvertices and medges, where every

vertex has degree at least n

2, is Hamiltonian.

Question 7

Question

Let Gbe a connected graph with 10 vertices and 15 edges. Prove that Gcontains

a cycle of length at most 4.

Solution

To prove that Gcontains a cycle of length at most 4, we will make use of the

Pigeonhole Principle.

Step 1: Counting edges for a path Consider a path Pof maximum

length in G. Since Ghas 10 vertices and 15 edges, the maximum length of P

is 9 (if Phas 10 vertices, then it would contain 9 edges, which is the maximum

possible). Let v1and v9be the endpoints of P.

Step 2: Neighborhood of v1and v9Since Gis connected, v1and v9

must have neighbors on Pas well as neighbors outside P. Let the neighbors of

v1not on Pbe xand y, and the neighbors of v9not on Pbe zand w.

Step 3: Using the Pigeonhole Principle Consider the paths v1−x−z−v9

and v1−y−w−v9. These paths form two internally vertex-disjoint paths joining

v1and v9, but they share the vertices v1and v9. By the Pigeonhole Principle,

one of the paths must contain a cycle of length at most 4.

Therefore, we have shown that Gcontains a cycle of length at most 4.

Question 8

Question

Let Gbe a connected graph with 12 vertices such that each vertex has degree

4 or 5. Prove that Gcontains a cycle of length 4.

Solution

To prove that Gcontains a cycle of length 4, we will use the Pigeonhole Principle.

Step 1: Count the total number of edges in the graph Let Vdenote

the set of vertices and Edenote the set of edges in graph G. Since each vertex has

degree 4 or 5, the total number of edges can be calculated using the Handshaking

Lemma:

2|E|=X

v∈V

deg(v)

where deg(v) is the degree of vertex v. Since each vertex has degree 4 or 5,

the total number of edges is between 4|V|and 5|V|. Since |V|= 12, the total

number of edges lies between 48 and 60.

Step 2: Consider the possible cases Assume that there are no cycles

of length 4 in G. This means that any cycle in Gmust have length at least 5.

Let nbe the number of edges in the longest cycle in G. Since the sum of the

degrees of the vertices is even, the total number of edges should be even. Since

each edge is shared by exactly two vertices, the length of the longest cycle must

be even. Therefore, n≥6.

Step 3: Apply the Pigeonhole Principle Since Gis connected with 12

vertices and each vertex has degree 4 or 5, we can count the total number of

edges using the Handshaking Lemma as shown in Step 1. As the total number

of edges lies between 48 and 60, and the longest cycle length is at least 6, we

can create at most 2(60)

6= 20 cycles of length 6 in G.

Step 4: Arrive at a contradiction Each cycle of length 6 uses 6 distinct

vertices. Since there are only 12 vertices in G, at least 12 vertices are repeated in

the 20 cycles of length 6. By the Pigeonhole Principle, there must be a repeated

vertex among the 20 cycles, which implies the existence of a cycle of length 4,

contradicting our assumption.

Therefore, there must exist a cycle of length 4 in the graph G.

Question 9

Question

Let Gbe a simple graph with 8 vertices and 14 edges. Prove that Gcontains a

subgraph with at least 5 vertices of degree 5 or higher.

Solution

Step 1: Let’s assume for the sake of contradiction that Gdoes not contain a

subgraph with at least 5 vertices of degree 5 or higher. This implies that the

maximum degree of any vertex in Gis at most 4.

Step 2: Since Gis a simple graph with 8 vertices, the sum of the degrees of all

vertices is equal to twice the number of edges. Thus, Pv∈Vdeg(v) = 2·14 = 28.

Step 3: If the maximum degree is at most 4, then the sum of the degrees

of all vertices is at most 8 ·4 = 32. However, this contradicts the fact that

Pv∈Vdeg(v) = 28.

Step 4: Therefore, our assumption that Gdoes not contain a subgraph with

at least 5 vertices of degree 5 or higher must be false. Hence, Gmust contain a

subgraph with at least 5 vertices of degree 5 or higher.

Question 10

Question

Let Gbe a simple graph with 9 vertices and 15 edges. Prove that Gcontains a

cycle of length at least 4.

Solution

Step 1: Let’s assume that Gdoes not contain any cycle of length at least 4.

Step 2: We know that a cycle of length nhas nedges. Therefore, if Gdoes

not contain any cycle of length at least 4, then the longest cycle in Ghas length

Step 3: Since the longest cycle in Ghas length 3, the graph can be decom-

posed into disjoint cycles and paths. If we count the number of edges in these

cycles and paths, we get:

Number of edges = 3c+p

where cis the number of cycles and pis the number of paths.

Step 4: Since the graph Ghas 9 vertices and 15 edges, we have:

Number of vertices −Number of edges + Number of components = 2

Substitute the given values:

9−15 + c+p= 2

c+p= 8

Step 5: If the longest cycle in Ghas length 3, then each cycle contributes

3 edges. Therefore, the total number of edges contributed by the cycles is a

multiple of 3, which means 3cis a multiple of 3.

Step 6: Since c+p= 8, ccan be at most 5 (as pshould be non-negative).

This implies that the remaining 3 edges in 3c+pwill be in the paths.

Step 7: However, placing 3 edges in paths would create a path with more than

two edges, thus creating a cycle of length 4, which contradicts our assumption.

Step 8: Therefore, our assumption that Gdoes not contain any cycle of

length at least 4 is incorrect. Hence, Gmust contain a cycle of length at least

Question 11

Question

Let Gbe a connected graph with nvertices and medges. Prove that if m<n−1,

then Gis disconnected.

Solution

To prove that if m<n−1, then Gis disconnected, we will use proof by

contradiction.

Step 1: Assume that Gis connected.

If Gis connected, then it must contain at least n−1 edges by definition. This

is because a connected graph with nvertices has at least n−1 edges (consider

a tree as an example).

Step 2: Contradiction.

Since m<n−1 has been given, this contradicts our assumption that Gis

connected because a connected graph with nvertices must have at least n−1

edges. Therefore, our assumption that Gis connected is false.

Step 3: Conclusion.

Since our assumption that Gis connected leads to a contradiction, we con-

clude that if m<n−1, then Gis disconnected.

Question 12

Question

Let Gbe a connected graph with 10 vertices and 22 edges. Prove that Gcontains

a cycle of length at least 4.

Solution

To prove that Gcontains a cycle of length at least 4, we will make use of the

fact that Gis a connected graph with 10 vertices and 22 edges.

Step 1: Use the Handshaking Lemma to find the average degree of vertices

in G. According to the Handshaking Lemma, the sum of the degrees of all

vertices in a graph is equal to twice the number of edges. Since Ghas 10

vertices and 22 edges, the sum of the degrees of all vertices is 2 ×22 = 44.

Therefore, the average degree of vertices in Gis 44

10 = 4.4.

Step 2: Use the Pigeonhole Principle to find a vertex with degree at least 5.

If the average degree of vertices is 4.4, by the Pigeonhole Principle, there must

exist a vertex in Gwith degree at least 5. Let vbe a vertex in Gwith degree

at least 5.

Step 3: Follow the path to find a cycle. Start from vertex vand follow its

edges. Since vhas degree at least 5, there must be at least 5 edges incident to v.

Follow a path of distinct vertices until you encounter a vertex that has already

been visited. This forms a cycle.

Step 4: Analyze the cycle found. The cycle found in Step 3 has length at

least 4 because it starts and ends at the same vertex v, and there are at least 4

distinct vertices in the path.

Therefore, we have proven that the connected graph Gwith 10 vertices and

22 edges contains a cycle of length at least 4.

Question 13

Question

Let Gbe a simple graph with 12 vertices and 28 edges. Prove that Gcontains

a cycle of length at least 4.

Solution

To prove that Gcontains a cycle of length at least 4, we will use the Pigeonhole

Principle.

Step 1: Find the number of edges in the complete graph K12.A

complete graph Knhas n(n−1)

2edges. For n= 12, the complete graph K12 has

12×11

2= 66 edges.

Step 2: Consider the complement of G, denoted by G.Since Ghas

28 edges, the complement Ghas 66 −28 = 38 edges.

Step 3: Apply the Pigeonhole Principle to the vertices of G.Each

vertex in Gis adjacent to 11 other vertices, which means each vertex in Gis

adjacent to 11 vertices in Gor G. By the Pigeonhole Principle, there must be

a vertex vin Gwith at least 7 edges connecting it to vertices in either Gor G.

Step 4: Consider the neighbors of vertex v.Since vertex vhas at least

7 edges connecting it to other vertices in Gor G, at least 7 of its neighbors are

in Gor G.

Step 5: Construct a cycle of length at least 4. Let w1, w2, . . . , w7be

the neighbors of vertex vin Gor G. If there exists an edge between any two of

wi’s, we would have found a cycle of length at least 4. Otherwise, since there are

7 vertices and each can only connect to 4 others or fewer (due to the condition

of not forming an edge), there must be two vertices that are not connected,

forming a length-2 path. Adding the edge connecting these two vertices to v

gives a cycle of length at least 4.

Question 14

Question

Let Gbe a connected graph with nvertices and medges, where m>n. Prove

that Ghas a cycle.

Solution

To prove that Ghas a cycle, we will use the fact that in a connected graph with

nvertices and medges, the graph is a tree if and only if m=n−1.

Step 1: Assume for the sake of contradiction that Gis a tree.

If Gis a tree, then m=n−1. However, given that m>n, this results in a

contradiction.

Step 2: Therefore, Gis not a tree.

Since Gis not a tree, it must contain at least one cycle.

Step 3: Conclusion

Therefore, the graph Gmust contain a cycle.

Question 15

Question

Let Gbe a connected graph with 10 vertices and 18 edges. Prove that Gcontains

a cycle of length at least 4.

Solution

Suppose for the sake of contradiction that Gdoes not contain a cycle of length

at least 4. Then all cycles in Gmust be of length 3 or less.

Step 1: Counting edges in a simple graph

In a simple graph with nvertices, the maximum number of edges is given by

n

2=n(n−1)

2. If Ghas 10 vertices and 18 edges, this implies that Gis not a

simple graph.

Step 2: Counting sum of degrees in a graph

By the Handshaking Lemma, the sum of the degrees of the vertices in a graph

is equal to twice the number of edges. That is, Pv∈Vdeg(v) = 2|E|. In our

case, this becomes Pv∈Vdeg(v)=2·18 = 36.

Step 3: Relationship between cycle length and vertex degrees

Assume that all cycles in Gare triangles. Since a triangle has 3 edges and 3

vertices, each vertex in a triangle must have degree at least 2. Thus, in a graph

containing only triangles, the sum of the degrees must be at least 3n(where n

is the number of vertices). Since the sum of the degrees in Gis 36, n≤12.

Step 4: Conclusion

We have shown that Gmust have at most 12 vertices in order for it to consist

only of cycles of length 3. However, since Ghas 10 vertices, there must be a

cycle in Gwith a length greater than 3. This contradicts our initial assumption,

so Gmust contain a cycle of length at least 4.

Question 16

Question

Let Gbe a connected graph with 12 vertices and 17 edges. Prove that Gcontains

at least one cycle.

Solution

Step 1: Let’s first establish a useful theorem.

Theorem: If Gis a connected graph with nvertices and medges, where n>m,

then Gcontains at least one cycle.

Step 2: Given that Gis a connected graph with 12 vertices and 17 edges,

we have n= 12 and m= 17.

Step 3: Since n>m, by the theorem stated in Step 1, we can conclude that

Gcontains at least one cycle.

Step 4: Therefore, the graph Gmust contain at least one cycle, as required.

Question 17

Question

Let Gbe a connected graph with 10 vertices and 14 edges. If Gcontains 3

bridges, what is the minimum number of edges that can be removed from Gto

obtain a connected graph?

Solution

Let nbe the number of vertices in the graph Gand let mbe the number of

edges.

Step 1: Finding the minimum number of edges in a connected graph with

nvertices. A connected graph with nvertices has at least n−1 edges. This is

known as the Handshaking Lemma.

Therefore, the minimum number of edges in a connected graph with 10

vertices is 10 −1 = 9.

Step 2: Calculating the minimum number of edges that can be removed

from G. Since Ghas 14 edges and 3 bridges, there are 14 −3 = 11 edges that

are not bridges.

To obtain a connected graph, we need at least 9 edges. Since there are 11

non-bridge edges already in G, we can remove 11−9 = 2 non-bridge edges while

keeping all bridges intact.

Thus, the minimum number of edges that can be removed from Gto obtain

a connected graph is 2 .

Question 18

Question

Let Gbe a simple graph with 7 vertices such that each vertex has degree at

least 4. Prove that Gcontains a cycle of length at least 4.

Solution

To prove that Gcontains a cycle of length at least 4, we will use the Pigeonhole

Principle.

Step 1: Counting edges in GSince each vertex in Ghas degree at least

4, the total number of edges in Gis at least 4×7

2= 14 (using Handshaking

Lemma).

Step 2: Assume the contrary Suppose Gdoes not contain a cycle of

length at least 4. This implies that any cycle in Ghas length 3 or less.

Step 3: Counting edges in cycles Consider any cycle in Gof length 3.

Since a cycle of length 3 requires 3 edges, and any pair of vertices in a cycle of

length 3 are connected by an edge, the number of edges in all cycles of length 3

is 3 ×number of cycles of length 3.

Step 4: Applying the Pigeonhole Principle Let xbe the number of

cycles of length 3 in G. From Step 3, we know that the total number of edges

in all cycles of length 3 is 3x. Since the total number of edges in Gis at least

14 (from Step 1), we have 3x≤14.

Step 5: Conclusion From Step 4, we have 3x≤14, which implies x≤

3. However, since xmust be a whole number (number of cycles cannot be a

fraction), this is a contradiction. Therefore, our assumption that Gdoes not

contain a cycle of length at least 4 is false. Thus, Gmust contain a cycle of

length at least 4.

Question 19

Question

Let Gbe a simple graph with 10 vertices, each of degree 6. Prove that there

exist two vertices in Gwith a common neighbor.

Solution

Let us assume that there are no two vertices in Gwith a common neighbor. We

will arrive at a contradiction using the Pigeonhole Principle.

Step 1: Calculate the total number of edges in G. Each vertex in Ghas

degree 6, which means that each vertex is incident with 6 edges. Therefore, the

total number of edges in Gis given by:

2×total degree = 1

2×10 ×6 = 30

Step 2: Count the number of pairs of vertices in G. Since Ghas 10 vertices,

the number of ways to choose 2 vertices from 10 is 10

2= 45.

Step 3: Assign the pairs of vertices to the 30 edges. Given that there are 30

edges in G, each pair of vertices can be thought of as a ”pigeonhole” and each

edge can be thought of as a ”pigeon.” By our assumption, each pair of vertices

must be assigned a unique edge and since there are 45 pairs of vertices and only

30 edges, we have a contradiction.

Step 4: Conclude the proof. Thus, our assumption that there are no two

vertices with a common neighbor is false. Therefore, there must exist two ver-

tices in Gthat share a common neighbor.

Question 20

Question

Let Gbe a connected graph with 8 vertices and 15 edges. Prove that Gcontains

a cycle of length 4.

Solution

Step 1: Let’s first establish some properties of the graph G. Since Ghas 8

vertices and 15 edges, we can use the handshaking lemma to find the average

degree of a vertex in G. The handshaking lemma states that the sum of the

degrees of all vertices in a graph is equal to twice the number of edges in the

graph. Therefore, if nis the number of vertices and mis the number of edges

in a graph, the average degree of a vertex in the graph is 2m

n. In our case,

with n= 8 vertices and m= 15 edges, the average degree of a vertex in Gis

2·15

8=30

8= 3.75.

Step 2: Next, we observe that the average degree of a vertex in Gis greater

than 3. This implies that Gmust contain a vertex with degree at least 4. If

Gcontains a vertex vwith degree 4 or more, then there must exist a cycle of

length 4 containing the vertex v.

Step 3: Hence, we have shown that if Gis a connected graph with 8 vertices

and 15 edges, then Gcontains a cycle of length 4.

Question 21

Question

Let Gbe a connected graph with 10 vertices and 15 edges. Prove that Gmust

contain a cycle of length at least 4.

Solution

To prove that Gmust contain a cycle of length at least 4, we will make use of

the fact that a connected graph with nvertices and nedges contains at least

one cycle.

Step 1: By the Handshaking Lemma, the sum of the degrees of the vertices

in Gis twice the number of edges. Since the graph Ghas 10 vertices and 15

edges, the sum of the degrees of the vertices is 2 ×15 = 30.

Step 2: Suppose, for the sake of contradiction, that Gdoes not contain any

cycles of length at least 4. Then, all cycles in Gmust have length 3 or less.

Step 3: Consider the smallest cycle in G, which must be of length 3. Since

each vertex in the cycle has degree at least 2 (as otherwise we could extend the

cycle), there must be at least 6 edges in the smallest cycle.

Step 4: Removing these 6 edges from the graph, we are left with a subgraph

with 4 vertices and at most 9 edges. Since the smallest cycle had 6 edges, only

9 - 6 = 3 edges can connect the 4 vertices without creating any new cycles.

Step 5: However, in a connected graph with 4 vertices, there must be at

least 3 edges to ensure connectivity. Therefore, it is impossible to have a 4-

vertex, 9-edge subgraph without containing a cycle of length at least 4.

Step 6: This contradiction implies that our assumption - that Gdoes not

contain any cycles of length at least 4 - is incorrect. Thus, we have proven that

Gmust contain a cycle of length at least 4.

Question 22

Question

Let Gbe a simple undirected graph with 7 vertices and 10 edges. Prove that G

contains at least two vertices of the same degree.

Solution

To prove that the graph Gcontains at least two vertices of the same degree, we

will use the Pigeonhole Principle.

Step 1: Calculate the sum of degrees of all vertices Let v1, v2, . . . , v7

be the vertices of the graph G. Since each edge contributes to the degree of two

vertices, the sum of degrees of all vertices in a simple undirected graph is equal

to twice the number of edges.

i=1

degree(vi)=2×number of edges = 2 ×10 = 20

Step 2: Apply the Pigeonhole Principle Since there are 7 vertices in

the graph, each with degree ranging from 0 to 6 (inclusive), there are a total of 7

possible degrees. We need to distribute 20 total degrees among these 7 possible

degrees.

Using the Pigeonhole Principle, if we assign at most one degree value to each

vertex, then at least two vertices must have the same degree because 20 >7.

Therefore, the graph Gmust contain at least two vertices with the same

degree.

Question 23

Question

Let Gbe a connected graph with nvertices and medges where n≥2. Prove

that if Ghas no cycles, then m≤n−1.

Solution

To prove this result, we will use a proof by induction on the number of vertices

Step 1: Base Case (n= 2)For n= 2, a graph with two vertices can have

at most one edge connecting them. Since there are no cycles in the graph, this

graph must be a tree with one edge, so m≤n−1 holds.

Step 2: Inductive Hypothesis Assume that for any connected graph with

kvertices where 2 ≤k≤nand no cycles, the inequality m≤k−1 holds.

Step 3: Inductive Step Consider a connected graph Gwith nvertices

and no cycles. Let’s choose a leaf vertex in G, which is a vertex of degree 1.

Removing this leaf vertex will not disconnect the graph since Gis connected.

After removing the leaf vertex, we obtain a connected subgraph with n−1

vertices and m−1 edges. Since the subgraph has no cycles and n−1≥2,

we can apply the inductive hypothesis to conclude that m−1≤(n−1) −1.

Therefore, m≤n−1 for the graph G.

By the principle of mathematical induction, we have shown that if a con-

nected graph Gwith nvertices and no cycles must have m≤n−1.

Question 24

Question

Let Gbe a connected graph with 15 vertices and 21 edges. Prove that Gcannot

be a tree.

Solution

To show that Gcannot be a tree, we will use the fact that in a tree with n

vertices, there are always n−1 edges.

Step 1: Let’s assume for contradiction that Gis a tree with 15 vertices and

21 edges.

Since Gis a tree with 15 vertices, it must have 15 −1 = 14 edges according

to the definition of a tree. However, we are given that Ghas 21 edges, which is

a contradiction. Therefore, our assumption that Gis a tree must be incorrect.

Step 2: Conclude that Gcannot be a tree.

Since the assumption that Gis a tree leads to a contradiction, we can con-

clude that Gcannot be a tree. Thus, Gmust contain at least one cycle, making

it a non-tree connected graph.

Question 25

Question

Let Gbe a connected graph with 12 vertices and 20 edges. Prove that Gis not

a tree.

Solution

Step 1: Recall that a tree is a connected graph with no cycles.

Step 2: Since Ghas 12 vertices and 20 edges, we can apply the Handshaking

Lemma which states that the sum of the degrees of all vertices in a graph is

equal to twice the number of edges. Mathematically, Pv∈Vdeg(v)=2|E|,

where deg(v) denotes the degree of vertex v.

Step 3: Let’s calculate the sum of the degrees of all vertices in G. Since G

is connected, each vertex must have degree at least 1. Therefore, the sum of

degrees is at least 12.

Step 4: By the Handshaking Lemma, 2|E|=Pv∈Vdeg(v)≥12. Since

|E|= 20, we have 2 ×20 = 40 ≥12, which is true.

Step 5: However, in a tree with 12 vertices, there are exactly 11 edges, as a

tree with nvertices has n−1 edges. Since Ghas 20 edges (more than 11), it

cannot be a tree.

Step 6: Therefore, Gis not a tree as it contains cycles.

Question 26

Question

Let Gbe a connected graph with 10 vertices and 15 edges. Prove that Gcannot

be a tree.

Solution

Step 1: Recall that a tree is a connected graph with no cycles.

Step 2: Suppose for the sake of contradiction that Gis a tree with 10 vertices

and 15 edges.

Step 3: By the Handshaking Lemma, the sum of the degrees of all vertices

in a graph is twice the number of edges. Since Ghas 15 edges, the sum of the

degrees of all vertices in Gis 2 ×15 = 30.

Step 4: In a tree, every vertex except leaves has a degree of at least 2, and

leaves have a degree of 1.

Step 5: Since there are no cycles in G, there must be at least one leaf in G.

Let kbe the number of leaves in G.

Step 6: Let nbe the number of non-leaf vertices in G. As mentioned in Step

4, each non-leaf vertex has a degree of at least 2. Therefore, the sum of the

degrees of the non-leaf vertices is at least 2n.

Step 7: The sum of the degrees of all vertices can be expressed as 1 ·k+ 2 ·n.

From Step 3, we know this sum is equal to 30, so k+ 2n= 30.

Step 8: Since Ghas 10 vertices in total, we have k+n= 10.

Step 9: By solving the system of equations k+ 2n= 30 and k+n= 10, we

find k= 10 and n= 20.

Step 10: This implies that Ghas 20 non-leaf vertices and 10 leaf vertices.

Step 11: However, in a tree with at least two vertices, the number of edges is

always one less than the number of vertices. Therefore, a tree with 30 vertices

should have 30 −1 = 29 edges, which contradicts the given information that G

has 15 edges.

Step 12: Since the assumption that Gis a tree leads to a contradiction, we

conclude that Gcannot be a tree. Thus, the original statement is proven.

Question 27

Question

Let Gbe a graph with 10 vertices and 13 edges. Prove that Gcontains at least

one cycle.

Solution

To prove that the graph Gcontains at least one cycle, we will make use of the

fact that a graph contains a cycle if and only if it has more edges than vertices.

Step 1: Calculate the maximum number of edges a graph with 10 vertices

can have without containing a cycle. A tree with nvertices has n−1 edges. Thus,

the maximum number of edges a tree with 10 vertices can have is 10 −1 = 9.

Step 2: Determine the difference between the number of edges in Gand

the maximum number of edges in a tree with 10 vertices. Given that Ghas 13

edges and the maximum number of edges in a tree with 10 vertices is 9, the

difference is 13 −9 = 4.

Step 3: Conclude that Gmust contain at least one cycle. Since the dif-

ference is positive (4 >0), we can conclude that Gmust contain at least one

cycle. This is because the extra edges beyond the maximum for a tree indicate

the presence of a cycle.

Therefore, the graph Gwith 10 vertices and 13 edges must contain at least

one cycle.

Question 28

Question

Let Gbe a connected graph with nvertices and medges. Prove that if m<n−1,

then Gis not connected.

Solution

To prove that if m < n −1, then Gis not connected, we will use a proof by

contradiction.

Step 1: Assume Gis connected and m<n−1.

Since Gis connected, we know that there exists a path between any pair of

vertices in G. Also, by the Handshaking Lemma, the sum of the degrees of all

vertices is equal to twice the number of edges, i.e., Pv∈Vdeg(v)=2m.

Step 2: Express the sum of degrees in terms of the number of vertices n.

Since each vertex vin Gcontributes deg(v)≥1 to the sum of degrees, we

have Pv∈Vdeg(v)≥n.

Step 3: Find a contradiction by comparing the expressions for the sum of

degrees.

From Step 1 and Step 2, we have Pv∈Vdeg(v)≥n > 2m. However, this

contradicts the Handshaking Lemma which states that Pv∈Vdeg(v)=2m.

This contradiction arose from our initial assumption that Gis connected

and m<n−1. Therefore, if m<n−1, then Gis not connected.

Question 29

Question

Let Gbe a simple graph with 10 vertices and 25 edges. Prove that Gcontains

a cycle of length at least 4.

Solution

To prove that Gcontains a cycle of length at least 4, we will use the Pigeonhole

Principle.

Step 1: Calculate the average degree of vertices Let nbe the number

of vertices and mbe the number of edges in a simple graph G. It follows that

the average degree of the vertices in Gis 2m

n. Here, n= 10 and m= 25. The

average degree of the vertices in Gis 2×25

10 = 5.

Step 2: Apply the Pigeonhole Principle By the Pigeonhole Principle,

there exists at least one vertex in Gwith a degree of at least 5. Let’s call this

vertex v.

Step 3: Construct a cycle using vertex vSince vhas a degree of at

least 5, there are at least 5 edges incident to v. By the Pigeonhole Principle, at

least two of these edges must be incident to the same vertex (other than v), say

w, since there are only 9 other vertices to choose from. Suppose there are edges

from vto vertices w,x,y,z, and u, in that order. If there is an edge between

any pair of these vertices (other than vand w), then there exists a cycle of

length at least 4. Otherwise, if there are no such edges, we have a 5-vertex star

centered at vertex vwhich is a cycle of length 3, and we just need to connect

any two other vertices (other than vand w) to wto form a cycle of length at

least 4.

Therefore, we have shown that the graph Gcontains a cycle of length at

least 4.

Question 30

Question

Let Gbe a connected graph with nvertices and n−1 edges. Prove that Gis a

tree if and only if there are no cycles in G.

Solution

To prove that Gis a tree if and only if there are no cycles in G, we need to

prove both directions.

Step 1: If Gis a tree, then there are no cycles in G.Assume Gis a tree

with nvertices and n−1 edges. A tree is acyclic by definition, meaning it

contains no cycles. Thus, if Gis a tree, then there are no cycles in G.

Step 2: If there are no cycles in G, then Gis a tree. Suppose there are no

cycles in G. We want to show that Gis a tree. Since Gis connected with n

vertices and n−1 edges, we know that Gis acyclic (since a cycle would require

at least nedges).

Now, we need to prove that Gis connected and acyclic, which will make G

a tree.



Connected: Since Gis connected and acyclic, there must be a unique path

between every pair of vertices. If there were more than one path between

any pair of vertices, a cycle would form. Thus, Gis connected.



Acyclic: We already know that Gis acyclic from the assumption.

Therefore, since Gis connected and acyclic, Gis a tree.

Thus, we have shown both directions: if Gis a tree, then there are no cycles

in G, and if there are no cycles in G, then Gis a tree. Hence, Gis a tree if and

only if there are no cycles in G.

Question 31

Question

Let Gbe a simple graph with 12 vertices and 32 edges. Prove that Gmust

contain a cycle of length at least 4.

Solution

To prove that Gmust contain a cycle of length at least 4, we will use the

Pigeonhole Principle.

Step 1: Determine the maximum number of edges in a tree with

12 vertices

A tree with nvertices has n−1 edges. Therefore, the maximum number of

edges in a tree with 12 vertices is 12 −1 = 11.

Step 2: Calculate the difference in edges between Gand a tree

Since Ghas 32 edges and the maximum number of edges in a tree with 12

vertices is 11, the difference in edges between Gand the tree is 32 −11 = 21.

Step 3: Apply the Pigeonhole Principle

Consider the 12 vertices in G. Each vertex can be connected to at most 11

other vertices (since a vertex cannot be adjacent to itself). Therefore, the total

number of possible edges between the 12 vertices is 12 ·11 = 132.

Since Ghas 32 edges, there are 132 −32 = 100 unused edges in G. These

unused edges must form cycles in G.

Step 4: Prove the existence of a cycle of length at least 4

Assume for the sake of contradiction that all cycles in Ghave length less

than 4. Since a cycle of length 3 uses 3 edges, there can be at most 32

3= 10

cycles of length 3.

The total number of cycles of length 1 and 2 is at most 22, as a cycle of

length 1 uses 1 edge and a cycle of length 2 uses 2 edges.

Therefore, the total number of cycles with length less than 4 is at most

10 + 22 = 32, which is less than the 100 unused edges that need to form cycles.

This is a contradiction.

Hence, there must exist a cycle in Gwith length at least 4.

Question 32

Question

Let Gbe a connected graph with 12 vertices such that every vertex has degree

at least 4. Prove that Gcontains a cycle of length at least 5.

Solution

Let’s approach this problem by contradiction.

Step 1: Assume that Gis a connected graph with 12 vertices where every

vertex has degree at least 4, but Gcontains no cycle of length at least 5.

Step 2: We can consider the longest path in G. Let v1, v2, . . . , vkbe the

vertices of the longest path in G. Since Gcontains no cycle of length at least

5, the path v1, v2, . . . , vkmust be of length at most 4.

Step 3: Since every vertex in Ghas degree at least 4, each vi(1 ≤i≤k)

has at least 3 neighbors among v1, v2, . . . , vi−1, vi+1, . . . , vk.

Step 4: Consider the possible neighbors of v1. Since v1has degree at least

4, v1must have at least 3 neighbors among v2, v3, v4. This creates a cycle of

length 3, contradicting our assumption that there are no cycles of length at least

Step 5: Therefore, our assumption that Gcontains no cycle of length at

least 5 must be false. Hence, Gcontains a cycle of length at least 5.

Question 33

Question

Let Gbe a connected graph with 6 vertices and 10 edges. If Ghas a Hamiltonian

cycle, what is the minimum number of edges that must be removed from Gto

disconnect it?

Solution

To find the minimum number of edges that must be removed from Gto discon-

nect it, we first need to consider the minimum degree of a vertex in G.

Step 1: Calculate the minimum degree of a vertex in GBy the

Handshaking Lemma, the sum of the degrees of all vertices in a graph is equal

to twice the number of edges. Since Ghas 6 vertices and 10 edges, the sum of

the degrees of all vertices is 2 ×10 = 20. Since Gis connected, the minimum

degree of a vertex in Gis at least ⌈20

6⌉= 4.

Step 2: Consider the Hamiltonian cycle in GSince Ghas a Hamilto-

nian cycle, every vertex in Ghas degree at least 2. In a Hamiltonian cycle, each

vertex has degree exactly 2 except for the starting and ending vertices which

have degree 1. Therefore, the minimum degree of a vertex in Gis precisely 2.

Step 3: Identify the vertex to be removed to disconnect GTo

disconnect G, we must remove at least one vertex. Since the minimum degree

of a vertex in Gis 2, removing any vertex with degree 2 will disconnect G.

Step 4: Determine the minimum number of edges to be removed

Removing a vertex of degree 2 requires removing 2 edges. Thus, the minimum

number of edges that must be removed from Gto disconnect it is 2.

Question 34

Question

Let Gbe a connected graph with 10 vertices and 16 edges. Prove that Gcontains

a subgraph that is a tree with at least 6 leaves.

Solution

To prove that Gcontains a subgraph that is a tree with at least 6 leaves, we

will use the following facts: 1. In any tree, the number of leaves is always one

more than the number of vertices with degree greater than 1. 2. A connected

graph with nvertices has a tree as a subgraph with n−1 edges.

Step 1: Find the number of vertices with degree at least 2. Let

videnote the number of vertices with degree i. Since Gis a connected graph

with 10 vertices and 16 edges, the Handshaking Lemma states that the sum

of the degrees of the vertices is twice the number of edges. Mathematically,

i=1 vi= 2|E|. This means v0+v1+. . . +vn= 2 ·16 = 32. Since Gis

connected, v1≥1.

Step 2: Prove the existence of a tree subgraph with at least 6

leaves. Assume for contradiction that every subgraph of Gwith kvertices has

less than k−1 leaves. Then, every subgraph with 10 vertices (i.e., Gitself)

would have at most 9 leaves. Using the fact that the number of leaves is one

more than the number of vertices with degree greater than 1 in a tree, we see

that in this case, there would be at most 8 vertices with degree at least 2.

Question 2

Question

Let Gbe a simple undirected graph with 12 vertices and 22 edges. Prove that

Gmust contain a cycle of length 4 or less.

Solution

To solve this problem, we will use the Pigeonhole Principle.

Step 1: Determine the maximum number of edges in a graph with

no cycles of length 4 or less. Let Gbe a graph with no cycles of length 4

or less. The smallest possible cycle is a triangle (i.e., a cycle of length 3). In a

triangle, each vertex is connected to the other two vertices. Thus, the maximum

number of edges in Gis achieved when Gis a triangle-free graph. Given that G

has 12 vertices, a triangle-free graph will have at most ⌊n

2⌋edges, where nis the

number of vertices. Therefore, the maximum number of edges in a triangle-free

graph with 12 vertices is ⌊12

2⌋= 6.

Step 2: Use the Pigeonhole Principle. If Ghas more than 6 edges,

then by the Pigeonhole Principle, there must be at least two edges incident to

the same vertex which creates a cycle of length 2. If Ghas more than 11 edges

(but less than 18 edges), then there must be at least one cycle of length 3. If

Ghas more than 18 edges (but less than 24 edges), then there must be at least

one cycle of length 4. Since Ghas 22 edges, it must contain at least one cycle

of length 4 or less.

Therefore, we have proved that in any simple undirected graph with 12

vertices and 22 edges, there must be a cycle of length 4 or less.

Question 3

Question

Let Gbe a connected graph with 10 vertices and 15 edges. If each vertex of G

has degree at least 3, what can you say about the graph G?

Solution

Step 1: We know that the sum of the degrees of all vertices of a graph is equal

to twice the number of edges. Therefore, for our graph Gwith 10 vertices and

15 edges, the sum of the degrees of all vertices is 2 ×15 = 30.

Step 2: Since each vertex has degree at least 3, the sum of the degrees of

all vertices in Gis at least 10 ×3 = 30. Therefore, the sum of the degrees is

exactly 30.

Step 3: This implies that each vertex in Gmust have degree exactly 3. If

any vertex had a degree greater than 3, the sum of the degrees would exceed

30.

Step 4: Therefore, the graph Gmust be a regular graph where each ver-

tex has degree 3. Additionally, since Gis connected, Gmust be a 3-regular

connected graph with 10 vertices and 15 edges.

Step 5: An example of such a graph is a 10-vertex cycle, where each vertex

is connected to the two vertices adjacent to it on the cycle.

Question 4

Question

Let Gbe a connected graph with 16 vertices and 32 edges. Prove that Gcontains

a cycle of length at least 4.

Solution

Step 1: Use the fact that a connected graph with nvertices and n−1 edges is

a tree.

Let Gbe a connected graph with 16 vertices and 32 edges. Since Gis

connected, it must contain a spanning tree.

Step 2: Recall that a tree with nvertices has n−1 edges.

Since Ghas 16 vertices and 32 edges, it cannot be a tree because a tree with

16 vertices would have 15 edges. Therefore, Gmust contain at least one cycle.

Step 3: Assume for contradiction that all cycles in Gare of length 3 or less.

Now, let’s assume for contradiction that all cycles in Gare of length 3 or

less.

Step 4: Use the fact that the sum of the lengths of all cycles in a graph is

equal to twice the number of vertices minus the number of edges.

The sum of the lengths of all cycles in any graph is equal to twice the number

of vertices minus the number of edges.

For our graph G, with 16 vertices and 32 edges, the left side of the equation

would be 0 (since we assumed all cycles are of length 3 or less). However, the

right side would be 16.

This is a contradiction, so our assumption that all cycles are of length 3 or

less must be false.

Step 5: Conclude that Gmust contain a cycle of length at least 4.

Thus, Gmust contain a cycle of length at least 4, as required.

Question 5

Question

Let Gbe a connected graph with 10 vertices and 17 edges. If Ghas no cycles of

length less than 4, then what is the maximum possible number of edges in G?

Solution

To maximize the number of edges in a graph with no cycles of length less than

4, we will build a graph that is a tree, which is a connected acyclic graph.

Step 1: Recall that in a tree with nvertices, there are n−1 edges. Since

Ghas 10 vertices, we can start by building a tree with 10 vertices and 9 edges.

Step 2: Now, we need to add more edges to the tree to reach a total of 17

edges. To maximize the number of edges without creating cycles of length less

than 4, we will add edges to form paths of length 3.

Step 3: We can add 8 more edges to the tree to form paths of length 3.

This brings the total number of edges to 9 + 8 = 17.

Step 4: Therefore, the maximum possible number of edges in Gis 17 .

Question 6

Question

Let Gbe a connected graph with nvertices and medges such that every vertex

has degree at least n

2. Prove that Gis Hamiltonian, i.e., it contains a Hamilto-

nian cycle.

Solution

To prove that Gis Hamiltonian, we will use the Dirac’s theorem.

Step 1: State Dirac’s Theorem

Dirac’s Theorem: Let Gbe a graph with n≥3 vertices. If every vertex in G

has degree at least n

2, then Gis Hamiltonian.

Step 2: Apply Dirac’s Theorem to the given graph

Since every vertex in Ghas degree at least n

2, we can apply Dirac’s Theorem to

conclude that Gis Hamiltonian.

Step 3: Conclusion

Therefore, the connected graph Gwith nvertices and medges, where every

vertex has degree at least n

2, is Hamiltonian.

Question 7

Question

Let Gbe a connected graph with 10 vertices and 15 edges. Prove that Gcontains

a cycle of length at most 4.

Solution

To prove that Gcontains a cycle of length at most 4, we will make use of the

Pigeonhole Principle.

Step 1: Counting edges for a path Consider a path Pof maximum

length in G. Since Ghas 10 vertices and 15 edges, the maximum length of P

is 9 (if Phas 10 vertices, then it would contain 9 edges, which is the maximum

possible). Let v1and v9be the endpoints of P.

Step 2: Neighborhood of v1and v9Since Gis connected, v1and v9

must have neighbors on Pas well as neighbors outside P. Let the neighbors of

v1not on Pbe xand y, and the neighbors of v9not on Pbe zand w.

Step 3: Using the Pigeonhole Principle Consider the paths v1−x−z−v9

and v1−y−w−v9. These paths form two internally vertex-disjoint paths joining

v1and v9, but they share the vertices v1and v9. By the Pigeonhole Principle,

one of the paths must contain a cycle of length at most 4.

Therefore, we have shown that Gcontains a cycle of length at most 4.

Question 8

Question

Let Gbe a connected graph with 12 vertices such that each vertex has degree

4 or 5. Prove that Gcontains a cycle of length 4.

Solution

To prove that Gcontains a cycle of length 4, we will use the Pigeonhole Principle.

Step 1: Count the total number of edges in the graph Let Vdenote

the set of vertices and Edenote the set of edges in graph G. Since each vertex has

degree 4 or 5, the total number of edges can be calculated using the Handshaking

Lemma:

2|E|=X

v∈V

deg(v)

where deg(v) is the degree of vertex v. Since each vertex has degree 4 or 5,

the total number of edges is between 4|V|and 5|V|. Since |V|= 12, the total

number of edges lies between 48 and 60.

Step 2: Consider the possible cases Assume that there are no cycles

of length 4 in G. This means that any cycle in Gmust have length at least 5.

Let nbe the number of edges in the longest cycle in G. Since the sum of the

degrees of the vertices is even, the total number of edges should be even. Since

each edge is shared by exactly two vertices, the length of the longest cycle must

be even. Therefore, n≥6.

Step 3: Apply the Pigeonhole Principle Since Gis connected with 12

vertices and each vertex has degree 4 or 5, we can count the total number of

edges using the Handshaking Lemma as shown in Step 1. As the total number

of edges lies between 48 and 60, and the longest cycle length is at least 6, we

can create at most 2(60)

6= 20 cycles of length 6 in G.

Step 4: Arrive at a contradiction Each cycle of length 6 uses 6 distinct

vertices. Since there are only 12 vertices in G, at least 12 vertices are repeated in

the 20 cycles of length 6. By the Pigeonhole Principle, there must be a repeated

vertex among the 20 cycles, which implies the existence of a cycle of length 4,

contradicting our assumption.

Therefore, there must exist a cycle of length 4 in the graph G.

Question 9

Question

Let Gbe a simple graph with 8 vertices and 14 edges. Prove that Gcontains a

subgraph with at least 5 vertices of degree 5 or higher.

Solution

Step 1: Let’s assume for the sake of contradiction that Gdoes not contain a

subgraph with at least 5 vertices of degree 5 or higher. This implies that the

maximum degree of any vertex in Gis at most 4.

Step 2: Since Gis a simple graph with 8 vertices, the sum of the degrees of all

vertices is equal to twice the number of edges. Thus, Pv∈Vdeg(v) = 2·14 = 28.

Step 3: If the maximum degree is at most 4, then the sum of the degrees

of all vertices is at most 8 ·4 = 32. However, this contradicts the fact that

Pv∈Vdeg(v) = 28.

Step 4: Therefore, our assumption that Gdoes not contain a subgraph with

at least 5 vertices of degree 5 or higher must be false. Hence, Gmust contain a

subgraph with at least 5 vertices of degree 5 or higher.

Question 10

Question

Let Gbe a simple graph with 9 vertices and 15 edges. Prove that Gcontains a

cycle of length at least 4.

Solution

Step 1: Let’s assume that Gdoes not contain any cycle of length at least 4.

Step 2: We know that a cycle of length nhas nedges. Therefore, if Gdoes

not contain any cycle of length at least 4, then the longest cycle in Ghas length

Step 3: Since the longest cycle in Ghas length 3, the graph can be decom-

posed into disjoint cycles and paths. If we count the number of edges in these

cycles and paths, we get:

Number of edges = 3c+p

where cis the number of cycles and pis the number of paths.

Step 4: Since the graph Ghas 9 vertices and 15 edges, we have:

Number of vertices −Number of edges + Number of components = 2

Substitute the given values:

9−15 + c+p= 2

c+p= 8

Step 5: If the longest cycle in Ghas length 3, then each cycle contributes

3 edges. Therefore, the total number of edges contributed by the cycles is a

multiple of 3, which means 3cis a multiple of 3.

Step 6: Since c+p= 8, ccan be at most 5 (as pshould be non-negative).

This implies that the remaining 3 edges in 3c+pwill be in the paths.

Step 7: However, placing 3 edges in paths would create a path with more than

two edges, thus creating a cycle of length 4, which contradicts our assumption.

Step 8: Therefore, our assumption that Gdoes not contain any cycle of

length at least 4 is incorrect. Hence, Gmust contain a cycle of length at least

Question 11

Question

Let Gbe a connected graph with nvertices and medges. Prove that if m<n−1,

then Gis disconnected.

Solution

To prove that if m<n−1, then Gis disconnected, we will use proof by

contradiction.

Step 1: Assume that Gis connected.

If Gis connected, then it must contain at least n−1 edges by definition. This

is because a connected graph with nvertices has at least n−1 edges (consider

a tree as an example).

Step 2: Contradiction.

Since m<n−1 has been given, this contradicts our assumption that Gis

connected because a connected graph with nvertices must have at least n−1

edges. Therefore, our assumption that Gis connected is false.

Step 3: Conclusion.

Since our assumption that Gis connected leads to a contradiction, we con-

clude that if m<n−1, then Gis disconnected.

Question 12

Question

Let Gbe a connected graph with 10 vertices and 22 edges. Prove that Gcontains

a cycle of length at least 4.

Solution

To prove that Gcontains a cycle of length at least 4, we will make use of the

fact that Gis a connected graph with 10 vertices and 22 edges.

Step 1: Use the Handshaking Lemma to find the average degree of vertices

in G. According to the Handshaking Lemma, the sum of the degrees of all

vertices in a graph is equal to twice the number of edges. Since Ghas 10

vertices and 22 edges, the sum of the degrees of all vertices is 2 ×22 = 44.

Therefore, the average degree of vertices in Gis 44

10 = 4.4.

Step 2: Use the Pigeonhole Principle to find a vertex with degree at least 5.

If the average degree of vertices is 4.4, by the Pigeonhole Principle, there must

exist a vertex in Gwith degree at least 5. Let vbe a vertex in Gwith degree

at least 5.

Step 3: Follow the path to find a cycle. Start from vertex vand follow its

edges. Since vhas degree at least 5, there must be at least 5 edges incident to v.

Follow a path of distinct vertices until you encounter a vertex that has already

been visited. This forms a cycle.

Step 4: Analyze the cycle found. The cycle found in Step 3 has length at

least 4 because it starts and ends at the same vertex v, and there are at least 4

distinct vertices in the path.

Therefore, we have proven that the connected graph Gwith 10 vertices and

22 edges contains a cycle of length at least 4.

Question 13

Question

Let Gbe a simple graph with 12 vertices and 28 edges. Prove that Gcontains

a cycle of length at least 4.

Solution

To prove that Gcontains a cycle of length at least 4, we will use the Pigeonhole

Principle.

Step 1: Find the number of edges in the complete graph K12.A

complete graph Knhas n(n−1)

2edges. For n= 12, the complete graph K12 has

12×11

2= 66 edges.

Step 2: Consider the complement of G, denoted by G.Since Ghas

28 edges, the complement Ghas 66 −28 = 38 edges.

Step 3: Apply the Pigeonhole Principle to the vertices of G.Each

vertex in Gis adjacent to 11 other vertices, which means each vertex in Gis

adjacent to 11 vertices in Gor G. By the Pigeonhole Principle, there must be

a vertex vin Gwith at least 7 edges connecting it to vertices in either Gor G.

Step 4: Consider the neighbors of vertex v.Since vertex vhas at least

7 edges connecting it to other vertices in Gor G, at least 7 of its neighbors are

in Gor G.

Step 5: Construct a cycle of length at least 4. Let w1, w2, . . . , w7be

the neighbors of vertex vin Gor G. If there exists an edge between any two of

wi’s, we would have found a cycle of length at least 4. Otherwise, since there are

7 vertices and each can only connect to 4 others or fewer (due to the condition

of not forming an edge), there must be two vertices that are not connected,

forming a length-2 path. Adding the edge connecting these two vertices to v

gives a cycle of length at least 4.

Question 14

Question

Let Gbe a connected graph with nvertices and medges, where m>n. Prove

that Ghas a cycle.

Solution

To prove that Ghas a cycle, we will use the fact that in a connected graph with

nvertices and medges, the graph is a tree if and only if m=n−1.

Step 1: Assume for the sake of contradiction that Gis a tree.

If Gis a tree, then m=n−1. However, given that m>n, this results in a

contradiction.

Step 2: Therefore, Gis not a tree.

Since Gis not a tree, it must contain at least one cycle.

Step 3: Conclusion

Therefore, the graph Gmust contain a cycle.

Question 15

Question

Let Gbe a connected graph with 10 vertices and 18 edges. Prove that Gcontains

a cycle of length at least 4.

Solution

Suppose for the sake of contradiction that Gdoes not contain a cycle of length

at least 4. Then all cycles in Gmust be of length 3 or less.

Step 1: Counting edges in a simple graph

In a simple graph with nvertices, the maximum number of edges is given by

n

2=n(n−1)

2. If Ghas 10 vertices and 18 edges, this implies that Gis not a

simple graph.

Step 2: Counting sum of degrees in a graph

By the Handshaking Lemma, the sum of the degrees of the vertices in a graph

is equal to twice the number of edges. That is, Pv∈Vdeg(v) = 2|E|. In our

case, this becomes Pv∈Vdeg(v)=2·18 = 36.

Step 3: Relationship between cycle length and vertex degrees

Assume that all cycles in Gare triangles. Since a triangle has 3 edges and 3

vertices, each vertex in a triangle must have degree at least 2. Thus, in a graph

containing only triangles, the sum of the degrees must be at least 3n(where n

is the number of vertices). Since the sum of the degrees in Gis 36, n≤12.

Step 4: Conclusion

We have shown that Gmust have at most 12 vertices in order for it to consist

only of cycles of length 3. However, since Ghas 10 vertices, there must be a

cycle in Gwith a length greater than 3. This contradicts our initial assumption,

so Gmust contain a cycle of length at least 4.

Question 16

Question

Let Gbe a connected graph with 12 vertices and 17 edges. Prove that Gcontains

at least one cycle.

Solution

Step 1: Let’s first establish a useful theorem.

Theorem: If Gis a connected graph with nvertices and medges, where n>m,

then Gcontains at least one cycle.

Step 2: Given that Gis a connected graph with 12 vertices and 17 edges,

we have n= 12 and m= 17.

Step 3: Since n>m, by the theorem stated in Step 1, we can conclude that

Gcontains at least one cycle.

Step 4: Therefore, the graph Gmust contain at least one cycle, as required.

Question 17

Question

Let Gbe a connected graph with 10 vertices and 14 edges. If Gcontains 3

bridges, what is the minimum number of edges that can be removed from Gto

obtain a connected graph?

Solution

Let nbe the number of vertices in the graph Gand let mbe the number of

edges.

Step 1: Finding the minimum number of edges in a connected graph with

nvertices. A connected graph with nvertices has at least n−1 edges. This is

known as the Handshaking Lemma.

Therefore, the minimum number of edges in a connected graph with 10

vertices is 10 −1 = 9.

Step 2: Calculating the minimum number of edges that can be removed

from G. Since Ghas 14 edges and 3 bridges, there are 14 −3 = 11 edges that

are not bridges.

To obtain a connected graph, we need at least 9 edges. Since there are 11

non-bridge edges already in G, we can remove 11−9 = 2 non-bridge edges while

keeping all bridges intact.

Thus, the minimum number of edges that can be removed from Gto obtain

a connected graph is 2 .

Question 18

Question

Let Gbe a simple graph with 7 vertices such that each vertex has degree at

least 4. Prove that Gcontains a cycle of length at least 4.

Solution

To prove that Gcontains a cycle of length at least 4, we will use the Pigeonhole

Principle.

Step 1: Counting edges in GSince each vertex in Ghas degree at least

4, the total number of edges in Gis at least 4×7

2= 14 (using Handshaking

Lemma).

Step 2: Assume the contrary Suppose Gdoes not contain a cycle of

length at least 4. This implies that any cycle in Ghas length 3 or less.

Step 3: Counting edges in cycles Consider any cycle in Gof length 3.

Since a cycle of length 3 requires 3 edges, and any pair of vertices in a cycle of

length 3 are connected by an edge, the number of edges in all cycles of length 3

is 3 ×number of cycles of length 3.

Step 4: Applying the Pigeonhole Principle Let xbe the number of

cycles of length 3 in G. From Step 3, we know that the total number of edges

in all cycles of length 3 is 3x. Since the total number of edges in Gis at least

14 (from Step 1), we have 3x≤14.

Step 5: Conclusion From Step 4, we have 3x≤14, which implies x≤

3. However, since xmust be a whole number (number of cycles cannot be a

fraction), this is a contradiction. Therefore, our assumption that Gdoes not

contain a cycle of length at least 4 is false. Thus, Gmust contain a cycle of

length at least 4.

Question 19

Question

Let Gbe a simple graph with 10 vertices, each of degree 6. Prove that there

exist two vertices in Gwith a common neighbor.

Solution

Let us assume that there are no two vertices in Gwith a common neighbor. We

will arrive at a contradiction using the Pigeonhole Principle.

Step 1: Calculate the total number of edges in G. Each vertex in Ghas

degree 6, which means that each vertex is incident with 6 edges. Therefore, the

total number of edges in Gis given by:

2×total degree = 1

2×10 ×6 = 30

Step 2: Count the number of pairs of vertices in G. Since Ghas 10 vertices,

the number of ways to choose 2 vertices from 10 is 10

2= 45.

Step 3: Assign the pairs of vertices to the 30 edges. Given that there are 30

edges in G, each pair of vertices can be thought of as a ”pigeonhole” and each

edge can be thought of as a ”pigeon.” By our assumption, each pair of vertices

must be assigned a unique edge and since there are 45 pairs of vertices and only

30 edges, we have a contradiction.

Step 4: Conclude the proof. Thus, our assumption that there are no two

vertices with a common neighbor is false. Therefore, there must exist two ver-

tices in Gthat share a common neighbor.

Question 20

Question

Let Gbe a connected graph with 8 vertices and 15 edges. Prove that Gcontains

a cycle of length 4.

Solution

Step 1: Let’s first establish some properties of the graph G. Since Ghas 8

vertices and 15 edges, we can use the handshaking lemma to find the average

degree of a vertex in G. The handshaking lemma states that the sum of the

degrees of all vertices in a graph is equal to twice the number of edges in the

graph. Therefore, if nis the number of vertices and mis the number of edges