Graphs and Digraphs

Draw the diagram of each of the following graphs $G=(V, E)$ :

Draw the diagram of each of the following graphs $G=(V, E)$ :

Identify the simple graphs in the previous two problems. If a simple graph is identified, determine whether it is (i) a bipartite graph, (ii) a complete graph, (iii) a complete bipartite graph, or (iv) a complete nonbipartite graph.

The complement of a simple graph $G=(V, E)$ is the simple graph $\bar{G}=(V, F)$ in which there is an edge between two vertices $\nu$ and $w$ if and only if there is no edge between $\nu$ and $w$ in $G$. Obviously, the complement of the complement of $\bar{G}$ is $G$. Draw the diagrams of the complements of the simple graphs identified in Problems 1.1 and 1.2.

Show that the complement of a bipartite graph need not be a bipartite graph.

Draw the diagram of an orientation of the simple nonbipartite graph that is not complete identified from Problems 1.1 and 1.2.

Any orientation of the complete graph with vertex set $\left\{ 1,2, \ldots , n\right\}$ is a tournament, and it is a transitive tournament if there is an arc from $i$ to $k$ whenever there is an arc from $i$ to $j$ and an arc from $j$ to $k$ for all choices of $i, j$, and $k$. Construct both a transitive tournament with four vertices and one that is not transitive.

Show that every simple graph of order $n$ is isomorphic to a subgraph of the complete graph with $n$ vertices.

If two graphs $G$ and $G^{\prime }$ are isomorphic, the order of $G$ is equal to the order of $G^{\prime }$ and the size of $G$ is equal to the size of $G^{\prime }$.

Show that two graphs need not be isomorphic even when they both have the same order and same size.

Show that two simple graphs are isomorphic if and only if their complements are isomorphic.

Determine whether the three graphs given in Fig. 1-10 are isomorphic.

Fig. 1-10

Suppose $N(n, k)$ is the number of nonisomorphic simple graphs with $n$ vertices and $k$ edges. Find $N(4,3)$.

Find all nonisomorphic simple graphs of order 4.

A simple graph that is isomorphic to its complement is called a self-complementary graph. Find a selfcomplementary graph of order 4.

Find two self-complementary graphs of order 5.

Find a vertex-induced bipartite subgraph of the graph in Fig. 1-6(a).

A set $I$ of vertices in a simple graph $G=(V, E)$ is an independent set (also known as an internally stable set) in $G$ if no two vertices in $I$ are adjacent. A set $K$ of vertices in $G$ is called a vertex cover if every edge in the graph is incident to at least one vertex in $K$. Show that a set $K$ of vertices is a vertex cover if and only if its complement $(V-K)$ is an independent set.

An independent set $I$ in a simple graph $G$ is a maximum independent set if there is no independent set $I^{\prime }$ in $G$ such that $\left|I^{\prime }\right|>\left|I\right|$. The number of vertices in a maximum independent set in $G$ is the independence number $\alpha (G)$ (also known as the internal stability number) of the graph $G$. A vertex cover $K$ in a graph $G$ is a minimum vertex cover if there is no vertex cover $K^{\prime }$ such that $\left|K^{\prime }\right|<\left|K\right|$. The number of vertices in a minimum vertex cover is called the vertex-covering number $\beta (G)$ of the graph $G$. Find the vertex-covering number and the independence number of the graph in Fig. 1-14.

Fig. 1-14

Show that in a simple graph $G$ of order $n, \alpha (G)+\beta (G)=n$.

A subset $D$ of vertices in a simple graph $G$ is a dominating vertex set (also known as an external dominating set) if every vertex not in $D$ is adjacent to at least one vertex in $D$. Find:

A dominating vertex set $D$ is a minimum dominating vertex set if there is no dominating set $D^{\prime }$ such that $\left|D^{\prime }\right|<\left|D\right|$. The number of vectors in a minimum dominating vertex set is the vertex domination number $\sigma (G)$ (also known as the external stability number) of the graph. Show that the vertex domination number of a simple graph cannot exceed its independence number.

