MATH 350 - DISCRETE MATHEMATICS Graph Theory Question Bank Set 3

MATH 350 - DISCRETE

MATHEMATICS - Graph Theory

Question Bank - Set 3

Liberty University

Question 1

Question

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

tree.

Solution

Step 1: Recall that a tree is an acyclic, connected graph. We need to show that

Gis acyclic and connected.

Step 2: Since Ghas nvertices and n−1 edges, Gis a connected graph with

the least possible number of edges for a connected graph.

Step 3: Assume, for the sake of contradiction, that Gcontains a cycle.

Removing any edge from the cycle would disconnect the graph, contradicting

the fact that Gis connected.

Step 4: Therefore, Gcannot contain a cycle, so Gis acyclic.

Step 5: Since Gis both connected and acyclic, we conclude that Gis a tree.

Question 2

Question

Let Gbe a simple graph with 10 vertices and 20 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 graph with-

out a cycle of length at least 4 Let’s consider the case where Ghas no cycle

of length at least 4. The maximum number of edges in a tree on 10 vertices is 9

(since a tree with nvertices has n−1 edges). Thus, if Ghas no cycle of length

at least 4, it can have at most 9 edges.

Step 2: Calculate the excess number of edges in GSince Ghas 20

edges, which is more than the maximum edges in a tree on 10 vertices, there

must be at least 20 −9 = 11 excess edges in G.

Step 3: Utilize the Pigeonhole Principle Consider the 10 vertices of G

as pigeons. Each edge in Gconnects two vertices, so each edge is a hole. Since

there are 11 excess edges and only 10 vertices, by the Pigeonhole Principle, there

must be at least one vertex that is incident to two edges.

Step 4: Finding the cycle Since the vertex is incident to two edges, there

must be a cycle of length at least 4 in G. This cycle is formed by the two edges

incident to the chosen vertex, along with the vertices connecting them.

Therefore, we have shown that a simple graph Gwith 10 vertices and 20

edges must contain a cycle of length at least 4.

Question 3

Question

Let Gbe a connected graph with nvertices and n+ 1 edges. Prove that G

contains a cycle.

Solution

To prove that Gcontains a cycle, we can use the fact that a connected graph

with nvertices and n−1 edges is a tree.

Step 1: First, we will prove that Gcontains a cycle by contradiction. Sup-

pose Gdoes not contain a cycle.

Step 2: Since Gis connected and acyclic, it must be a tree. Therefore, G

has n−1 edges.

Step 3: However, by the given information, Gactually has n+ 1 edges,

which contradicts the assumption that Gis a tree.

Step 4: Since our assumption led to a contradiction, we conclude that G

must contain a cycle.

Question 4

Question

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

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

Solution

To prove this statement, we will use the Pigeonhole Principle. Let’s assume for

the sake of contradiction that Gdoes not contain a cycle of length at least 4.

Step 1: Counting edges Since Ghas 10 vertices and every vertex has

degree at least 3, the total number of edges in Gis at least 3·10

2= 15 (since each

edge contributes to the degree of 2 vertices).

Step 2: Counting faces Let’s denote the number of vertices, edges, and

faces in Gby V,E, and F, respectively. By Euler’s formula, we have V−E+F=

2 for any connected planar graph. Since Gis connected and not a tree, we have

E≥V+ 1 (since a tree with Vvertices has V−1 edges). Substituting E≥15

into Euler’s formula gives F≤7.

Step 3: Applying the Pigeonhole Principle Consider each face in the

planar representation of G. Since every face is bounded by a cycle, every face

has at least 3 edges. The average number of edges per face is 2E

F≥2·15

7>4. By

the Pigeonhole Principle, there must exist a face bounded by a cycle of length

at least 4, which contradicts our assumption.

Therefore, our assumption that Gdoes not contain a cycle of length at least

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

Question 5

Question

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

a cycle of length at least 4.

Solution

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

Principle.

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

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

number of edges in a tree with 10 vertices is 10 −1 = 9.

Step 2: Find the minimum number of edges needed to form a

graph with 10 vertices that is not a tree. Since Ghas 15 edges and the

maximum number of edges in a tree with 10 vertices is 9, we need at least

15 −9 = 6 more edges to form a graph that is not a tree.

Step 3: Apply the Pigeonhole Principle. In a graph with 10 vertices,

the minimum degree of a vertex in a graph is 2 (if Gis a tree, then the minimum

degree is 1). Since we need at least 6 more edges to form a graph that is not

a tree, there must be at least one vertex with degree greater than 2, meaning

there is a cycle in G.

Hence, Gcontains a cycle of length at least 4.

Question 6

Question

Let Gbe a connected graph with nvertices, each with degree at least n

2. Prove

that Gis Hamiltonian, i.e., it contains a Hamiltonian cycle.

Solution

Let’s prove the statement by contradiction:

Step 1: Assume that Gis not Hamiltonian.

Step 2: By Dirac’s Theorem, if Gis a graph with n≥3 vertices such that

each vertex has degree at least n

2, then Gis Hamiltonian. Since our assumption

contradicts Dirac’s Theorem, there must be a vertex vin Gwith degree less

than n

Step 3: Let vbe a vertex with degree less than n

2in G. Since Gis connected,

