5.2: Properties of Graphs
- Page ID
- 88869
Definitions of Graph Properties
Two vertices, \(v_i\) and \(v_j,\) in a graph \(G\) are adjacent if and only if \(\{v_i,v_j\}\) is an edge in \(G.\)
Vertices A and B are adjacent in the graph in Figure \(\PageIndex{11}\) because \(\{A,B\}\) is an edge.
Two edges in a graph \(G\) are incident if and only if they share a vertex.
Edges \(\{A,B\}\) and \(\{B,G\}\) are incident in the graph in Figure \(\PageIndex{11}\) because they share vertex B.
A vertex \(v\) and an edge \(e=\{v_i,v_j\}\) in a graph \(G\) are incident if and only if \(v \in e.\)
Vertex A is incident with edge \(\{A,B\}\) in the graph in Figure \(\PageIndex{11}\), that is, A is in the edge.
The degree of a vertex \(v\) is the number of edges incident with \(v.\)
Vertex A in the graph in Figure \(\PageIndex{11}\) has degree 4, because \(\{A,B\}\text{,}\) \(\{A,L\}\text{,}\) \(\{A,K\}\text{,}\) and \(\{A,F\}\) are edges incident with it.
The minimum degree of all vertices in a graph \(G\) is denoted \(\delta(G)\) and the maximum degree of all vertices in a graph \(G\) is denoted \(\Delta(G).\)
A graph \(G\) is regular if and only if the degree of all vertices are the same.
Figure \(\PageIndex{11}\) shows a regular graph.
A graph \(G\) is a complete graph, denoted \(K_n,\) if and only if \(\{v_i,v_j\} \in E\) for all \(i \ne j.\)
Figure \(\PageIndex{13}\) shows the complete graph, \(K_5\text{.}\)
Note the size of a graph or subgraph is the number of vertices. Thus \(K_5\) has size 5.
A subset \(A\) of vertices in a graph are independent if and only if no pair of vertices in \(A\) are adjacent.
\(A,C,E\) is an independent set for the graph in Figure 5.2.11. Note no edge contains any two of these vertices.
A graph \(G\) is bipartite if and only if the vertices can be partitioned into two sets such that no two vertices in the same partition are adjacent.
This video shows how to demonstrate a graph is bipartite.
This video shows how to determine if a graph is bipartite.
This video shows how to demonstrate a graph is not bipartite.
If each vertex in any partition of a bipartite graph is adjacent to all vertices in the other partition, the graph is called complete bipartite and is denoted \(K_{n,m}\) where \(n,m\) are the sizes of the partitions.
The third graph in Figure 5.2.44 is a complete bipartite graph.
A graph \(H=(V_H,E_H)\) is a subgraph of a graph \(G=(V_G,E_G)\) if and only if \(V_H \subseteq V_G\) and \(E_H \subseteq E_G.\)
The graph with vertex set \(V_H=\{A,B,C,G,L\}\) and edge set \(E=\{\{A,B\}, \{A,L\}, \{L,G\}, \{B,C\}, \{C,G\} \}\) is a subgraph of the graph in Figure \(\PageIndex{11}\)
A graph \(H=(V_H,E_H)\) is an induced subgraph of a graph \(G=(V_G,E_G)\) if and only if \(V_H \subseteq V_G\) and \(E_H=\{(v_1,v_2) \in E_G : v_1,v_2 \in V_H\}\) (the set of all edges from \(G\) using only vertices in \(H\)).
The graph with vertex set \(V_H=\{A,B,C,G,L\}\) and edge set \(E=\{\{A,B\}, \{A,L\}, \{B,L\}, \{B,G\}, \{L,G\}, \{B,C\}, \{C,G\} \}\) is the subgraph of the graph in Figure \(\PageIndex{11}\) induced by \(V_H\text{.}\)
The complement of a graph \(G=(V,E)\) is the graph \(H=(V,E_2)\) such that \(v_1,v_2\) are adjacent in \(H\) if and only if they are not adjacent in \(G.\)
The dual of a graph \(G=(V,E)\) is the graph \(H=(E,E_2)\) such that for two vertices (edges of \(G\)) are adjacent if they were incident in \(G.\)
Practice
Checkpoint \(\PageIndex{29}\)
List the minimum and maximum degree of every graph in Figure \(\PageIndex{43}\)
Determine which graphs in Figure \(\PageIndex{43}\) are regular.
Complete graphs are also known as cliques. The complete graph on five vertices, \(K_5,\) is shown in Figure \(\PageIndex{14}\). The size of the largest clique that is a subgraph of a graph \(G\) is called the clique number, denoted \(\Omega(G).\)
Checkpoint \(\PageIndex{31}\)
Find \(\Omega(G)\) for every graph in Figure \(\PageIndex{43}\)
Checkpoint \(\PageIndex{32}\)
Prove that a complete graph is regular.
Checkpoint \(\PageIndex{33}\)
Draw a graph with at least five vertices. Calculate the degree of each vertex. Add these degrees. Count the number of edges. Compare the sum of the degrees to the number of edges. Add an edge. Repeat the experiment. Conjecture a relationship.
Checkpoint \(\PageIndex{34}\)
After the class confirms the result above prove that the number of vertices of odd degree is even.
The size of the maximum independent set in a graph \(G\) is denoted \(\alpha(G).\)
Checkpoint \(\PageIndex{35}\)
Find \(\alpha(G)\) for every graph in Figure \(\PageIndex{43}\)
Checkpoint \(\PageIndex{36}\)
Re-write the definition of independent set exchanging vertices for edges. Note this is called a matching.
Checkpoint \(\PageIndex{37}\)
Find the size of the maximum matching for each graph in Figure \(\PageIndex{43}\)
Checkpoint \(\PageIndex{38}\)
Determine which graphs in Figure \(\PageIndex{43}\) are bipartite.
Checkpoint \(\PageIndex{39}\)
Write a definition for tripartite graphs.
Checkpoint \(\PageIndex{40}\)
Construct the graph complement of the bottom left graph in Figure \(\PageIndex{44}\)
Checkpoint \(\PageIndex{41}\)
Construct the graph complement of \(K_4\).
Checkpoint \(\PageIndex{42}\)
Construct the dual graph of the bottom left graph in Figure 5.1.1.