An independent set is a maximal independent set if it is not a proper subset of another independent set. Show that an independent set is a dominating vertex set if and only if it is a maximal independent set. (A maximal independent set is not the same as a maximum independent set defined in Problem 1.19.)

Show that if there are at least two people who do not know each other among a set of individuals, it is possible to choose people from that set to form a committee such that no two individuals in the committee know each other and that every individual in the set not included in the committee is known to at least one person in the committee.

A committee $S$ as described in Problem 1.24 is a minimum committee if there is no committee $S^{\prime }$ such that $\left|S^{\prime }\right|<\left|S\right|$. The committee number of a set is the cardinality of a minimum committee in the set. Find the committee number of the acquaintance graph in Fig. 1-14.

A set $M$ of edges in a graph is called a matching (also known as an independent edge set) if no two edges in $M$ have a vertex in common. A set of edges $L$ is an edge cover if every vertex of positive degree is a vertex of at least one edge in $L$. Show that the complement of a matching need not be an edge cover. (Compare this result with that of Problem 1.18.)

A matching $M$ in a simple graph is a maximum matching (also known as maximum cardinality matching) if there is no matching $M^{\prime }$ such that $\left|M^{\prime }\right|>\left|M\right|$. The edge independence number $\alpha_{1}(G)$ of a graph $G$ is the number of edges in a maximum matching. An edge cover $L$ of a simple graph $G$ is a minimum edge cover if there is no edge cover $L^{\prime }$ of $G$ such that $\left|L^{\prime }\right|<\left|L\right|$. The edge-covering number $\beta_{1}(G)$ of the graph is the sum of the number of edges in a minimum edge cover and the number of isolated vertices. Find the edge independence number and the edge-covering number of the graph of Fig. 1-14.

Show that in a simple graph, $\alpha_{1}+\beta_{1}=n$.

A set $F$ of edges in a graph $G=(V, E)$ is a dominating edge set if every edge not in $F$ has a vertex in common with an edge in $F$. The edge domination number $\sigma_{1}(G)$ is the number of edges in a minimum edge domination set. Find the edge domination number of the graph of Fig. 1-14.

Show that the edge domination number cannot exceed the edge independence number.

Find a necessary and sufficient condition to be satisfied by a matching so that it is a dominating edge set.

Find the number of edges in the complete graph with $n$ vertices.

Using techniques from graph theory, show that $1+2+\cdots +n=n(n+1) / 2$.

Show that the number of vertices in a self-complementary graph is either $4 k$ or $4 k+1$, where $k$ is a positive integer.

Find the number of edges in the complete bipartite graph $K_{m, n}$.

Prove Theorem 1.1: The sum of the degrees of a graph is twice the number of edges in it.

Use Theorem 1.1 (the sum of the degrees of a graph is twice the number of edges in it) to find the size of:

Prove Theorem 1.2: Every graph has an even number of odd vertices.

Construct two nonisomorphic simple graphs with six vertices with degrees $1,1,2,2,3$, and 3. Find the size of the graph thus constructed.

Show that if $G$ and $G^{\prime }$ are isomorphic graphs, the degree of each vertex is preserved under the isomorphism.

Show that two graphs $G$ and $G^{\prime }$ with the same set $V=\left\{ 1,2, \ldots , n\right\}$ of vertices such that the degree of vertex $i$ is the same for both the graphs for every $i$ need not be isomorphic.

Prove Theorem 1.3: In a digraph, the sum of the outdegrees of all the vertices is equal to the number of arcs, which is also equal to the sum of the indegrees of all the vertices.

Show that there is no simple graph with 12 vertices and 28 edges in which

Show that there is no simple graph with four vertices such that three vertices have degree 3 and one vertex has degree 1.

A labeled graph with $\boldsymbol {n}$ vertices is obtained by assigning the labels $1,2, \ldots , n$ to the vertices of agiven graph $G$ with $n$ vertices and $m$ edges. Two labeled graphs thus obtained from a given graph $G$ are necessarily isomorphic, but they need not be equivalent. Label the vertices of a simple graph with four vertices of degrees $1,1,1$, and 3, creating three isomorphic graphs $G_{1}, G_{2}$, and $G_{3}$ such that (i) $G_{1}$ and $G_{2}$ are equivalent, and (ii) $G_{1}$ and $G_{3}$ are not equivalent.

