Discrete Mathematics Test 4

Concept:

A cyclic graph is a connected graph in which vertices is equal to the number of edges, and every vertex has degree 2

Explanation:

Consider a graph of odd cycle C_n and n≥ 3 (by definition)

The minimum number of colors required to edge-color G is 3

if n is even

The minimum number of colors required to edge-color G is 2

Therefore we need at least 3 colors to edge-color G

Vertices in G₁ = 5

Vertices in G₂ = 9

Vertices in G₃ = 13

Maximum edges are possible if it is a complete graph

For G₁: maximum number of edges:

\(\frac{{n\left( {n - 1} \right)}}{2} = \frac{{5 \times 4}}{2} = 10\)

For G₂: maximum number of edges:

\(\frac{{9\left( {9 - 1} \right)}}{2} = \frac{{9 \times 8}}{2} = 36\)

For G₃: maximum number of edges:

\(\frac{{13\left( {13 - 1} \right)}}{2} = \frac{{13 \times 12}}{2} = 78\;\)

Sum of the edges = 10 + 36 + 78 = 124

The number of perfect matching in a complete graph K_2n is given by \({(2n)! \over n!2^n}\)

Therefore, the number of perfect matching in a complete graph K₆ is \({6!\over 3!2^3}\)= 15

Concepts:

The complementary graph G' of a simple graph G has the same vertex set as G, and two vertices are adjacent in G' if and only if they are not adjacent in G.

An n-vertex self-complementary graph has exactly half number of edges of the complete graph.

∴ e = e’ = 39

Sum of edges in G and G’ is equal to edges in complete graph with n vertices

Formula:

\(^{n}{{C}_{2}}=e+e'\)

Calculation:

\(\frac{\text{n}\left( \text{n}-1 \right)}{2}=39+39\)

n² - n - 156 = 0

(n - 13) (n + 12) = 0

Since n > 0

∴ n = 13.

Important Points:

n is the number of vertices in G or G’

e and e’ are number of edges in G or G’ respectively

III is not simple graph as highest degree in any simple graph with n vertices is (n-1). II is also not a simple graph because it has 7 vertices and two vertices has degree 6, hence minimum degree cannot be 1. We can use Havel-Hakimi method for I & IV. We can show II is not simple graph using Havel-Hakimi method also.

Concept:

Since there is only one simple path between each pair of vertices, the given graph is a tree.

Tree with n nodes has (n -1) edges

Let the number of vertices of degree 1 be x.

2 vertices have degree 4

2 vertices have degree 2

1 vertex has degree 3

Calculation:

Total number of nodes in a graph = x + 2 + 2 + 1 = x + 5

Total number of nodes in a graph = x + 5 - 1 = x + 4

According to Handshaking Lemma,

∑deg(v) = 2|E|

\( {{2 \times 4 + 1 \times 3 + 2 \times 2 + x}} = 2(x + 4)\)

15 + x = 8 + 2x

∴ x = 7