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
148 views

Find a subdivision of K4 in the Grötzsch graph.

It is known that the Grötzsch graph is 4-coloring. Hence it contains a subdivision of K4. But where is this subdivision?
1
vote
1answer
32 views

Find the number of $f: A \to B$ where there is no element in $B$ with $3$ sources

Let $A$ and $B$ be sets such that $|A| = 8$ and $|B| = 5$. Find the number of functions $f: A \rightarrow B$ such that there is no element in b that has 3 sources (that means, for all $b \in B ...
1
vote
2answers
195 views

Proof of bipartite graph formula

I've come across a question that has got be stuck for hours. I need to proof that: Let $G$ be a graph $=(V,E)$, a bipartite graph with $n$ vertices and $e$ edges. Show that $$e\leqslant ...
1
vote
1answer
68 views

3-arc-transitivity of the Odd graphs

The Kneser graph $K_s^{(r)}, (s \ge 2r+1)$ has as its vertex set the $r$-subsets of $\{1,2,\ldots,s\}$, with two vertices being adjacent iff the corresponding subsets are disjoint. An exercise asks ...
1
vote
1answer
111 views

Is one graph ever a subgraph of another?

Let $G$ denote the complete equipartite graph with $p$ partitions and $v$ vertices in each partition; that is, $G:= K_{v,v, \dots ,v}$ where there are $p$ instances of $v$ in the subscript. ...
1
vote
1answer
597 views

Prim's algorithm

Given a connected, directed and weighted graph, Prim's algorithm may not necessarily generate the minimal spanning tree. Suppose we have such a graph $G$ with the special condition that for every pair ...
1
vote
1answer
84 views

Distances between vertices in a graph

Prove $$d(x,z)\le d(x,y)+d(y,z)$$ I did attempt a proof, but I'm not really sure if the reasoning is sound, and I also want to know alternative answers. Let P1=(x,...,y) and P2=(y,...,z) (1)P1 and ...
1
vote
1answer
99 views

Prove / Disprove: If the Residual Graph $G_f$ Contains no Path from $u$ to $v$ then $e$ Crosses Some Minimum Cut

Let $G = (V,E)$ be a flow network. Let $e = (u,v)$ be an edge in $E$ and let $f$ be a maximum flow in $G$. Prove or Disprove: If the residual graph $G_f$ contains no directed path from $u$ to ...
1
vote
1answer
133 views

Minimal spectral radius of a primitive matrix

Given the set of all primitive matrices of dimensions $m$ by $m$ that are non-negative and integer - which one is the matrix with the minimal spectral radius? Edit (according to the first comment): ...
1
vote
1answer
50 views

Given $G = (V,E)$, a planar, connected graph with cycles, Prove: $|E| \leq \frac{s}{s-2}(|V|-2)$. $s$ is the length of smallest cycle

Given $G = (V,E)$, a planar, connected graph with cycles, where the smallest simple cycle is of length $s$. Prove: $|E| \leq \frac{s}{s-2}(|V|-2)$. The first thing I thought about was Euler's ...
1
vote
1answer
104 views

Proof about existence subgraph in graph

I need help with my math problem. Let $G$ be a graph with $n$ nodes and more than $\dfrac{3 (n - 1)}{2} $ links. Show that $G$ contains some $\theta a,b,c$ graph as its subgraph. $\theta a, b, c$ ...
1
vote
1answer
201 views

2-colorable belongs to $\mathsf P$

To show that 2-colorable belongs to $\mathsf P$, I have a straightforward mental description in mind that I don't think will be considered as a formal proof. Hence I am interested to know how this ...
1
vote
1answer
246 views

Anonymous graphs and graph embeddedness

What are anonymous graphs, what is graph embeddedness, and how do they relate to each other? Very confused - I could not find short answer. Thanks.
1
vote
1answer
77 views

Proof is needed for a lower bound of the maximal eigen-value of a non-negative, irreducible, integer matrix

$A$ is a non-negative, integer, irreducible, $m$ by $m$ matrix. It is well known (Perron-Frobenius) that $A$ has a positive eigen value (denote it by $\lambda$) with a positive eigen vector ($x$). It ...
1
vote
1answer
121 views

Prove that the existence of a bridge is an invariant

An invariant is a property $P$ that is shared by all isomorphic graphs. In other words, a property $P$ is an invariant provided that whenever $G_1$ and $G_2$ are isomorphic graphs, if $G_1$ satisfies ...
1
vote
1answer
51 views

Find limits for functions of natural numbers

So I am dealing with some problems about random graphs where we find limits of functions of natural numbers. A simple example can be the limit of $\ln(n)$ as $n \rightarrow \infty$, where $n$ is the ...
1
vote
1answer
56 views

Calculating upper eccentricity in a graph

I was going through a paper. There calculating upper eccentricity was mentioned. Can anybody help me in finding out how it was done? I tried hard but was unable to get it. A little hint or explanation ...
1
vote
1answer
352 views

Weighted directed graph clustering

I had a really huge sets of molecules and it's I'd like to compare according to various factors. So I created a similarity measure which was very informative and fitted for comparing different types ...
1
vote
2answers
267 views

Map-Coloring Problem

When we are faced with map-coloring problem, why do we allow countries that meet at only one point to receive the same color? Is it because they do not share the same boundaries or common boundaries? ...
1
vote
1answer
96 views

to find disconnected graphs

We know that if in a graph $G$, $e$ < $(n -1)$, then the graph is disconnected, where $e$ and $n$ are number of edges and number of vertices resp. Is there any other criteria to find out the ...
1
vote
1answer
98 views

Graph theory problem with friends

There are 9 people and for every 3 people, 2 of them are mutual friends. Please show that there exist 4 people out of the 9 who are all mutual friends.
1
vote
1answer
41 views

Definition of $\mathbb{Z}_2$-periodic graph

I see a definition of a planar, bipartite $\mathbb{Z}_2$-periodic graph, which is a graph can be embedded in the plane, the vertices can be coloured by white and black such that every edges of the ...
1
vote
1answer
1k views

Ranked Preference Matching Algorithm

first dropping the link that will serve as reference: NRMP Residency Matching I have a sort of side project (nothing riding on it, computational performance not an issue, so feel free to go wild, I ...
1
vote
1answer
2k views

How to prove Petersen graph has no Hamiltonian cycle?

How to prove Petersen graph has no Hamiltonian cycle? My working $step \ 1.$ first assume that there exists a cycle. $step \ 2.$ now take a-b-c three continuous node from cycle,than delete node b ...
1
vote
2answers
147 views

Adjacency matrix

Let $G$ be any simple and undirected graph. Let $A$ be the adjacency matrix of $G$. 1) Let $B$ be the number $\tfrac16\mathrm{tr}(A^3)$. What does $B$ count? That is $B$ counts the number of....? 2) ...
1
vote
1answer
47 views

