Question

The line graph \(L(G)\) of a simple graph \(G\) is the graph whose vertices are in one-one correspondence with the edges of \(G\), with two vertices of \(L(G)\) being adjacent if and only if the corresponding edges of \(G\) are adjacent. (i) Show that \(K_{3}\) and \(K_{1,3}\) have the same line graph. (ii) Show that the line graph of the tetrahedron graph is the octahedron graph. (iii) Prove that, if \(G\) is regular of degree \(k\), then \(L(G)\) is regular of degree \(2 k-2\). (iv) Find an expression for the number of edges of \(L(G)\) in terms of the degrees of the vertices of \(G\). (v) Show that \(L\left(K_{5}\right)\) is the complement of the Petersen graph.

Short answer

The line graphs for \(K_3\) and \(K_{1,3}\) are isomorphic. The line graph of a Tetrahedron is an Octahedron. If \(G\) is a regular graph with degree \(k\), \(L(G)\) would be regular of degree \(2k-2\). The number of edges of \(L(G)\) is half the sum of vertices degrees. \(L(K_5)\) is the complement of Petersen graph.

Step-by-step solution

Part I Solution: Compare Line Graphs \(L(K_3)\) and \(L(K_{1,3})\)

Both \(K_3\) and \(K_{1,3}\) have 3 edges, hence, their line graphs will both have 3 vertices. There isn't any adjacent edge in \(K_3\) and \(K_{1,3}\), so there wouldn't be any edges in \(L(K_3)\) and \(L(K_{1,3})\) either. Hence, \(L(K_3)\) and \(L(K_{1,3})\) are isomorphic.

Part II Solution: Tetrahedron and Octahedron Line Graphs

A Tetrahedron graph has 4 vertices and 6 edges. Its line graph would have 6 vertices. An Octahedron graph also has 6 vertices. As each pair of edges in Tetrahedron graph shares a common endpoint, the line graph will be a complete graph, which is same as the Octahedron graph. Therefore, line graph of Tetrahedron graph is the Octahedron graph.

Part III Solution: Degree of Vertices Proof

For a regular graph of degree \(k\), each vertex is adjacent to \(k\) others. Therefore, each edge of \(G\) is adjacent to \(2k-2\) others. This implies that each vertex in \(L(G)\), which corresponds to an edge in \(G\), has degree \(2k-2\). Hence, \(L(G)\) is regular of degree \(2k-2\).

Part IV Solution: Express Number of Edges

Each vertex in \(L(G)\) corresponds to an edge in \(G\), and is adjacent to the vertices corresponding to edges adjacent to its edge in \(G\). This implies that the number of edges of \(L(G)\) is half the sum of the degrees of vertices in \(G\). Hence, the required expression is \(\frac{1}{2}\sum degrees\).

Part V Solution: \(L(K_5)\) and Petersen Graph Complement

\(K_5\) is a complete graph with 5 vertices and each vertex is connected to 4 other vertices. Hence \(L(K_5)\) is regular of degree 4x2-2=6. The Petersen graph has 10 vertices and is 3-regular. Its complement will also have 10 vertices, and being a complement of a 3-regular graph, it will have degree 10-3-1=6. Hence, \(L(K_5)\) and the complement of the Petersen graph are both 10-vertex, 6-regular graphs. As there is only one such graph, \(L(K_5)\) is indeed the complement of the Petersen graph.

Key concepts

Graph Theory

Graph theory is a branch of mathematics that studies the properties and applications of graphs, which are structures made up of nodes (also called vertices) connected by edges. This field of study is fundamental in various areas such as computer science, biology, and social science, where it can be applied to model networks, pathways, and relationships.

With graphs, we can represent and solve complex problems like finding the shortest path between two points, determining the most efficient routing for deliveries, or even analyzing social networks to identify influential individuals. Graphs come in various forms, including simple graphs, directed graphs, weighted graphs, and others.

One intriguing aspect covered in graph theory is the transformation of a given graph into its line graph. This concept resonates well with the exercise at hand, where the properties of line graphs are explored extensively. A line graph essentially builds a bridge between the edges of the original graph, turning these edges into nodes and connecting them if they share a common node in the original graph.

Graph Isomorphism

Graph isomorphism is the concept of equivalency between two graphs. Two graphs are said to be isomorphic if there is a one-to-one correspondence between their vertices that preserves the adjacency of the vertices. That is, if there is a way to 'relabel' the vertices of one graph to match the other in such a way that the structure of connections remains unchanged, the graphs are isomorphic.

This concept was illustrated in the exercise when showing that the line graphs of two different graphs, namely the complete graph on three vertices (\(K_3\)) and the star graph with three edges (\(K_{1,3}\)), are actually the same graph. Despite the original graphs being different, their line graphs, which represent the interconnectedness of edges, are indistinguishable in structure and hence, isomorphic.

Regular Graph

A regular graph is a graph where each vertex has the same number of neighbors; in other words, every vertex has the same degree. The degree of a vertex is defined as the number of edges incident to it. Regular graphs are particularly interesting due to their balanced structure and often exhibit symmetrical properties.

For instance, the exercise demonstrated a property of regular graphs in the context of their line graphs. If a graph is regular of degree k, then each of its edges is connected to certain other edges. Specifically, the line graph of such a regular graph will itself be a regular graph with vertices of degree \(2k - 2\). This predictable pattern is essential when analyzing the structure of networks and designing algorithms.

Graph Complement

The graph complement is a transformation that takes a graph and produces another graph on the same vertex set where two vertices are adjacent in the complement if and only if they are not adjacent in the original graph. It's like flipping the presence of edges: where there was an edge, there now is none, and vice versa. The concept of the complement is noteworthy when discussing properties of graphs and their relationships.

In the context of the exercise, we discuss the graph complement of the well-known Petersen graph. While the Petersen graph itself is 3-regular, its complement will have edges that the Petersen graph lacks, making it fully interconnected except for the edges that were originally there, indicating a different sort of regularity. The exercise concludes with showing that the line graph of the complete graph on five vertices (\(L(K_5)\) is actually the complement of the Petersen graph, showcasing a neat crossover of these graph properties.