Graph in discrete math

Question

i) What is a graph?

ii) Draw a simple graph with 6 vertices and 7 edges?

iii) What is the degree of a vertice in graphs?

iv) What is a complete graph?

v) Find the number of edges of a complete graph if it has 16 vertices.

Answer 1

Hi Xamid!

i) A graph, by definition, is two sets: a set of Vertices (or nodes), and a set of unordered pairs of vertices that represent Edges.

ii) To create a simple graph with 6 vertices and 7 edges, start by drawing 6 dots on a piece of paper. These are your 6 vertices, and they can go anywhere you want them! When you connect two of these dots with a line, you have created an edge, so you'll have to create 7 edges in that manner. The only rules you need to follow to keep the graph simple is that a vertex cannot be connected to itself (no loops!) and once two vertices are connected, you cannot connect them with a second edge.

iii) The degree of a vertex is the number of edges that are connected to it. Pick a vertex, and then count how many edges you see coming out of it to find its degree.

iv) A complete graph is a graph where every single possible edge is drawn. That means that every vertex is connected by an edge to every other vertex.

v) The graph has 16 vertices. Vertex A must connect to the other 15 vertices. Vertex B must also connect to the other 15, but since we already connected it to A, it only has 14 left to connect with. Following this pattern, we would find the answer to be: 15 + 14 + 13 + 12 + .... + 2 + 1.

Theres a shortcut though! To find the sum up of numbers from 1 to n, you can use the formula 1/2*n(n-1). In our case, n = 15, so 1/2 * 15 * (15-1) = 105 edges.

Hope this helps!