What's the dual graph of the plane graph of order 2 and size 0?

Consider the plane graph consisting of 2 vertices and no edges. It has one face and no edge, so its dual is the trivial graph. On the other hand, it has two vertices, so its dual should have two ...
1
vote
1answer
142 views

Prüfer sequence for an order-2 tree?

All the algorithms for constructing a Prüfer sequence state that the input is a tree, but none give any output corresponding to an order-2 tree. And Wikipedia gives this definition:" A Prüfer ...
1
vote
1answer
69 views

Counting the number of graphs with a certain property

How many simple graphs exist with the property that such a graph $G$ has chromatic number 3, but given any edge $e$ in $G$, $G - e$ has chromatic number 2? Is there some sort of standard criteria to ...
1
vote
1answer
1k views

Topological Sorting in Linear Order for Hasse Diagram

I have come across an exam review question that I am stuck on. The question states: Use topological sort to compute a valid linear order of the elements for the following Hasse Diagram: This is ...
1
vote
1answer
222 views

Union, intersection and difference operations with cycle graphs

I am confused with some graph operations, so would like to clarify some simple questions; If I have below sub graphs (cycles) such as $G_1$, $G_2$, $G_3$ & $G_4$ and if i want to do the union, ...
1
vote
1answer
385 views

What types of questions is graph theory best suited at answering?

I'm dealing with a particular optimization problem at work (financial scorecards), and I noticed that my dataset can be set up as a set of DAGs, where the scorecards for each customer comprise a ...
1
vote
1answer
639 views

How can I tell how many non-isomorphic unrooted trees with 6 edges exists without drawing them all?

Typically my professor asks that we draw them all, but I would like to save some time to confirm how many I need.
1
vote
1answer
313 views

Adjacency matrix defines a distance metric

