Question

a) Obtain the Ferrar graph of the partition 8+7+6+5+5+3+2+1. Find the conjugate
partition. Is the partition self conjugate?
b) For the graph in Fig. Fig. 2 on the following page find a minimal colouring.
c) Is Petersen graph bipartite? Give reasons for your answer.

Answer 1

ANSWER on Question #81205 – Math – Discrete Mathematics

QUESTION

a) Obtain the Ferrar graph of the partition $8 + 7 + 6 + 5 + 5 + 3 + 2 + 1$ . Find the conjugate partition. Is the partition self-conjugate?

b) For the graph in Fig.2 on the following page find a minimal colouring.

c) Is Petersen graph bipartite? Give reasons for your answer.

SOLUTION

c) Here is an example of the Petersen graph. We number its vertices.

We recall one of the properties of a bipartite graph:

A graph is bipartite if and only if it does not contain an odd cycle.

(More information: https://en.wikipedia.org/wiki/Bipartite_graph#Properties)

In our case,

The Petersen graph contains an odd cycle: $1 \leftrightarrow 2 \leftrightarrow 3 \leftrightarrow 4 \leftrightarrow 5 \leftrightarrow 1$ .

Conclusion,

Petersen's graph is not bipartite

b)

Figure 2

Recall the definition of a planar graph:

A graph is called planar if it can be drawn in the plane without any edges crossing (where a crossing of edges is the intersection of the lines or arcs representing them at a point other than their common endpoint).

Also remember The four color theorem: Every planar graph can be colored using no more than four colors.

In our case,

This graph is planar. It is obvious that it can't be colored in two colors, but we need to check only the possibility of coloring in three colors.

This edge is prevented from coloring this graph in three colors.

Conclusion,

This graph can be colored only in 4 colors.

a) Define a Ferrers graph to be a bipartite graph on the vertex partition $U = \{u_0, \dots, u_n\}$ and $V = \{v_0, \dots, v_n\}$ such that

1) if $\left(u_{i}, u_{j}\right)$ is an edge then so is $\left(u_{p}, u_{q}\right)$ for $0 \leq p \leq i$ and $0 \leq q \leq j$ .

2) $(u_0, u_m)$ and $(u_n, u_0)$ are edges.

In our case,

the Ferrers graph of the partition $8 + 7 + 6 + 5 + 5 + 3 + 2 + 1$

The conjugate partition is

We define that the number of partitions of a positive integer into odd distinct parts equals the number of partitions whose Ferrers diagrams are self-conjugate.

In our case,

The diagram contains 8, 6, 2. Therefore,

the partition isn't self-conjugate

Answer provided by https://www.AssignmentExpert.com