there must be a path from vto any other vertex in G. Let ube a vertex adjacent

to v.

Step 4: Since deg(v)<n

2, there are at least n

2+1 vertices in Gnot adjacent

to v. Since Gis connected and uis adjacent to v, there must be a vertex wnot

adjacent to vbut adjacent to u.

Step 5: Now consider the graph G′=G− {v, w}+{uw}, where we remove

vertices vand walong with their incident edges, and add the edge uw. Notice

that every vertex in G′still has degree at least n

Step 6: By repeating this process, we can construct a new graph with n−1

vertices, each with degree at least n−1

2. Continuing this process, we eventually

arrive at a subgraph G′′ with three vertices such that all vertices have degree

at least 1.

Step 7: Since G′′ has three vertices and each vertex has degree at least 1,

it forms a Hamiltonian cycle, which contradicts our assumption that Gis not

Hamiltonian.

Step 8: Therefore, our initial assumption that Gis not Hamiltonian is false,

and thus Gmust be Hamiltonian.

Question 7

Question

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

a pair of vertices with degree at least 3.

Solution

Let’s prove this by contradiction.

Step 1: Assume for the sake of contradiction that every pair of vertices in

Ghas degree at most 2.

Step 2: Since Ghas 10 vertices, each vertex can have a maximum degree of 9

(connecting to all other vertices except itself). But according to our assumption,

each vertex has degree at most 2. This means the maximum number of edges

in Gcan be 10 ×2 = 20.

Step 3: However, we are given that Ghas 20 edges. This implies that our

assumption is incorrect, and there must exist at least one pair of vertices in G

with degree greater than 2.

Step 4: Therefore, we have proved by contradiction that in any simple

graph with 10 vertices and 20 edges, there must be at least one pair of vertices

with degree at least 3.

Question 8

Question

Let Gbe a connected graph with nvertices and n+ 3 edges. Prove that G

contains at least one cycle.

Solution

To prove that Gcontains at least one cycle, we will use the fact that in a

connected graph with nvertices, n−1 edges are necessary and sufficient for the

graph to be a tree. Since Ghas n+ 3 edges, it must contain at least one cycle.

Step 1: Let’s assume by contradiction that Gis a connected graph with n

vertices and n+ 3 edges, but does not contain any cycles.

Since Gis acyclic, it must be a tree and hence has n−1 edges. However,

n−1< n + 3, which contradicts our assumption.

Therefore, our assumption that Gdoes not contain any cycles is false, and

Gmust contain at least one cycle.

Question 9

Question

Let Gbe a connected graph with 12 vertices and 15 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 more edges than vertices.

Step 1: Counting Edges Since Ghas 12 vertices and 15 edges, we know

that the average degree of the vertices is 2·15

12 =5

2. Therefore, by the Pigeonhole

Principle, there exists a vertex in Gwith degree at least 5.

Step 2: Finding a Cycle Consider a vertex vin Gwith degree at least

5. Since Gis connected, there must be at least 5 distinct neighbors of v. Let’s

denote these neighbors as v1, v2, v3, v4, v5.

Step 3: Creating a Cycle Now, consider the subgraph of Ginduced by

the vertices {v, v1, v2, v3, v4, v5}. Since vhas 5 neighbors among these vertices,

there must exist a cycle consisting of at least 4 vertices. Thus, Gcontains a

cycle of length at least 4.

Therefore, we have shown that any connected graph with 12 vertices and 15

edges must contain a cycle of length at least 4.

Question 10

Question

Let Gbe a connected graph with 10 vertices and 14 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 fact that

Gis a connected graph with 10 vertices and 14 edges.

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

10 vertices can have. A connected graph with nvertices has at least n−1 edges.

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

is 10 −1 = 9. Since Ghas 14 edges, which is greater than 9, it implies Gcan

have at most 10 + 8 = 18 edges (but we are given that Ghas 14 edges).

Step 2: Use the Pigeonhole Principle to find a cycle of length at least 4.

Consider the vertices of Gas the ”pigeons” and the edges as the ”pigeonholes”.

In this case, each vertex corresponds to an edge incident to it. Since there are

14 edges and 10 vertices, there must be at least one vertex with 3 or more edges

incident to it. Let’s suppose there is a vertex vwith at least 3 incident edges.

Step 3: Use the fact that vhas at least 3 incident edges to find a cycle of

length at least 4. Since vhas at least 3 incident edges, at least one edge must

connect two vertices different from v. Let’s call these vertices uand w. Now,

we have a path from uto vand an edge between vand w. By adding the edge

between wand u, we obtain a cycle of length at least 4 (u→v→w→u).

Therefore, the graph Gcontains a cycle of length at least 4.

Question 11

Question

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

a cycle of length 4.

Solution

Step 1: By the handshake theorem, the sum of the degrees of the vertices in G

is twice the number of edges. Since Gis connected, the degree of each vertex is

at least 1. Thus, the sum of the degrees is at least 8.

Step 2: Let d1, d2, . . . , d8be the degrees of the vertices in G, in non-decreasing

order. Then we have d1+d2+. . . +d8≥8.

Step 3: If d1≥4, then we are done, since a vertex of degree at least 4 implies

the existence of a cycle of length 4 in G. Hence, we can assume d1<4.