Let $A$ be adjacency matrix of a graph (perhaps weighted). Prove that \begin{equation} \sum_i \sum_j A_{ij} (f_i- f_j)^2 = \mathbf{f}^T L \mathbf{f} \end{equation} where $\mathbf{f}$ holds values of ...
1
vote
1answer
240 views

Introductory Level Books for Graph Theory

Can anybody please suggest some good introductory level text books on Graph Theory ? Preferably those which don't really require a great pre-requisite background on discrete mathematics, but rather ...
1
vote
1answer
278 views

Algorithm for finding a particular spanning bipartite subgraph

This is an exercise from a book (Bondy/Murty): a) Deduce from Theorem 2.4 that every loopless graph $G$ contains a spanning bipartite subgraph $F$ with $e(F)\geq\frac{1}{2}e(G)$. b) Describe ...
1
vote
1answer
16 views

Graph cover question

Given an undirected connected graph containing k nodes with odd degree (and some more in even degree), I need to show that it's possible to cover the graph's edges with k/2 paths (the paths have no ...
1
vote
1answer
80 views

Calculating a minimum connected subgraph containing a fixed set.

Let $(V,E)$ be a connected, planar graph, and let $S \subset V$ be some desired set of vertices. What is the fastest algorithm, if it exists, to calculate a connected subgraph of $(V,E)$ which ...
1
vote
1answer
395 views

Proving a simple graph is a connected graph

Does any proof exist that a simple graph with $n$ vertices such that the least vertex degree is $\geq \frac{n-1}{2}$ is a connected graph? (i.e. does such a proof have a name?)
1
vote
1answer
180 views

Does the Cycle Property hold when edges values are non distinct?

Will the Cycle Property hold when we have non-distinct edges? It seems like we should still be able to state that some edge will not be part of ANY MST when a connection can be made with smaller ...
1
vote
1answer
323 views

How to generate random graph?

I am new to Graph theory. Please correct me if I am wrong. How do I define the probability of linking nodes to create a random bidirectional network (Erdos Renyi network) with network density of ...
1
vote
1answer
82 views

How do we distinguish “walks” or “paths”?

For example, let $G(V,E)$ be a graph such that $V=\{v_1,v_2\}$ and $E=\{(v_1,v_2)\}$. And let $s_1:\{1,2\}\rightarrow V$ be a walk such that $s_1(1)=v_1$ and $s_1(2)=v_2$. And let ...
1
vote
1answer
216 views

Does *pair* always mean a pair of distinct elements in graph theory?

Definition of edge in wikipedia: An edge of a graph is a set of 2-elements in a set of vertices. Definition of tournament in my text: A tournament is a directed graph such that each pair of vertices ...
1
vote
1answer
362 views

A Problem about friends and strangers using Ramsey's Theory

Question: Consider a group of 8 people, each pair of which are either friends or enemies. Show that if some person in the group has at least 6 friends, then there are 4 people who are mutual friends ...
1
vote
1answer
182 views

High clustering coefficient and large average path length in one graph

Can somebody provide an example of a network with a high clustering coefficient and a large average path length? A visual representation of such a network would be great. No reason for asking, ...
1
vote
2answers
195 views

Triangular graphs

I was learning algorithms and data structures, and can't manage with this problem: We say that a graph is triangular when it is undirected, connected and it's each biconnected component is a cycle ...
1
vote
2answers
114 views

Can a non-simple graph have a complement?

If so, this means that: Two different graphs can share the same complement, however each graph cannot have two different complements. Is this correct?
1
vote
1answer
327 views

Bipartite graphs/ cartesian product

Prove that G and H are bipartite if any only if G x H is bipartite. (G x H denotes cartesian product) I saw someone else asked the same question, but the reply is only a hint on how to solve it. I am ...
1
vote
2answers
128 views

Total Permutation of graph with $n$ vertex?

Given there are $n$ vertex. How to calculate total number of distinct graph having all $n$ vertex. Is there any formula for that? Sorry one correction here: There is one more rule that there should ...
1
vote
1answer
67 views

Part from “Regular polytopes” which I don't understand

This is a paragraph from "Regular polytopes" by Coxeter that I don't understand. Although it is not always possible to include all the vertices of a polyhedron in a single chain of edges, it ...
1
vote
1answer
130 views

Is the number of path exponential to the number of state in acyclic Kripke structure?

Given an acyclic kripke structure, is the number of possible paths (path that start from initial state and ends in final state) exponential to the number of states? If yes, what is the simple argument ...