Find the number of nonequivalent labeled graphs with $n$ vertices.

Show that the number of vertices in a $k$-regular graph is even if $k$ is odd.

Show that it is not possible to have a group of seven people such that each person in the group knows exactly three other people in the group.

Prove that in any group of six people, there will be either three people who know one another or three people who do not know one another.

The positive integer $n$ has the $(\boldsymbol {p}, \boldsymbol {q})$-Ramsey property if for every graph $G$ with $n$ vertices, either $K_{p}$ is a subgraph of $G$ or $K_{q}$ is a subgraph of the complement of $G$. Show that the positive integer 6 has the $(3,3)$-Ramsey property whereas the positive integer 5 does not.

Show that the following properties are equivalent: (i) the positive integer $n$ has the $(p, q)$-Ramsey property, (ii) every simple graph with $n$ vertices has a clique of $p$ vertices or an independent set of $q$ vertices, and (iii) the edges of $K_{n}$ can be colored using two colors such that there will be either a clique $K_{p}$ in which all edges are of one color or a clique $K_{q}$ in which all edges are of the other color.

The smallest integer $n$ that has the $(p, q)$-Ramsey property is called a Ramsey number, denoted $\boldsymbol {R}(\boldsymbol {p}, \boldsymbol {q})$. Show that:

Show that if a bipartite graph $G=(X, Y, E)$ is regular, both $X$ and $Y$ have the same number of elements.

A cubic graph is simple graph in which the degree of each vertex is 3. Construct two nonisomorphic cubic graphs each with six vertices.

Find the maximum number of edges in a bipartite graph.

The $\boldsymbol {k}$-cube (also known as the hypercube) is the graph $Q_{k}$ whose vertices are the ordered $k$-tuples of binary numbers, two vertices being joined by an edge if and only if they differ exactly in one component. Show that a $k$-cube is a $k$-regular bipartite graph, and find the number of vertices and edges in a $k$-cube.

Find the fewest vertices needed to construct a complete graph with at least 1000 edges.

Show that the vertices of the bipartite graph $G=(X, Y, E)$ with $m$ vertices in $X$ and $n$ vertices in $Y$ can be enumerated so that the adjacency matrix has the form

where $A$ is an $m \times n$ matrix in which each entry is 0 or $1, A^{T}$ is the transpose of $A$, and 0 is a matrix in which each entry is zero.

Prove Theorem 1.4:

Prove Theorem 1.5:

A permutation matrix is a square binary matrix that has exactly one 1 in each row and column. Two matrices $A$ and $A^{\prime }$ are isomorphic if there is a permutation matrix $P$ such that $A^{\prime } P=P A$. Show that two graphs are isomorphic if and only if their adjacency matrices are isomorphic.

Find the adjacency matrices $A$ and $A^{\prime }$ of the two isomorphic graphs given in Fig. 1-18, and obtain a permutation matrix $P$ such that $A^{\prime } P=P A$.

Fig. 1-18

The characteristic polynomial of a simple graph with $n$ vertices is the determinant of the matrix $(A-\lambda I)$, where $A$ is the adjacency matrix and $I$ is the $n \times n$ identity matrix. Show that if two graphs are isomorphic, their characteristic polynomials are the same. (Note: The determinant of $A$ is written $\operatorname {det}\left(A\right)$.)

By computing the characteristic polynomials of the two graphs shown in Fig. 1-19, show that two nonisomorphic graphs can have the same characteristic polynomial.

Fig. 1-19

If $A=\left[a_{i j}\right]$ is the adjacency matrix of a simple graph $G$ with $n$ vertices, the binary code of $G$ with respect to $\boldsymbol {A}$ is the nonnegative integer $a_{12} 2^{0}+a_{13} 2^{1}+\cdots +a_{1 n} 2^{n-1}+a_{23} 2^{n}+\cdots +a_{2 n} 2^{2 n-3}+ \cdots +a_{n-1, n} 2^{k-1}$, where $k=n(n-1) / 2$. Find the binary code of the adjacency matrix of the graph $G=(V, E)$, where $V=\left\{ 1,2,3,4\right\}$ and $E=\left\{ \left\{ 1,2\right\} ,\left\{ 1,4\right\} ,\left\{ 2,4\right\} ,\left\{ 3,4\right\} \right\}$.