Step 4: If d2≥4, then we are done similarly as in Step 3. If not, remove

vertices of degree less than 4 along with their incident edges until reaching a

vertex of degree at least 4.

Step 5: Repeat this process until a vertex of degree at least 4 is found. Since

there are 8 vertices and removing a vertex decreases the sum of the degrees by

at most 1, this process can be repeated at most 4 times.

Step 6: After at most 4 iterations, we will have a vertex of degree at least

4. Hence, there exists a cycle of length 4 in the graph G.

Question 12

Question

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

a cycle of length at least 4.

Solution

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

Pigeonhole Principle.

Step 1: Determine the minimum number of edges needed for a

cycle. In a simple graph, a cycle of length nrequires at least nedges. Therefore,

a cycle of length 4 requires at least 4 edges.

Step 2: Calculate the maximum number of vertices in a cycle of

length 3. A cycle of length 3 has 3 vertices and 3 edges. If there are 3 vertices

in a cycle, there can be at most 3 edges.

Step 3: Consider the remaining edges after removing edges from

triangles. Since a cycle of length 3 can use at most 3 edges, any additional

edge connected to the 3 vertices forms a cycle of length at least 4. Assume

there are no cycles of length at least 4. Then, removing the 3 edges from each

triangle, we are left with at least 16 −3·3 = 7 edges.

Step 4: Applying the Pigeonhole Principle. If we have 10 vertices and

7 edges remaining, then at least one vertex must have degree at least 2 (by the

Pigeonhole Principle). This vertex, along with its two adjacent vertices, forms

a cycle of length at least 4.

Therefore, the graph Gmust contain a cycle of length at least 4.

Question 13

Question

Let Gbe a connected graph with 14 vertices and 24 edges. Prove that Gcontains

a cycle of length at most 6.

Solution

To prove that Gcontains a cycle of length at most 6, we will use the Pigeonhole

Principle.

Step 1: Recall the definition of a cycle in a graph. A cycle in a graph is a

path of distinct vertices that starts and ends at the same vertex.

Step 2: Consider the total number of vertices in G. Since Ghas 14 vertices,

and is connected, the minimum number of edges needed to connect all vertices

is 13. Therefore, the graph has more than the minimum number of edges.

Step 3: Apply the Pigeonhole Principle. Since Ghas 24 edges and 13 edges

are needed for a tree to have 14 vertices, the remaining 11 edges must create

cycles in the graph. We will assign the edges to ”pigeonholes” based on the

number of edges incident upon each vertex.

Step 4: Choose a vertex with at least 3 incident edges. By the Pigeonhole

Principle, there must exist a vertex with at least 3 incident edges. Let’s call

this vertex v.

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

incident edges, there are at least 3 neighbors of v. We will consider the possible

connections between these neighbors to create a cycle.

Step 6: Analyze the possible cycles involving vertex v. Consider the cycles

that involve vertex v: - If there is a cycle of length 3 involving v, we are done.

- If there is no cycle of length 3 but there is a cycle of length 4 involving v, we

are done. - If there is a cycle of length 5 involving v, we can shorten it to a

cycle of length 3 by removing an edge. - If there is no cycle of length 3, 4, or 5

involving v, there must be a cycle of length 6 involving v.

Therefore, we have shown that Gmust contain a cycle of length at most 6.

Question 14

Question

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

a cycle of length at least 4.

Solution

Let’s prove this statement by contradiction:

Step 1: Assume for the sake of contradiction that Gdoes not contain a

cycle of length at least 4. Then all cycles in Gare of length 3 or less.

Step 2: Recall that in a simple connected graph, the number of edges eand

vertices vare related by the formula e≤v−1. Since Gis connected with 10

vertices and 15 edges, then 15 ≤10 −1 which is a contradiction.

Step 3: Therefore, our assumption in Step 1 is incorrect. Thus, Gmust

contain a cycle of length at least 4.

Therefore, we have proved that a connected graph with 10 vertices and 15

edges must contain a cycle of length at least 4.

Question 15

Question

Let Gbe a connected graph with 7 vertices and 11 edges. Prove that Gis not

a tree.

Solution

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

Step 2: Let nbe the number of vertices in a graph G, and let mbe the

number of edges in G.

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

in a graph is twice the number of edges. That is, Pv∈Vdeg(v)=2m.

Step 4: Since Gis connected, the minimum number of edges in a connected

graph with nvertices is n−1. Therefore, m≥n−1.

Step 5: For a tree with nvertices, there are n−1 edges.

Step 6: Since Ghas 7 vertices and 11 edges, it violates the condition for

being a tree, which requires n−1 edges for nvertices.

Step 7: Therefore, Gis not a tree.

Thus, we have proved that a connected graph with 7 vertices and 11 edges

is not a tree.

Question 16

Question

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

contain a cycle of length 4 or less.

Solution

Step 1: Assume for the sake of contradiction that Gdoes not contain a cycle of

length 4 or less.

Step 2: Consider the maximum number of edges a simple graph with 10

vertices can have without containing a cycle of length 4 or less. In such a

graph, every vertex is connected to the other 9 vertices, except for itself and its

immediate neighbors.

Step 3: Each vertex has 9 edges connected to it. Since there are 10 vertices,

the maximum number of edges in such a graph is 10 ×9/2 = 45.

