Sample Solution

MMTE-001 Solved Assignment 2023

Question:-01

1.State whether the following statements are true or false. Justify your answers with a short proof or a counterexample

i) Every tree has a perfect matching.

Answer:

let’s address the statement:

“Every tree has a perfect matching.”

This statement is false.

Justification:

A perfect matching in a graph is a set of edges such that every vertex of the graph is adjacent to exactly one edge in the set, and no two edges in the set share a common vertex.

For a tree to have a perfect matching, it must have an even number of vertices. This is because each edge in the matching covers exactly two vertices, so if there’s an odd number of vertices, at least one vertex will be left unmatched.

Counterexample:

Consider a simple tree with 3 vertices and 2 edges (a path of length 2). This tree does not have a perfect matching because one of the three vertices will always be left unmatched.

Thus, the statement “Every tree has a perfect matching” is false.

ii) Every 2-connected bipartite graph is Hamiltonian.

Answer:

The statement is:

“Every 2-connected bipartite graph is Hamiltonian.”

This statement is false.

Justification:

A graph is Hamiltonian if it has a Hamiltonian cycle, which is a cycle that visits every vertex exactly once and returns to the starting vertex. A bipartite graph is one whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent.

For a bipartite graph to be Hamiltonian, it must satisfy the following condition: both sets of vertices (let’s call them A and B) must have the same number of vertices. This is because a Hamiltonian cycle in a bipartite graph will alternate between vertices in A and B. If one set has more vertices than the other, it’s impossible to form a Hamiltonian cycle.

Counterexample:

Consider a bipartite graph with sets A and B where $|A|=3$$|A|=3$|A|=3|A| = 3$|A|=3$ and $|B|=2$$|B|=2$|B|=2|B| = 2$|B|=2$. The graph is 2-connected, but it cannot have a Hamiltonian cycle because the two sets have different numbers of vertices. Specifically, imagine three vertices on the left (set A) and two on the right (set B). Even if every vertex is connected to every other vertex across the sets, you can’t form a cycle that visits every vertex exactly once and returns to the starting vertex.

Thus, the statement “Every 2-connected bipartite graph is Hamiltonian” is false.

iii) For some nonnegative integers $d_1,d_2,\dots ,d_n$$d_1,d_2,\dots ,d_n$d_(1),d_(2),dots,d_(n)d_1, d_2, \ldots, d_n$d_1,d_2,\dots ,d_n$ the sequence $(max\{d_1,n\},d_2,d_3,\dots ,d_n)$$\left(max\left\{d_1,n\right\},d_2,d_3,\dots ,d_n\right)$(max{d_(1),n},d_(2),d_(3),dots,d_(n))\left(\max \left\{d_1, n\right\}, d_2, d_3, \ldots, d_n\right)$(max\{d_1,n\},d_2,d_3,\dots ,d_n)$ is graphic.

Answer:

The statement is:

“For some nonnegative integers $d_1,d_2,\dots ,d_n$$d_1,d_2,\dots ,d_n$d_(1),d_(2),dots,d_(n)d_1, d_2, \ldots, d_n$d_1,d_2,\dots ,d_n$ the sequence $(max\{d_1,n\},d_2,d_3,\dots ,d_n)$$\left(max\left\{d_1,n\right\},d_2,d_3,\dots ,d_n\right)$(max{d_(1),n},d_(2),d_(3),dots,d_(n))\left(\max \left\{d_1, n\right\}, d_2, d_3, \ldots, d_n\right)$(max\{d_1,n\},d_2,d_3,\dots ,d_n)$ is graphic.”

To determine if this statement is true or false, we need to understand what it means for a sequence to be graphic. A sequence of nonnegative integers is said to be graphic if there exists a simple, undirected graph with no loops or multiple edges such that the degrees of its vertices correspond to the numbers in the sequence.

The statement is suggesting that for some sequences of degrees, if we replace $d_1$$d_1$d_(1)d_1$d_1$ with the maximum of $d_1$$d_1$d_(1)d_1$d_1$ and $n$$n$nn$n$, the resulting sequence is still graphic.

This statement is false.

Justification:

