# Tagged Questions

Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

46 views

### how we can understand from spectrum of laplacian matrix of a graph that this graph is regular or not .

how we can understand from spectrum of laplacian matrix of a graph that this graph is regular or not . if we consider $0=\mu_1 \leq \mu_2 \leq ...\leq \mu_n$ as the eigenvalue of laplacian matrix ,we ...
56 views

154 views

### Piping three circles to three squares

How I can prove the impossibility of joining three circles to three squares with non-intersecting lines (not strictly straight). Shapes of squares and circles are only representative. Each circle ...
57 views

### Graph-like problem

Each shop in a town has an odd number of customers and each pair of shops shares an even number of customers. Prove that there are at least as many customers as there are shops. Any hints are ...
855 views

### bipartite graph vs. directed acyclic graph

I'm having a hard time understanding the fundamental differences between a directed acyclic graph and a bipartite graph. Can anyone see how they are different from a mathematics perspective (or data ...
55 views

### Calculating Total Number of Possible 4-Colorings of a Graph

I recently met with a professor to discuss this problem and she didn't have an answer for how to do the calculation. What I did learn is that the counting itself is considered NP-Hard and is in a ...
144 views

### Chromatic polynomial of a graph - might take a while

I'm currently struggling with graphs that require either adding edges, or removing them. Problem here being that the graphs I'm working on takes forever to complete and I don't really know if adding ...
148 views

### In graph theory, are undirected graphs assumed to be reflexive?

In graph theory, are undirected graphs assumed to be reflexive? I know that in directed graphs vertices do not point to themselves unless explicitly stated, but what about undirected graphs?
344 views

### number of edges in the complement of a complete bipartite graph as a function of $n$, the toal number of verticies

Consider any complete bipartite graph $K_{p,q}$. Express the number of edges in $K_{p,q}^C$, the complement of $K_{p,q}$, as a function of $n$, the total number of verticies. Now, I know that I ...
201 views

### drawable graph theory

What are all the tricks that make a graph drawable? I know that a graph is drawable when you can draw the graph without lifting your pen off the paper and without retracing any edges. I know that if ...
42 views

### Does there exist a big graph with that property?

Does there exist a graph with the chromatic number greater than $2013$ and all the cycles of length greater than $2013$ too?