Step 4: Since Ghas 20 edges, it must contain a cycle of length 4 or less.

This contradicts our assumption that Gdoes not contain a cycle of length 4 or

less.

Step 5: Therefore, our assumption must be false, and we conclude that G

must contain a cycle of length 4 or less.

Question 17

Question

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

a cycle with at most 6 edges.

Solution

To prove that Gcontains a cycle with at most 6 edges, we will use the fact that

in a connected graph with nvertices and medges, if m > n, then the graph

contains a cycle.

Step 1: Calculate the number of edges in a tree with 10 vertices. Since a

tree with 10 vertices has 9 edges, the maximum number of edges in a connected

graph with 10 vertices is 9 + 1 = 10.

Step 2: Using the fact that Ghas 15 edges, determine whether Gcontains

a cycle. Since Ghas 15 edges (which is greater than 10), Gmust contain a cycle.

Step 3: Prove that Gcontains a cycle with at most 6 edges. Assume the

contrary that all cycles in Ghave more than 6 edges. Since Gcontains a

cycle, the smallest cycle in Gmust have at least 7 edges (as 6-edge cycle is not

possible).

Step 4: Consider the 7-edge cycle and remove an edge to obtain a tree.

If we remove one of the edges from the 7-edge cycle, we obtain a tree with 10

vertices and 14 edges. However, this contradicts the fact that a tree with 10

vertices has 9 edges.

Therefore, the assumption must be false, and Gcontains a cycle with at

most 6 edges.

Question 18

Question

Let Gbe a connected graph with 12 vertices and 20 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

following theorem:

Theorem: If an undirected graph Ghas nvertices and medges, and n>m,

then Gcontains a cycle.

Step 1: Calculate the number of vertices and edges in the graph G. Given

that Ghas 12 vertices and 20 edges.

Step 2: Verify if the condition n>mis satisfied for the given graph G.

From the information given, n= 12 (number of vertices) and m= 20 (number

of edges). Since 12 >20, the condition n>mis satisfied.

Step 3: Apply the theorem to conclude that Gcontains a cycle. By the

theorem, since 12 >20, the graph Gmust contain a cycle.

Step 4: Determine the length of the shortest cycle in G. Since Gis con-

nected, the shortest cycle will be a triangle (3 vertices) or a square (4 vertices).

Step 5: Verify that the shortest cycle in Ghas a length at most 4. Since

the shortest cycle in Gis a triangle or a square, both of which have a length of

at most 4, we can conclude that Gcontains a cycle of length at most 4.

Therefore, we have shown that the connected graph Gwith 12 vertices and

20 edges contains a cycle of length at most 4.

Question 19

Question

Let Gbe a connected graph with nvertices, all of which have degree at least

2. Prove that Gis a connected graph with diameter at most 2.

Solution

To prove that Gis a connected graph with diameter at most 2, we will proceed

with the following steps:

Step 1: Show that Gis a connected graph.

Since Gis a connected graph with nvertices, we can start at any vertex v

and reach any other vertex uby traversing along the edges of G. Thus, Gis

connected.

Step 2: Show that the diameter of Gis at most 2.

Consider any two vertices uand vin G. Since Gis connected, there exists

a path between uand v. If this path is of length 1, i.e., uand vare adjacent

vertices, then the diameter is 1.

Now, suppose the path between uand vis of length greater than 1. Let wbe

a vertex on the path from uto vsuch that wis farthest away from u. Since all

vertices in Ghave degree at least n

2,wmust be connected to at least half of the

vertices in G. In particular, wis connected to both uand v. Therefore, there

exists a path from uto vpassing through w, which implies that the diameter

of Gis at most 2.

Thus, we have shown that Gis a connected graph with diameter at most 2.

Question 20

Question

Let Gbe a connected graph with 10 vertices, each with degree at least 3. Prove

that Gcontains a cycle of length at most 20

Solution

To prove that Gcontains a cycle of length at most 20

3, we will use the following

theorem:

Theorem: Every connected graph with nvertices and each vertex having

degree at least 3 contains a cycle of length at most 2n

Step 1: Since Ghas 10 vertices, and each vertex has degree at least 3, the

total number of edges in Gis at least 10·3

2= 15 by the Handshaking Lemma.

Step 2: Assume, for the sake of contradiction, that Gcontains no cycle of

length at most 20

3. Then, every cycle in Gmust have length at least 20

3+ 1.

Step 3: Consider different cycles in G. Let C1, C2, . . . , Ckbe the different

cycles in G.

Step 4: Since every cycle has length at least 20

3+ 1, the total number of

edges in Gis at most 3 ·(20

3+ 1) = 23.

Step 5: However, this contradicts the fact that Ghas at least 15 edges.

Therefore, our assumption that Gcontains no cycle of length at most 20

3is

incorrect.

Step 6: Hence, there must exist a cycle in Gof length at most 20

Question 21

Question

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

that if every vertex of Ghas degree at least n

2, then Gmust contain a cycle.

Solution

Step 1: Let’s assume that Gdoes not contain a cycle. Then Gmust be a tree.

Step 2: Since Gis a tree with nvertices, it must have n−1 edges.

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

in Gis equal to twice the number of edges. Since each vertex has degree at least

2, the sum of the degrees is at least n·n