Show that it is possible to construct a simple graph $G$ if the binary code of one of its adjacency matrices and the order of $G$ are known.

The minicode of a graph is its smallest binary code, and the largest binary code is the maxicode of the graph. Find the minicode and maxicode of a simple graph with three vertices and two edges.

Prove Theorem 1.6: Let $v=\left[\begin{array}{lllll}d_{1} & d_{2} & d_{3} & \cdots & d_{k}\end{array}\right]$ be a nonincreasing vector of $k$ (where $k$ is at least 2) nonnegative integers such that no component $d_{i}$ exceeds $(k-1)$. Let $v^{\prime }$ be the vector obtained from $v$ by deleting $d_{1}$ and subtracting 1 from each of the next $d_{1}$ components of $v$. Let $v_{1}$ be the nonincreasing vector obtained from $v^{\prime }$ by rearranging its components if necessary. Then $v$ is a graphical vector if and only if $v_{1}$ is a graphical vector.

Prove that the algorithm in Section 1.6 determines whether a given vector of nonnegative integers is a graphical vector.

Test whether $\left[\begin{array}{llllllll}5 & 4 & 3 & 3 & 3 & 3 & 3 & 2\end{array}\right]$ is a graphical vector. If it is graphical, draw a simple graph with this vector as the degree vector.

Test whether $\left[\begin{array}{lllllll}6 & 6 & 5 & 4 & 3 & 3 & 1\end{array}\right]$ graphical.

Let $v=\left[\begin{array}{llll}d_{1} & d_{2} & \cdots & d_{n}\end{array}\right]$ and $w=\left[\begin{array}{lllll}w_{n} & w_{n-1} & \cdots & w_{2} & w_{1}\end{array}\right]$, where $w_{i}=n-1-d_{i}$. Show that $v$ is graphical if and only if $w$ is graphical.

Show that there is no simple graph with six vertices of which the degrees of five vertices are $5,5,3,2$, and 1.

Find $x$ if $\left[\begin{array}{llllllllllll}8 & x & 7 & 6 & 6 & 5 & 4 & 3 & 3 & 1 & 1 & 1\end{array}\right]$ is a graphical vector.

Show that a finite nonincreasing vector in which no two components are equal cannot be a graphical vector.

Show that in a simple graph, there are at least two vertices with equal degrees.

Show that there exists a simple graph with 12 vertices and 28 edges such that the degree of each vertex is either 3 or 5. Draw this graph.

Show that there exists a simple graph with seven vertices and 12 edges such that the degree of each vertex is 2 or 3 or 4.

Find the complements of:

Find the number of nonisomorphic graphs with four vertices and at most 3 edges.

Find the vertex covering number and the independence number of $K_{n}$ and $K_{m, n}$.

Find the vertex dominating number of $K_{n}$ and $K_{m, n}$.

Find the committee number of:

If $I$ is an independent set in a graph, find the subgraph induced by $I$.

Find the maximum number of edges in

It is known that there exists a simple graph with 12 vertices and 28 edges in which the degree of each vertex is either 3 or 5. Find the number of vertices of degree 3.

Find the number of nonequivalent graphs with four vertices and three edges.

Find the number of nonequivalent graphs with five vertices and three edges.

If $G$ is a $k$-regular graph with $n$ vertices, find the number of triangles in $G$ and its complement.

Show that if every edge in a graph joins an odd vertex and an even vertex, the graph is bipartite. Is the converse true?

Any root of the characteristic polynomial of a graph is an eigenvalue of the graph. The spectrum of a graph is the collection of all its eigenvalues. Find the spectrum of:

Find the spectrum of $K_{n}$.

Find the minicode and the maxicode of the simple graph with four vertices such that the degrees of the vertices are $1,2,2$, and 3.

Find the minicode and maxicode of $K_{n}$.