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.

learn more… | top users | synonyms

1
vote
1answer
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 ...
1
vote
1answer
56 views

What is the chromatic index of a complete graph with its edges doubled?

If $G$ is a graph, let $G'$ denote the graph obtained by doubling each edge of $G$. How can I show that $\chi'(G')=2\chi'(G)$? I am considering the two cases when $G$ is a complete graph $K_n$ with $...
1
vote
2answers
170 views

Prove that if $deg (v) > \frac{k}{2}$ for every $v \in V(G)$ then $G$ is Hamitonian.

Let $G$ be a bipartite graph with partite sets $U$ and $W$ such that $|U|=|W|=k \geq 2$. Prove that if $deg (v) > \frac{k}{2}$ for every $v \in V(G)$ then $G$ is Hamitonian. Dirac's theorem : ...
1
vote
1answer
149 views

Problem solving by using Graph Theory

In a group of 9 people, is it possible for every one to know exactly 3 other people in the group? I just learnt a theorem that in any graph G, the number of odd vertices in G is even. Does it ...
1
vote
1answer
69 views

prove that $G$ is complete graph.

suppose that $G$ is connected graph and for every eigenvalue of its adjacency matrix we have $\lambda \geq -1$. prove that $G$ is complete graph. I think that the easiest way is to show that we have ...
1
vote
2answers
198 views

In complete graph, how can I prove ${n\choose 2} = {k\choose 2} + k(n-k) + {n-k\choose 2}$ for $0 \le k \le n$

I'm studying graphs in algorithm and complexity, but I'm not very good at math. How can I prove that ${n\choose 2} = {k\choose 2} + k(n-k) + {n-k\choose 2}$ for $0 \le k \le n$?
1
vote
1answer
35 views

If a graph $G=\left<V,E\right>$ is connected and $\left|E\right|=\left|V\right|$ then there's a circle in $G$

Prove: If a graph, $G =\left<V,E\right>$ is connected and $|E|=|V|$ then there's a cycle in $G$ I think this should be proved by induction. This is certainly holds for $n=1$ (a vertex with a ...
1
vote
1answer
130 views

How many ways can we color a $7$-cycle with $3$ colors so that no three consecutive nodes are of the same color

I have to paint graph We have three colors. The constraint is that there are no three consecutive nodes of the same color. And my idea is: All ways to paint is $3^7$ I'm going to count ...
1
vote
2answers
178 views

Find the number of spanning trees of a dumbbell graph.

A (k, l)-dumbbell graph is obtained by taking a complete graph on k (labeled) nodes and a complete graph on l (labeled) nodes, and connecting them by a single edge. Find the number of spanning trees ...
1
vote
1answer
748 views

Proof of Floyd Cycle Chasing (Tortoise and Hare)

I am looking for a proof of Floyd's cycle chasing algorithm, also referred to as tortoise and hare algorithm. After researching a bit, I found that the proof involves modular arithmetic (which is ...
1
vote
2answers
1k views

Upper and lower bound on graph

Find upper and lower bound for the size of a maximum (largest) independent set of vertices in an n-vertex connected graph, then draw three 8-vertex graphs, one that achieves the lower bound, one that ...
1
vote
4answers
113 views

Notation for two-vertex graph with m edges

Is there standard notation for the graph on two vertices with $m$ edges between them?
1
vote
2answers
763 views

Planar graphs where every face boundary is a cycle of even length are bipartite

Let $G$ be a connected planar graph with a planar embedding where every face boundary is a cycle of even length. Prove that $G$ is bipartite. If every face boundary is a cycle of even length, ...
1
vote
1answer
722 views

Graph with edge disjoint cycles

If the vertices of graph have a degree of at least $n\geq2$, show that the graph has at least $\frac{n}{2}$ edge disjoint cycles. Unsure how to approach this, but I understand that edge disjoint ...
1
vote
3answers
137 views

is MST a Steiner tree?

I am a little bit confused about MST and Steiner tree? Is an MST a steiner tree?? and suppose we are given a weighted undirected connected graph G = (V,E) and S ⊆ V is the smallest subtree of an MST ...
1
vote
2answers
1k views

How many vertices of odd degree are there in $\overline{G}$, the complement of graph G?

Here's the full problem: If a graph $G$ has n vertices (all of which but one have odd degree), how many vertices of odd degree are there in $\overline{G}$, the complement of $G$? So what I ...
1
vote
1answer
77 views

Longest path in directed complete graph

This is a question that I just wondered. I don't know if there's a good answer or not. Given a complete graph of $n$ vertices. Each edge $ab$ is given a direction (either $a\rightarrow b$ or $b\...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
1
vote
1answer
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?
1
vote
2answers
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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?
1
vote
3answers
128 views

How to show that if $G$ is a graph with $\delta (G) \geq 2$ then $G$ contains a cycle?

I know a cycle is a closed trail with no repeated vertices except the first and the last (starts and ends at the same vertex). But I'm not sure how to go about proving this
1
vote
1answer
49 views

Graph G with two Spanning Trees

Let's assume that Graph $G = <V,E>$ has two Spanning Trees $G_a = <V, T_1>$ and $G_b = <V,T_2>$ where $T_1 \cap T_2 = \emptyset$ and $T_1 \cup T_2 = E$. Prove that $\chi(G) \le 4$ $...
1
vote
1answer
39 views

Determine $\chi(S_n)$ and $\chi'(S_n)$, where $S_n$ is the Sierpinski graph of order $n$.

Determine $\chi(S_n)$ and $\chi'(S_n)$, where $S_n$ is the Sierpinski graph of order $n$. Prove this by induction for both $\chi(S_n)$ and $\chi'(S_n)$. I know only about vertex and edge chromatic ...
1
vote
1answer
95 views

Determine a decomposition of the Grötzsch graph into smallest possible number of paths.

Here is the interesting challenge problem from my graph theory professor. Find a decomposition of the Grötzsch graph into smallest possible number of paths. Give a justification why this is as ...
1
vote
3answers
4k views

how can we make 11 non-isomorphic graphs on 4-vertices?

How can we draw all the non-isomorphic graphs on $4$ vertices ? But it is mentioned that $ 11 $ graphs are possible.
1
vote
1answer
104 views

Contraction of loops in matroids

If $M=(E,I)$ is a matroid, and $e$ is not a loop (a loop is an element of the matroid which is not an element of any independent set), we may define the matroid obtained by contracting $e$ to be the ...
1
vote
1answer
237 views

$\chi(G)+\chi(G')\leq n+1$

How to prove, that the sum of chromatic numbers of graph and it's complement is smaller then the number of vertices incremented by one? $\chi(G)+\chi(G')\leq n+1$ The notes from my classes say to ...
1
vote
2answers
105 views

Simple $2$-connected Graph with $\chi(G)=3$

I need to prove that for $G$, a simple $2$-connected graph with chromatic number $\chi(G)=3$, that every $v \in V(G)$ is contained in an odd cycle. Something tells me I need to somehow show that ...
1
vote
1answer
1k views

Show that a regular, connected bipartite graph does not have a bridge.

I need to show, that a connected regular bipartite graph (degree of the graph is $>1$) does not have a bridge. Well let's assume that there is a bridge $e$. After we cut it, the graph is divided ...
1
vote
1answer
486 views

Maximum number of edges in a DAG without transitivity condition

Consider a directed acyclic graph $G(V,E)$ such that no three vertices satisfy the transitivity property. Formally, $$\forall u,v,w \in V, (u,v) \in E \wedge (v,w) \in E \Rightarrow (u,w) \not \in E$$ ...
1
vote
1answer
447 views

Gossip problem why 4?

Each of 10 friends knows some item of gossip not known to the others. They communicate by telephone, and in each call the two friends on the line share everything they have heard thus far. What is the ...
1
vote
2answers
121 views

Check if a graph is Eulerian

Let $G=((2,3,4,5,6,7),E)$ be a graph such that {$x$,$y$} $\in E$ if and only if the product of $x$ and $y$ is even, decide if G is an Eulerian graph. My attempt I tried to plot the graph, this is ...
1
vote
1answer
49 views

A List of Graphs on Small Vertex Sets?

I am preparing for the exam of a first year introductory course on Graph Theory. 50% of the paper unfortunately consists multiple choice questions which are at times tricky. They do not necessarily ...
1
vote
2answers
99 views

Proof - Bipartite Graphs

Let $G$ be an arbitrary, unknown graph with at least two vertices. Suppose you are given the subgraphs in the set $S = \{G - v | v \in V(G)\}$, but the vertices in the subgraphs are not labeled, and ...
1
vote
1answer
1k views

Maximum number of edges in a simple graph?

I found that the maximum number of edges in a simple graph is equal to $$\sum\limits_{i=1}^{n-1} i$$ Where $n =$ number of vertices. For example in a simple graph with $6$ vertices, there can be at ...
1
vote
1answer
102 views

Self-complementary graph problem

For which $n$ from $N$ is $C_{n}$ isomorphic to its complement? Blew my mind, I mean is there even one? I've been trying to find at least one, but I wasn't lucky and I can't even imagine such a ...
1
vote
1answer
135 views

Modified Shortest Path Problem

Consider a directed, weighted graph $G=(V, E)$ where all edge weights are positive. You have one magic star, which lets you traverse one edge of your choice for free. In other words, you may change ...
1
vote
1answer
75 views

2 colour theorem

Take a square and draw a straight line right across it. Draw several more lines in any arrangement so that the lines all cross the square, and the square is divided into several regions. The task is ...
1
vote
1answer
59 views

Is this graph a graceful tree?

Suppose we have a graph $G=(V,E)$ where $V=\{0,1,\ldots,n\}$ and $E$ consists of $n$ edges in such a way that the set of absolute differences $\{|i-j||ij\in E\}$ is exactly the set $\{1,\ldots,n\}$. ...
1
vote
1answer
101 views

Existance of Hamiltonian cycle in the connected graph.

I know the fact, that if a graph is connected and each of its vertices has a degree of $2$, then graph is a cycle graph and it has a Hamiltonian path. From that I easily conclude, that, if graph with ...
1
vote
1answer
514 views

Dilworth's Theorem is equivalent to Hall's

I have been told that Dilworth's Theorem implies Hall's Theorem. I don't seem to be able to show this implication, especially because I haven't done any graph theory in a while! Any help? If possible, ...
1
vote
3answers
680 views

Show the union of two matching is bipartite

Let $G=(V,E)$ be a graph. Let $M1, M2$ be two matchings of $G$. Consider the new graph $G' = (V, M1 ∪ M2)$ (i.e. on the same vertex set, whose edges consist of all the edges that appear in either $M1$...
1
vote
2answers
291 views

bridgeless graph

I need to prove that every graph containing only even vertices is bridgeless. I understand that an even vertex is one with an even degree. Therefore an even vertex is one which is connected to an ...
1
vote
1answer
167 views

What's this graph? (8 vertices, 16 edges)

Let $G = (V,E) =$ f------g |`. |`. | `a--+---b | | | | e---+--h | `. | `. | . `d------c Now let $G' = (V,\, E \cup \{\{a,h\}, \{b,e\}, \{c,f\}, ...