Step 4: So, 2(n−1) ≥n2, which simplifies to 2n−2≥n2.

Step 5: Rearranging the inequality gives n2−2n+ 2 ≤0.

Step 6: However, this quadratic inequality has no real solutions for n≥2.

Step 7: Thus, by contradiction, we conclude that if every vertex of Ghas

degree at least n

2, then Gmust contain a cycle.

Question 22

Question

Let Gbe a connected graph with nvertices, medges, and exactly one cycle.

Prove that m=n.

Solution

To prove that m=n, we will make use of the cycle and connectedness properties

of the graph.

Step 1: Let’s denote the number of vertices in the cycle by k. Since the

graph has exactly one cycle, all other vertices should belong to the tree compo-

nent of the graph.

Step 2: The cycle contains kvertices and kedges. The tree component

consists of the remaining n−kvertices and m−kedges.

Step 3: Since the graph is connected, every vertex in the tree component

must be connected to the cycle. Therefore, each vertex in the tree component

contributes at least one edge to the total count of m.

Step 4: Combining the edges from the cycle and the tree component, we

have at least m≥k+ (n−k) = n.

Step 5: Since Gis connected, there are no isolated vertices in the graph.

Therefore, all nvertices are connected in some way.

Step 6: If m>n, this would imply some vertices are connected more than

once, forming a cycle other than the given one. This contradicts the assumption

that Ghas only one cycle.

Step 7: Therefore, we must have m=n, as required.

Thus, we have shown that in a connected graph with nvertices, medges,

and exactly one cycle, the number of edges is equal to the number of vertices,

m=n.

Question 23

Question

Let Gbe a connected graph with 10 vertices, each of degree at least 4. Prove

that Gcontains a cycle of length at most 10.

Solution

To prove that Gcontains a cycle of length at most 10, we will use the Pigeonhole

Principle.

Step 1: Consider the longest path Pin G. Let v1, v2, . . . , vkbe the vertices

in this path.

Step 2: Since Gis connected, each vertex in Ghas degree at least 4. This

means that each vertex on Phas at least 2 neighbors not on the path.

Step 3: For i= 1,2, . . . , k, let wibe a neighbor of vinot in P. Since Pis

the longest path, wimust be adjacent to at least one vertex in P.

Step 4: Consider the vertices w1, w2, . . . , wk. By the Pigeonhole Principle,

at least two of these vertices share a common neighbor in P. Let wiand wjbe

two such vertices.

Step 5: Since wiand wjboth have a common neighbor in P, there exists a

cycle in Gformed by the path from wito their common neighbor in P, followed

by the path from the common neighbor to wj, and closing the cycle by going

back from wjto wi.

Step 6: This cycle has length at most (i−j) + (j−i)=2k≤20, where k

is the length of the path P. Therefore, Gcontains a cycle of length at most 10.

Question 24

Question

Let Gbe a connected graph with nvertices such that every vertex in Ghas

degree at least n

2. Prove that Gis Hamiltonian.

Solution

To prove that Gis Hamiltonian, we will first show that Ghas a cycle containing

all vertices of G(Hamiltonian cycle).

Step 1: Let vbe a vertex of G. Since Gis connected, there exists a path

Pin Gthat connects vto every other vertex of G. Let ube a vertex in Psuch

that u=v.

Step 2: Consider the component of Gobtained by removing the vertex

vand all incident edges. Since all vertices in Ghave degree at least n

2, this

component has at least n

2vertices.

Step 3: Remove any n

2−1 vertices from this component to form a subgraph

Hwith n

2vertices. Since Hhas n

2vertices, by the Pigeonhole Principle, there

exists a vertex win Hthat is adjacent to u.

Step 4: Now, we construct a cycle in Gby following the path Pfrom vto

u, then adding the edge uw, and finally following the path in Hback to v.

Step 5: Repeat this process for every vertex of Gto obtain a cycle containing

all vertices of G. Therefore, Gis Hamiltonian.

Question 25

Question

Let Gbe a connected graph with 11 vertices and 16 edges. If Ghas exactly one

cycle, what is the minimum possible number of vertices in this cycle?

Solution

Let nbe the minimum possible number of vertices in the cycle in graph G.

Step 1: We know that in any graph, the sum of the degrees of all vertices

is equal to twice the number of edges. Therefore, in a graph with 11 vertices

and 16 edges, the sum of the degrees of all vertices is 2 ×16 = 32.

Step 2: Since Gis connected, each vertex in the cycle contributes at least

2 to the sum of degrees, and each non-cycle vertex contributes at least 1 to the

sum of degrees. Therefore, the sum of degrees of the non-cycle vertices is at

most 11 −n.

Step 3: Let Mbe the number of non-cycle vertices. The sum of the degrees

of all vertices can be expressed as 2n+ (11 −n) + 2M. Setting this equal to 32,

we have 2n+ (11 −n)+2M= 32.

Step 4: Now, we can simplify the equation: n+ 11 + 2M= 32 implies

n+ 2M= 21.

Step 5: Since Mis the number of non-cycle vertices and nis the minimum

number of vertices in the cycle, we want to maximize Mto minimize n. The

maximum value of Moccurs when M= 9, so n+ 2 ×9 = 21 which implies

n= 3.

