mmte-001-solved-assignment-2024-ss-8e24e610-06c9-4b43-84f6-a5bf6ef5ab5c

1. State whether the following statements are true or false. Justify your answers with a short proof or a counterexample
   i) There exists no 9-vertex graph with three vertices of degree 3 , four vertices of degree 2 and two vertices of degree 1 .

• Three vertices of degree 3
• Four vertices of degree 2
• Two vertices of degree 1

• $C_6$$C_6$C_(6)C_6$C_6$ represents a cycle graph with 6 vertices, which means it has a cycle of length 6.
• $P_4$$P_4$P_(4)P_4$P_4$ represents a path graph with 4 vertices, which is a linear graph with no cycles.
• The operation $\vee$$\vee$vv\vee$\vee$ represents the join of two graphs, which means connecting every vertex of the first graph to every vertex of the second graph.

• The diameter of a graph is the length of the longest shortest path between any two vertices in the graph.
• The girth of a graph is the length of the shortest cycle in the graph.

• A Hamiltonian graph is a graph that contains a Hamiltonian cycle, which is a cycle that visits every vertex exactly once.
• An Eulerian graph is a graph in which all vertices have even degree, and there exists a cycle (called an Eulerian cycle) that traverses every edge exactly once.

• A graph is said to be $k$$k$kk$k$-connected if there is no set of $k-1$$k-1$k-1k-1$k-1$ vertices whose removal disconnects the graph.
• A graph is said to be $k$$k$kk$k$-edge-connected if there is no set of $k-1$$k-1$k-1k-1$k-1$ edges whose removal disconnects the graph.

• An Eulerian graph is a graph in which there exists a closed walk that visits every edge exactly once.
• $L(G)$$L(G)$L(G)L(G)$L(G)$ represents the line graph of $G$$G$GG$G$, which is a graph whose vertices represent the edges of $G$$G$GG$G$ and where two vertices in $L(G)$$L(G)$L(G)L(G)$L(G)$ are adjacent if and only if their corresponding edges in $G$$G$GG$G$ are incident (share a common vertex) in $G$$G$GG$G$.

• ${\chi }^{\mathrm{\prime }}(G)$${\chi }^{\mathrm{\prime }}(G)$chi^(‘)(G)\chi^{\prime}(G)${\chi }^{\mathrm{\prime }}(G)$ represents the edge chromatic number of a graph $G$$G$GG$G$, which is the minimum number of colors needed to color the edges of $G$$G$GG$G$ such that no two adjacent edges share the same color.
• $C_3$$C_3$C_(3)C_3$C_3$ is the cycle graph with 3 vertices, also known as a triangle.
• $K_2$$K_2$K_(2)K_2$K_2$ is the complete graph with 2 vertices, which is essentially a single edge.
• $C_3\times K_2$$C_3\times K_2$C_(3)xxK_(2)C_3 \times K_2$C_3\times K_2$ represents the Cartesian product of $C_3$$C_3$C_(3)C_3$C_3$ and $K_2$$K_2$K_(2)K_2$K_2$, which results in a graph where each vertex of $C_3$$C_3$C_(3)C_3$C_3$ is connected to each vertex of $K_2$$K_2$K_(2)K_2$K_2$, forming a hexagon.

• $\chi (G)$$\chi (G)$chi(G)\chi(G)$\chi (G)$ represents the chromatic number of a graph $G$$G$GG$G$, which is the minimum number of colors needed to color the vertices of $G$$G$GG$G$ such that no two adjacent vertices share the same color.
• $\omega (G)$$\omega (G)$omega(G)\omega(G)$\omega (G)$ represents the clique number of $G$$G$GG$G$, which is the size of the largest complete subgraph (clique) in $G$$G$GG$G$.

• A $k$$k$kk$k$-chromatic graph is a graph whose chromatic number $\chi (G)$$\chi (G)$chi(G)\chi(G)$\chi (G)$ is equal to $k$$k$kk$k$.
• The size of a graph refers to the number of edges in the graph.
• $\left(\begin{array}{c}k\\ 2\end{array}\right)$$\left(\begin{array}{c}k\\ 2\end{array}\right)$([k],[2])\left(\begin{array}{c}k \\ 2\end{array}\right)$\left(\begin{array}{c}k\\ 2\end{array}\right)$ is the binomial coefficient, representing the number of ways to choose 2 elements from a set of $k$$k$kk$k$ elements, which is also equal to $\frac{k(k-1)}{2}$$\frac{k(k-1)}{2}$(k(k-1))/(2)\frac{k(k-1)}{2}$\frac{k(k-1)}{2}$.

• A hypercube $Q_n$$Q_n$Q_(n)Q_n$Q_n$ is a graph that represents an $n$$n$nn$n$-dimensional cube. It has $2^n$$2^n$2^(n)2^n$2^n$ vertices, each corresponding to a unique $n$$n$nn$n$-bit binary string. Two vertices are adjacent if and only if their binary strings differ in exactly one bit.
• A perfect matching in a graph is a set of edges such that every vertex in the graph is incident to exactly one edge in the set.