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
2answers
20 views

Prove:Graph in which every pair of vertices has an odd number of common neighbors is Eulerian.

Let G be a graph in which every pair of vertices has an odd number of common neighbors. Prove that G is Eulerian. I have in mind two main ways to prove this but every time i get stuck . 1) get a ...
-1
votes
1answer
37 views

Graph theory and tree company

I appreciate anyone who answer this question and I anyone who design appropriate graph.
0
votes
1answer
19 views

suppose a graph $G$ is 3-regular with bridge (cut edge),do we have $\chi^{'}(G)=4$?

suppose a graph $G$ is 3-regular with bridge (cut edge),do we have $\chi^{'}(G)=4$? I think that it is right but I couldn't prove it,can you give me some hint or guidance about it,thanks a lot.
0
votes
0answers
11 views

Minimum weight vertex cover test set

I want to test the efficiency of an approximate algorithm for finding the minimum weight vertex cover. Is there an online test suite that contains weighted graphs with known vertex covers? If not, ...
0
votes
1answer
29 views

Existence of a maximum matching containing a vertex $v$ in a graph

Let $v$ be a vertex of a graph $G$, which is not isolated. Prove the existence of a maximum matching in which $v$ is saturated (matched).
1
vote
1answer
18 views

an example for an arbitrary graph $G$ with even vertices which $\forall S \in V(G) , |N(S)|\geq |S| $ but there is no complete matching .

I want to say an example for an arbitrary graph $G$ with even vertices which $\forall S \in V(G) , |N(S)|\geq |S| $ but there is no complete matching . I have tried so many shapes but I couldn't ...
3
votes
1answer
25 views

Number of edges in a graph with n vertices and k connected components

Let $m$ be te number of edges, $n$ the number of vertices and $k$ the number of connected components of a graph G. Prove that: $m$ $\leq$ $\frac{(n-k+1)*(n-k)}{2}$ Thanks!
1
vote
0answers
12 views

Deviation of number of cycles of length 4 in Erdős–Rényi random graphs.

I'm working on my homework and can't find any relevant information for this problem. Problem: Let $G(n, p)$ be Erdős–Rényi random graph. I need to find deviation of number of cycles of length 4 in ...
1
vote
1answer
20 views

Triangles formed by line segments in a square

There is a square, denoted by points A, B, C, and D. There are 30 distinct points located inside the square (call these $A_2, A_3, A_4, ... A_{31}$. Non-intersecting segments $A_iA_j$ vertices are ...
4
votes
4answers
156 views

Triangle-free graph with 5 vertices

What is the maximum number of edges in a triangle-free graph on 5 vertices? No answers, please...just hints. I believe that E $\leq$ 5, but I'm not sure where to go from there.
5
votes
1answer
43 views

all possible values of vertices, given the number of faces and all the vertices have the same degree on a connected planar graph?

A connected planar graph has 26 faces and an unknown amount of vertices (denoted as "V"). All the vertices have the same degree. What are all possible values of V? What I have so far: V + F = E + ...
-1
votes
1answer
65 views

Check if Sequence is Graphic: 8, 8, 7, 7, 6, 6, 4, 3, 2, 1, 1, 1 [duplicate]

This is part of my Discrete Math homework and I have no idea how to solve this. I am given this sequence: $8, 8, 7, 7, 6, 6, 4, 3, 2, 1, 1, 1 $ I have to check whether it is graphic or not. How do ...
3
votes
0answers
58 views

a problem about finding an algorithm for a spanning tree in a 3-regular graph

"Consider the connected 3-regular graph G. Find an algorithm that produces a subgraph S of G which is a spanning tree and if you remove S from G then G is divided into some components that each of ...
0
votes
0answers
19 views

Graph Theory with Homology Diagram

In homological algebra we end up playing around with diagrams a lot. For example, when we prove that a whole diagram commutes (like a chain map between two chain complexes) we simply prove that each ...
1
vote
1answer
38 views

What is $\tau(A)$ of components of $G \backslash A$, where $A \subseteq V$?

A graph is $t$-tough if for all cutsets $A$ we have : definition of t-tough can be found here http://personal.stevens.edu/~dbauer/pdf/dmn04f6.pdf Now I am reading a paper which author defines ...
0
votes
3answers
56 views

How many ways to make a connected graph using 4, 5, 6 edges?

How can/how many ways can you make a connected graph that has 5 vertices using 4, 5, 6 edges? I'm not sure how it would look like for 4 edges. Can you draw a diagram?
1
vote
0answers
17 views

Inequality to bound $\sum_i a_i b_i - \sum_i c_i d_i$ (harmonic eigenfunction/graph) type sum with constraints

We have a homogeneous graph $G = (V,E)$ with a function $f:V\rightarrow \mathbb{R}$. We define the following modulus: $\displaystyle \omega(s) = \sup\{f(x)-f(y) \ | \ |x-y|=s \}$ and wish to lower ...
2
votes
0answers
31 views

Is there a name for this class of graphs?

Consider the graphs $G=(V,E)$ where there exists a non-empty $S \subseteq V$ such that $G[S]$ is a complete subgraph and every possible edge between $S$ and $V\setminus S$ is present in $G$. ...
1
vote
1answer
51 views

Induction and basic assumptions in Graph Theory

I am beginning to work through a text in graph theory and have a couple of questions. 1) Can we always assume a graph is nonempty, i.e., if a graph $G$ has order $n$, do we assume $n\in \{1,2,...\}$? ...
0
votes
1answer
18 views

Weakly Connected Graphs

How is the following graph a weakly connected graph?
0
votes
1answer
21 views

Create a map of connected nodes from a list of edges in $O(n^2)$

I have a directed graph. It may or may not be a DAG. I would like to create a map in $O(n^2)$ time to find all nodes that are accessible from a node on a directed path, where $n$ is number of ...
1
vote
0answers
12 views

Which are the best book for doing a project on graph theory, exspecially the topic spanning trees and its applications? [on hold]

I want the best reference books in post graduate level or high. Can any one help me to select a book?
0
votes
0answers
20 views

How to formalize a lattice in a graph

Given directed a graph: G = (V, E). How to use algebra symbols to express a lattice in G? where reachability stands for partial order, i.e. in the lattice ...
1
vote
1answer
17 views

Could you expand a little on this proof or Floyd-Warshall Algorithm?

I'm reading this. $\quad$ He gives a proof of Floyd-Warshall's algorithm but I don't understand what he's doing nor why it proves that. I can see an intuitive proof in my mind that is as ...
2
votes
1answer
22 views

What's the meaning of “reuse space”?

I'm reading this. $\quad \;\;$ What's the meaning of reuse space in here?
3
votes
0answers
24 views

How is a part of eulerian path called?

An eulerian path in a graph is a path that visits every edge in the graph exactly once. If there is a path that has a similar property that it visits an edge at most once (e.g. a part of an eulerian ...
0
votes
0answers
25 views

Questions on Graph Theory:

Prove: Every collection of 6 people contains a group of 3 friends or a group of 3 strangers. The shortest closed walk is a cycle. (Don't have any idea how I will solve the first statement. For the ...
1
vote
1answer
12 views

Planar representation of a planar bipartite graph

I can't understand the following : In the planar representation of a planar bipartite graph ,each region is bordered by atleast 4-edge curves . Kindly help me with this..
2
votes
1answer
30 views

If a graph has order 99 then it has a vertex of even degree .

How should I show the following: If a graph has order $99$ , then show that it has a vertex of even degree. I don't get how to prove it, maybe we need the use of fact that the sum of all ...
4
votes
1answer
56 views

Every simple planar graph with $\delta\geq 3$ has an adjacent pair with $deg(u)+deg(v)\leq 13$

Claim: Every simple planar graph with minimum degree at least three has an edge $uv$ such that $deg(u) + deg(v)\leq 13$. Furthermore, there exists an example showing that 13 cannot be replaced by ...
1
vote
0answers
33 views

Counting simple, connected, labeled graphs with N vertices and K edges

Given the number of vertices $n$ and the number of edges $k$, I need to calculate the number of possible non-isomorphic, simple, connected, labelled graphs. My question is very similar to this one. ...
0
votes
1answer
16 views

isoperimetric inequalities in permutohedron

Consider the graph whose vertices are all n! permutations of numbers 1..n and there is an edge between two vertices iff we can get from one to another by an adjacent transposition. We call this graph ...
3
votes
3answers
48 views

Proof on Graph Theory.

If G is a connected planar graph, then G has a vertex of degree at most 5. Any planar graph can be colored with 5/6 colors. Any tree has atleast one leaf. Solutions: Although I've read a lot on ...
3
votes
2answers
37 views

Edges between two parts of graph

Consider a (simple undirected) graph $G$ with set of vertices $V=A\cup B$ with $|B|=30$. (1) Every vertex in $A$ has an edge to exactly $3$ vertices in $B$. (2) Every vertex in $B$ has an edge to ...
1
vote
2answers
19 views

Can a K1 graph be a maximal clique of a graph?

I had a discussion with my teacher, whether $K_1$, the complete graph on a single vertex, can be a maximal clique of a given graph. I was notified that it couldn't be a maximal clique, because $K_1$ ...
1
vote
1answer
17 views

How does $\mathcal{A}\cup \mathcal{B}$ indicates that there is at least one augmenting path on $\mathcal{A}$?

I had an exam and there was the following question: $\mathcal{A}$ and $\mathcal{B}$ are matchings in a graph $G$, with $|\mathcal{A}|< |\mathcal{B}|$, study the graph formed with the edges of ...
1
vote
1answer
20 views

Example showing ,for a given graph G , spanning trees need not be unique

The following question appeared in my examination : Give an example to show that for a given graph G , spanning trees need not be unique . but I was unable to construct an example for this ...
5
votes
1answer
55 views

Max flow min cut from duality

I have been having some trouble deriving the max flow min cut theorem from duality, which I was told is possible. To begin with, I need to cast the problem into the form "maximize $\langle c, ...
10
votes
4answers
167 views

How many “good” graphs of size $n$ are there?

Let's a call a directed simple graph $G$ on $n$ labelled vertices good if every vertex has outdegree 1 and, when considered as if it were undirected, it is connected. How many good graphs of size $n$ ...
0
votes
0answers
22 views

unique cycles in strongly connected labeled digraphs.

Define a "characterizing cycle" as a cycle in a labeled digraph, along with a distinguished node, such that the sequence of labels starting from that node is unique to that cycle and node. Note: the ...
0
votes
1answer
29 views

Minimal cuts in network.

Let $(S_1, \overline{S_1} ) , (S_2, \overline{S_2} )$ be minimum cuts in some network. Thesis: The $(S_1 \cap S_2, \overline{S_1 \cap S_2)}$ is minimum cuts in this network. Thesis is true? Why? I ...
0
votes
1answer
36 views

Is it possible to apply properties of nodes in a graph to its edges?

I have a graph whose vertices represent points in geometric space. The edges of this graph represent line segments between various points. Is it possible to assign a direction to an edge based on ...
2
votes
0answers
33 views

Sizes of Hamming balls on the discrete torus

Consider the discrete torus $\mathbb Z^2_k $, with $k$ even, i.e. the graph with vertex set $\{0,1,\dots, k-1\} \times \{0,1,\dots, k-1\}$ and edges between any pair of vertices which differ in ...
3
votes
1answer
21 views

How many subgraphs of $K_{m,n}$ are there that contain m + n vertices?

In this problem, a subgraph of $G = (V,E)$ is given by $G' = (V', E')$ where $V' \subset V$ and $E'$ is subset of edges of $E$ that connect two vertices in $V'$. How many subgraphs of $K_{m,n}$ are ...
1
vote
1answer
33 views

Counting the number of unicyclic graphs

Could you help me giving me the number of unicyclic graphs with k vertices and k edges ? I remind that a unicyclic graph with k vertices and k edges is a tree with k vertices and k-1 edges to wich we ...
1
vote
1answer
20 views

Directed Multigraph or Directed Simple Graph?

I have the following two questions in my book: Question # 1 Determine whether the graph shown has directed or undirected edges, whether it has multiple edges, and whether it has one or more ...
0
votes
1answer
29 views

Finding representation matrix of $M$*$(K_5)$ above $\mathbb F_2$

Finding representation matrix of $M$*$(K_5)$ above $\mathbb F_2$. $M$*$(K_5)$ is the dual matroid representing the graph $K_5$, that is, a complete graph with 5 vertices. How do I solve this? ...
5
votes
1answer
49 views

Special case of Minimum Spanning Tree

I have been bashing my head trying to solve the following problem for the past two days, it is a review question in preparation for my exam and I assume something similar will be on it. The problem ...
-3
votes
0answers
42 views

What is the chromatic number of $G_1 \cup G_2$? [closed]

Please give me some advice. Let $G=G_1 \cup G_2$ where $V_1 \cap V_2 = \emptyset$. Prove that: $$\chi(G) \le \chi(G_1)\chi(G_2).$$
0
votes
1answer
28 views

Extension of hypercube

I understand the notion of a hypercube as a graph with vertex set $\{0,1\}^{n}$ and an edge between two vertices if their vertices differ in one co-ordinate is there an extensive body of work on the ...