Step 6: Therefore, the minimum possible number of vertices in the cycle in

graph Gis 3 .

Question 26

Question

Let Gbe a simple graph with 10 vertices and 20 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: Assume that Gis simple with 10 vertices and 20 edges.

Step 2: Calculate the maximum number of edges a simple graph with 10

vertices can have.

The complete graph K10 has 10

2= 45 edges. Any simple graph with 10

vertices will have at most 45 edges.

Step 3: Determine the number of ”extra” edges in Gbeyond the complete

graph K10.

Since Ghas 20 edges, and K10 has 45 edges, there are 45 −20 = 25 ”extra”

edges in G.

Step 4: Consider the 10 vertices of Gas the pigeonholes and the 25 ”extra”

edges as the pigeons.

Since there are more pigeons than pigeonholes, by the Pigeonhole Principle,

there must be at least one pair of vertices that is connected by more than one

edge.

Step 5: If there is a pair of vertices connected by more than one edge, then

there exists a cycle of length at least 4 in G.

If there are multiple edges between a pair of vertices, we can form a cycle of

length at least 4 using these multiple edges along with the shortest path between

the vertices.

Therefore, Gcontains a cycle of length at least 4.

Question 27

Question

Let Gbe a simple graph with 10 vertices and each pair of vertices is connected

by either an edge or a non-edge. If Ghas 28 edges, what is the maximum

number of vertices that can form a complete subgraph in G?

Solution

To find the maximum number of vertices that can form a complete subgraph in

G, we need to find the largest complete subgraph that can be formed by the 10

vertices.

Step 1: Determine the maximum number of edges a complete

subgraph of nvertices can have. For a complete subgraph with nvertices,

the maximum number of edges it can have is given by the formula E=n(n−1)

Step 2: Find the largest complete subgraph in G.We want to find

the value of nsuch that n(n−1)

2≤28, since Ghas 28 edges.

Solving n(n−1)

2= 28 gives n2−n−56 = 0. Factoring the quadratic equation,

we get (n−8)(n+7) = 0. Since nmust be positive, the largest complete subgraph

in Ghas 8 vertices.

Step 3: Answer the question. Therefore, the maximum number of ver-

tices that can form a complete subgraph in Gis 8.

Question 28

Question

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

at least one cycle.

Solution

Step 1: Let’s use the fact that a connected graph with nvertices and n−1

edges is a tree. We will try to show that if Gis connected with 10 vertices and

13 edges, then it must contain a cycle.

Step 2: Since Ghas 10 vertices and 13 edges, it has more edges than a tree

with 10 vertices, which would have 9 edges. This means Gmust have at least

one cycle.

Step 3: Suppose for the sake of contradiction that Gdoes not contain a cycle.

Then Gis a forest, which is a disjoint union of trees. Since Gis connected, it

cannot be a forest.

Step 4: Therefore, we have reached a contradiction, and our initial assump-

tion that Gdoes not contain a cycle is false. Hence, Gmust contain at least

one cycle.

Question 29

Question

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

a subgraph isomorphic to K3,3(the complete bipartite graph with parts of size

3).

Solution

To prove that Gcontains a subgraph isomorphic to K3,3, we will use the fact

that every connected graph with 10 vertices and 15 edges contains a subgraph

isomorphic to K3,3.

Step 1: Find the average degree of the vertices in G.Since Gis a

connected graph with 10 vertices and 15 edges, the average degree of the vertices

in Gis 2 ×15

10 = 3.

Step 2: Find the minimum degree in G.By the Handshaking Lemma,

the sum of the degrees of all vertices in Gis twice the number of edges, which

is 30. Since the average degree is 3, every vertex in Gmust have degree at least

3. Therefore, the minimum degree in Gis 3.

Step 3: Apply the Dirac’s theorem. Dirac’s theorem states that if Gis

a graph with nvertices (n≥3) such that every vertex has degree at least n/2,

then Gcontains a Hamiltonian cycle. In our case, n= 10 and the minimum

degree is 3, which is greater than n/2 = 5. Therefore, Gcontains a Hamiltonian

cycle, and since K3,3is a subgraph of a Hamiltonian cycle, Gmust contain a

subgraph isomorphic to K3,3.

Thus, we have proved that the connected graph Gwith 10 vertices and 15

edges contains a subgraph isomorphic to K3,3.

Question 30

Question

Let Gbe a simple graph with 10 vertices, each having degree at least 4. Prove

that Gcontains a cycle of length at least 4.

Solution

Let’s prove this statement by contradiction.

Step 1: Assume that Gdoes not contain a cycle of length at least 4.

Step 2: Since Gis a simple graph with 10 vertices, each having degree at

least 4, let’s consider the worst-case scenario where each vertex is connected to

exactly 4 other vertices. This implies that the number of edges in Gis 10·4

2= 20

(by Handshaking Lemma).

Step 3: In a graph without a cycle of length at least 4, the longest possible

cycle is a triangle. In a triangle, each vertex has degree 2. Therefore, the number

of edges required to form a triangle with 10 vertices is 3·10

2= 15 which is less

than the total number of edges in G.

Step 4: However, if Gdoes not contain a cycle of length at least 4, then it

can have at most 15 edges as shown in Step 3. This contradicts the fact that G

has 20 edges (from Step 2).

