The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+3 votes
A graph consists  of only one vertex,which is isolated ..Is that graph

A) a complete graph ???

B) a clique???

C) connected graph ???

Please explain your answer ...
in Graph Theory by Loyal (7.7k points) | 411 views

3 Answers

+3 votes

A) Definitely a complete graph because a graph having one vertex is trivial and hence implicitly complete.

B) Yes it is a clique because the vertex forms subgraph of the graph itself and as the subgraph is complete trivially, it is a clique. Please note that C ⊆ V denotes that C is subset of V and not PROPER subset of V hence both C and V contains the single Vertex.

C) Yes it is connected as well. Because a graph having one vertex is implicitly connected. 

by (369 points)
0 votes

It's not a complete graph because property of a complete graph is

Kn has n(n − 1)/2 edges (a triangular number), and is a regular graph of degree n − 1.

here n=1 so 1*(1-1)/2 is not defined so it is not a complete graph

It's not clique because the definition of clique is

cliqueC, in an undirected graph G = (VE) is a subset of the vertices, C ⊆ V, such that every two distinct vertices are adjacent. This is equivalent to the condition that the induced subgraph of G induced by C is a complete graph. In some cases, the term clique may also refer to the subgraph directly.

there is no subgraph in given graph which is complete

It's not connected graph because according to definition a graph should have atleast two vertices to show it is connected or not

Defination: A graph is connected when there is a path between every pair of vertices

in the question it is only mentioned that there is one vertex 

by Active (3.4k points)

Why is this 1*(1-1)/2 not defined ? Number of edges is zero. Single vertex graph is definitely complete.

C ⊆ V means that C is subset (not proper subset) of V. Hence in our case C = V and hence it can form a clique. 

A graph is connected when there is a path between every pair of vertices (Only when there are 2 or more vertices). Single vertex does not require the condition of edge being present.

absolutely right.
0 votes
According to defination, All three are correct.

Related questions

0 votes
1 answer
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,362 questions
55,786 answers
90,919 users