Combinatorics -- Graphs

63 Views Asked by At

I need to construct a graph that has the following properties: the vertices of G are the edges of a complete graph $K_5$ on 5 vertices. The vertices of G are adjacent if and only if the corresponding edges of $K_5$ have an endpoint in common. I then need to determine the chromatic number of this graph.

Can someone help me with at least the construction of the graph?

1

There are 1 best solutions below

6
On

I'm not sure what you're looking for, where the construction is concerned; it is fairly explicit. But, let me try to rephrase a little bit, and perhaps that will help.

We start off with $K_5$; to make things precise, let's say that $K_5$ has vertex set $\{1,2,3,4,5\}$, and the edges of $K_5$ are all pairs $\{i,j\}$ where $i,j\in \{1,2,3,4,5\}$ and $i\neq j$.

So, the VERTEX set of your new graph should be $$ V=\{\{1,2\},\{1,3\},\{1,4\},\{1,5\},\{2,3\},\{2,4\},\{2,5\},\{3,4\},\{3,5\},\{4,5\}\}; $$ the edge set consists of all pairs $e,f\in V$ such that $e\neq f$ and $e\cap f\neq\varnothing$. So, for instance, there is an edge connecting $\{1,2\}$ and $\{2,3\}$, but not connecting $\{1,2\}$ and $\{3,4\}$.

Does that help?