Step 5: Therefore, our assumption in Step 1 is incorrect. Hence, Gmust

contain a cycle of length at least 4.

Question 31

Question

Let Gbe a connected graph with 10 vertices and 15 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 a proof by

contradiction.

Step 1: Assume there are no cycles of length at least 4 in G.

Since Gis a connected graph with 10 vertices and 15 edges, it follows from

Euler’s formula that Ghas 10 - 15 + 1 = -4 connected components. This

contradicts the fact that Gis a connected graph.

Step 2: Therefore, our assumption was incorrect and there must be a cycle

of length at least 4 in G.

Thus, we have proved that a connected graph Gwith 10 vertices and 15

edges must contain a cycle of length at least 4.

Question 32

Question

Let Gbe a connected graph with 12 vertices and 20 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 a proof by

contradiction.

Step 1: Assume that Gdoes not contain a cycle of length at least 4.

Since Gis a connected graph with 12 vertices, it must have at least 11 edges

to be connected. Thus, Gneeds 11 edges to have at least one cycle.

Let ebe an arbitrary edge in G. Removing efrom Gwill disconnect Ginto

two components. Since Gis connected and removing edisconnects G, the graph

G−ewill have at least two connected components.

Step 2: Analyze the number of edges in G−e.

Since Ghas 20 edges and we removed one edge e, the graph G−ewill have

19 edges.

Step 3: Find the maximum number of edges a tree with 12 vertices can

have.

A tree with nvertices has n−1 edges. Therefore, a tree with 12 vertices

can have at most 11 edges.

Step 4: Consider the edges in the two components of G−e.

Since G−ehas 19 edges and can be divided into two components, at least

one of the components will have more than 9 edges. This violates the fact that

a tree with 12 vertices can have at most 11 edges.

This contradiction arises from our initial assumption that Gdoes not contain

a cycle of length at least 4. Therefore, Gmust contain a cycle of length at least

Question 33

Question

Let Gbe a simple graph with nvertices, medges, and connectivity κ(G). Prove

that if Gis connected and every vertex has degree at least n

2, then κ(G)≥n−1.

Solution

Let Gbe a connected simple graph with nvertices, medges, and δ(G)≥n

We want to show that κ(G)≥n−1.

Step 1: We know that if Gis connected, then κ(G)≤δ(G).

Step 2: Since the minimum degree of Gis at least n

2, we have δ(G)≥n

Step 3: Combining Step 1 and Step 2, we get κ(G)≥n

Step 4: Since κ(G) is an integer, we have κ(G)≥n

2.

Step 5: We know that n

2≥n−1 for all n≥3.

Step 6: Therefore, we conclude that κ(G)≥n−1. Thus, if Gis connected

and every vertex has degree at least n

2, then κ(G)≥n−1.

Question 34

Question

Let Gbe a connected graph with nvertices where n≥3. Suppose that every

vertex in Ghas degree at least n/2. Prove that Gis Hamiltonian.

Solution

Step 1: Since Gis connected with nvertices, we have to show that there exists

a Hamiltonian cycle in G.

Step 2: Let v1be an arbitrary vertex in G. Since v1has degree at least n/2

and Ghas nvertices, v1has at least n/2 neighbors.

Step 3: Let v2be any neighbor of v1. If all the neighbors of v1are distinct,

then we have a Hamiltonian path between v1and v2.

Step 4: If all the neighbors of v1are not distinct, then we consider the first

time we revisit a vertex, say vk, while traversing the neighbors of v1.

Step 5: Since vkhas at least n/2 neighbors in Gand we revisit it while

traversing the neighbors of v1, there exists a neighbor, say vk+1, of vkthat is

not part of the path between v1and vk.

Step 6: By following this process of choosing new neighbors that are not

already part of the path, we create a Hamiltonian cycle in Gthat includes all

nvertices.

Step 7: Therefore, Gis Hamiltonian.

Question 35

Question

Let Gbe a connected graph with 8 vertices, each of degree 3. Prove that G

contains a cycle of length 4.

Solution

Given: Gis a connected graph with 8 vertices, each of degree 3.

Step 1: Count the number of edges in G. Since each vertex has degree 3,

the total number of edges in Gis 1

2(3 ×8) = 12.

Step 2: Consider the possible cases for the number of odd degree vertices

in G. In a connected graph, the number of odd degree vertices is always even.

Step 3: Assume there are 0 vertices of odd degree. If there are no odd

degree vertices, then all vertices have even degree which means there must be a

cycle of length 4 or more (since cycles must have even length).

Step 4: Assume there are 2 vertices of odd degree. If there are 2 odd degree

vertices, then the other 6 vertices have degree 3, forming a cycle of length 4.

Step 5: Assume there are 4 vertices of odd degree. If there are 4 odd degree

vertices, then the other 4 vertices have degree 3. By the Pigeonhole Principle,

at least one pair of odd degree vertices must be adjacent. Thus, there exists a

cycle of length 4.

Step 6: Assume there are 6 vertices of odd degree. If there are 6 odd degree

vertices, then the other 2 vertices have degree 3. By the Pigeonhole Principle,

either: - Both of the odd degree vertices have neighbors among the remaining 6

vertices, which forms a cycle of length 4, or - One of the odd degree vertices has