Consider the sequence $d_1,d_2,\dots ,d_n$$d_1,d_2,\dots ,d_n$d_(1),d_(2),dots,d_(n)d_1, d_2, \ldots, d_n$d_1,d_2,\dots ,d_n$ where $d_1=0$$d_1=0$d_(1)=0d_1 = 0$d_1=0$ and all other $d_i$$d_i$d_(i)d_i$d_i$ values are 1. This sequence is graphic because it represents a star graph with $n-1$$n-1$n-1n-1$n-1$ edges and $n$$n$nn$n$ vertices.

Now, let’s replace $d_1$$d_1$d_(1)d_1$d_1$ with the maximum of $d_1$$d_1$d_(1)d_1$d_1$ and $n$$n$nn$n$. Since $d_1=0$$d_1=0$d_(1)=0d_1 = 0$d_1=0$, the new $d_1$$d_1$d_(1)d_1$d_1$ value will be $n$$n$nn$n$. The new sequence becomes $n,1,1,\dots ,1$$n,1,1,\dots ,1$n,1,1,dots,1n, 1, 1, \ldots, 1$n,1,1,\dots ,1$. This sequence is not graphic. The reason is that the first vertex is supposed to have $n$$n$nn$n$ edges connected to it, but there are only $n-1$$n-1$n-1n-1$n-1$ other vertices available, each of which can only provide one edge.

Thus, the statement “For some nonnegative integers $d_1,d_2,\dots ,d_n$$d_1,d_2,\dots ,d_n$d_(1),d_(2),dots,d_(n)d_1, d_2, \ldots, d_n$d_1,d_2,\dots ,d_n$ the sequence $(max\{d_1,n\},d_2,d_3,\dots ,d_n)$$\left(max\left\{d_1,n\right\},d_2,d_3,\dots ,d_n\right)$(max{d_(1),n},d_(2),d_(3),dots,d_(n))\left(\max \left\{d_1, n\right\}, d_2, d_3, \ldots, d_n\right)$(max\{d_1,n\},d_2,d_3,\dots ,d_n)$ is graphic” is false.

iv) Grötzsch graph is Eulerian.

Answer:

The statement is:

“Grötzsch graph is Eulerian.”

A graph is Eulerian if it contains an Eulerian cycle, which is a cycle that visits every edge exactly once and returns to the starting vertex. For a graph to be Eulerian, every vertex must have an even degree.

The Grötzsch graph is a triangle-free graph with 11 vertices and 20 edges.

To determine if the Grötzsch graph is Eulerian, we need to check the degrees of its vertices.

Justification:

The Grötzsch graph is known to have the following degree sequence: 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4.

From the degree sequence, it’s clear that there are four vertices of degree 5, which is odd. Since an Eulerian graph must have all vertices of even degree, the Grötzsch graph cannot be Eulerian.

Thus, the statement “Grötzsch graph is Eulerian” is false.

v) $K_4$$K_4$K_(4)K_4$K_4$, as a plane graph, is self-dual.

Answer:

The statement is:

“$K_4$$K_4$K_(4)K_4$K_4$, as a plane graph, is self-dual.”

A graph is self-dual if its planar embedding is isomorphic to its dual graph. The dual graph of a planar graph has a vertex for each face of the original graph and an edge for each edge in the original graph that separates the corresponding faces.

Justification:

The graph $K_4$$K_4$K_(4)K_4$K_4$ is the complete graph on 4 vertices. When drawn in the plane without any edges crossing, $K_4$$K_4$K_(4)K_4$K_4$ divides the plane into 4 regions: 3 triangular regions and 1 outer region.

The dual graph of this planar embedding of $K_4$$K_4$K_(4)K_4$K_4$ will have 4 vertices (one for each region). Since each triangular region in $K_4$$K_4$K_(4)K_4$K_4$ is bounded by 3 edges, each vertex in the dual graph will have degree 3. This means the dual graph is also $K_4$$K_4$K_(4)K_4$K_4$.

Thus, the planar embedding of $K_4$$K_4$K_(4)K_4$K_4$ is isomorphic to its dual, making $K_4$$K_4$K_(4)K_4$K_4$ self-dual when considered as a plane graph.

Therefore, the statement “${\mathit{K}}_{\mathbf{4}}$${\mathit{K}}_{\mathbf{4}}$K_(4)\boldsymbol{K_4}${\mathit{K}}_{\mathbf{4}}$, as a plane graph, is self-dual” is true.