both neighbors among the remaining 6 vertices, and the other has one neighbor,

forming a cycle of length 4.

Step 7: Therefore, in all cases, the graph Gcontains a cycle of length 4.

Question 4

Question

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

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

Solution

To prove this statement, we will use the Pigeonhole Principle. Let’s assume for

the sake of contradiction that Gdoes not contain a cycle of length at least 4.

Step 1: Counting edges Since Ghas 10 vertices and every vertex has

degree at least 3, the total number of edges in Gis at least 3·10

2= 15 (since each

edge contributes to the degree of 2 vertices).

Step 2: Counting faces Let’s denote the number of vertices, edges, and

faces in Gby V,E, and F, respectively. By Euler’s formula, we have V−E+F=

2 for any connected planar graph. Since Gis connected and not a tree, we have

E≥V+ 1 (since a tree with Vvertices has V−1 edges). Substituting E≥15

into Euler’s formula gives F≤7.

Step 3: Applying the Pigeonhole Principle Consider each face in the

planar representation of G. Since every face is bounded by a cycle, every face

has at least 3 edges. The average number of edges per face is 2E

F≥2·15

7>4. By

the Pigeonhole Principle, there must exist a face bounded by a cycle of length

at least 4, which contradicts our assumption.

Therefore, our assumption that Gdoes not contain a cycle of length at least

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

Question 5

Question

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

a cycle of length at least 4.

Solution

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

Principle.

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

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

number of edges in a tree with 10 vertices is 10 −1 = 9.

Step 2: Find the minimum number of edges needed to form a

graph with 10 vertices that is not a tree. Since Ghas 15 edges and the

maximum number of edges in a tree with 10 vertices is 9, we need at least

15 −9 = 6 more edges to form a graph that is not a tree.

Step 3: Apply the Pigeonhole Principle. In a graph with 10 vertices,

the minimum degree of a vertex in a graph is 2 (if Gis a tree, then the minimum

degree is 1). Since we need at least 6 more edges to form a graph that is not

a tree, there must be at least one vertex with degree greater than 2, meaning

there is a cycle in G.

Hence, Gcontains a cycle of length at least 4.

Question 6

Question

Let Gbe a connected graph with nvertices, each with degree at least n

2. Prove

that Gis Hamiltonian, i.e., it contains a Hamiltonian cycle.

Solution

Let’s prove the statement by contradiction:

Step 1: Assume that Gis not Hamiltonian.

Step 2: By Dirac’s Theorem, if Gis a graph with n≥3 vertices such that

each vertex has degree at least n

2, then Gis Hamiltonian. Since our assumption

contradicts Dirac’s Theorem, there must be a vertex vin Gwith degree less

than n

Step 3: Let vbe a vertex with degree less than n

2in G. Since Gis connected,

there must be a path from vto any other vertex in G. Let ube a vertex adjacent

to v.

Step 4: Since deg(v)<n

2, there are at least n

2+1 vertices in Gnot adjacent

to v. Since Gis connected and uis adjacent to v, there must be a vertex wnot

adjacent to vbut adjacent to u.

Step 5: Now consider the graph G′=G− {v, w}+{uw}, where we remove

vertices vand walong with their incident edges, and add the edge uw. Notice

that every vertex in G′still has degree at least n

Step 6: By repeating this process, we can construct a new graph with n−1

vertices, each with degree at least n−1

2. Continuing this process, we eventually

arrive at a subgraph G′′ with three vertices such that all vertices have degree

at least 1.

Step 7: Since G′′ has three vertices and each vertex has degree at least 1,

it forms a Hamiltonian cycle, which contradicts our assumption that Gis not

Hamiltonian.

Step 8: Therefore, our initial assumption that Gis not Hamiltonian is false,

and thus Gmust be Hamiltonian.

Question 7

Question

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

a pair of vertices with degree at least 3.

Solution

Let’s prove this by contradiction.

Step 1: Assume for the sake of contradiction that every pair of vertices in

Ghas degree at most 2.

Step 2: Since Ghas 10 vertices, each vertex can have a maximum degree of 9

(connecting to all other vertices except itself). But according to our assumption,

each vertex has degree at most 2. This means the maximum number of edges

in Gcan be 10 ×2 = 20.

Step 3: However, we are given that Ghas 20 edges. This implies that our

assumption is incorrect, and there must exist at least one pair of vertices in G

with degree greater than 2.

Step 4: Therefore, we have proved by contradiction that in any simple

graph with 10 vertices and 20 edges, there must be at least one pair of vertices

with degree at least 3.

Question 8

Question

Let Gbe a connected graph with nvertices and n+ 3 edges. Prove that G

contains at least one cycle.

Solution

To prove that Gcontains at least one cycle, we will use the fact that in a

connected graph with nvertices, n−1 edges are necessary and sufficient for the

graph to be a tree. Since Ghas n+ 3 edges, it must contain at least one cycle.

Step 1: Let’s assume by contradiction that Gis a connected graph with n

vertices and n+ 3 edges, but does not contain any cycles.

Since Gis acyclic, it must be a tree and hence has n−1 edges. However,

n−1< n + 3, which contradicts our assumption.

Therefore, our assumption that Gdoes not contain any cycles is false, and

Gmust contain at least one cycle.