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

2
votes
2answers
95 views

Is there an appropriate labeling for the colored graph

Motivation: For those of you who care to know, I thought about this question after looking at this question. Let $X=\{1,2,\dots,N\}$, and let $f:X\to X$ be a bijection. We define the two-colored ...
2
votes
1answer
204 views

Planar Graph with Maximum Number of Edges and 3-Colouring in Eulerian

Show that a planar graph with $n$ vertices and $3n-6$ edges with $\chi=3$ is Eulerian. $\chi=3$ means there is a optimal vertex colouring with three colours. Eulerian means that the graph admits ...
7
votes
1answer
112 views

Universal properties of “interesting” families of graphs

Can cycles – and/or other "interesting" families of graphs like paths, trees, hypercubes, etc. – be characterized by a universal property in the category of graphs? I admit that there is ...
1
vote
0answers
73 views

automorphism group of connected cubic symmetric graph

I want to cumpute |Aut(X)| when X be a connected cubic symmetric graph. Let X be a connected cubic symmetric graph. Automorphism group of X act on vertex set, V(X). Let u be a vertex of X.We know ...
1
vote
2answers
828 views

Variations : Anti-Symmetric Relations on an $n$-Element Set : Graph Theoretic Elucidation

Question: How many antisymmetric relations are there on an $n$-element set? Guess: I suspect that there are $2^n$ such relations. Discussion: I'm told that anti-symmetric relations on a ...
2
votes
2answers
207 views

universal graph

Show that there doesn't exist a (countable) universal graph for each of the following classes of graphs (that is, no universal graph for class 1, and unrelatedly, no universal graph for class 2): ...
1
vote
0answers
50 views

Fixed Length Cycle Search

I am given a list of $0 \le M \le 2n(n-1) $ edges of a graph. My goal is to find a connected subgraph of this graph such that the degree of every vertex in the subgraph is $n$ that has exactly $n$ ...
1
vote
0answers
27 views

Union of preimages of edge coloring

Let $G=(V,E)$ be a graph and $c:E \rightarrow [\chi'(G)]$ be an edge coloring with chromatic index $\chi'(G)$. It is obvious that the preimage $c^{-1}(i),i\in [\chi'(G)]$ is a matching, but what can ...
2
votes
0answers
68 views

Adjacency in graphs: definition.

I have a little doubt about understanding the basic definiton. Adjacency in strong product of n graphs $G_1, G_2,.....,G_n$ for two distinct vertices $x = (x_1,x_2,...,x_n)$ and $y = ...
2
votes
1answer
42 views

A class of graphs

$\mathcal G_n $ conists of graphs $G$ on $n$ vertices $1,\ldots,n$ such that for all $i<j$, each vertex $k, i<k<j$ is not adjacent to at least one of $i$ and $j$. Question 1. Can we classify ...
3
votes
1answer
90 views

Computing with graphs in surfaces

I am currently working on a research project involving a polynomial defined for graphs in surfaces, similar to the Tutte polynomial, except with terms accounting for the embedding. At the moment, it ...
5
votes
3answers
95 views

Number of trees with a fixed edge

Consider a vertex set $[n]$. By Cayley's theorem there there are $n^{(n-2)}$ trees on $[n]$, but how can one count the following slightly modified version: What is the number of trees on $[n]$ ...
2
votes
1answer
261 views

maximum number of maximal cliques

I would like to know about upper bounds on the number of maximal cliques in graphs with small degrees. More precisely, how does the number of maximal cliques scale with graph size (i.e., number of ...
1
vote
1answer
65 views

graph combinatorics: how many graphs are there given k stable sets

Let $V_1,\dots, V_k$ be $k$ pairwise disjoint sets and set $V:=\cup_i V_i$. How many graphs $G=(V,E)$ are there such that $\vert e\cap V_i \vert \leq 1$ for all $i\in [k]$, i.e. the $V_i$ are stable ...
0
votes
0answers
65 views

Spectral moments of signless Laplacians through eigenvalues of the line graph?

For a simple graph G, the following relationships hold: $$RR^T=\Delta+A$$ and $$R^TR=2I+A_{L(G)}$$ where R is the incidence matrix, A is the adjacency matrix, I is the identity matrix, $A_{L(G)}$ is ...
0
votes
2answers
471 views

Number of optimal paths through a grid with an ordered path constraint

I found, but the awesome explanation of Arturo Magidin: Counting number of moves on a grid the number of paths for an MxN matrix. If I am thinking about this correctly (please say something if I am ...
-1
votes
2answers
55 views

Graph theory and combinatorics [closed]

Show that there is no graph $G$ with $V (G) = 12$ and $E(G) = 28$ in which each vertex is of degree either $3$ or $4$.
0
votes
1answer
50 views

Help understanding this connected graph equation

So in this equation: The number of connected labeled bipartite graphs with bipartition (X,Y) where |X|=m and |Y|=n is the coefficient of $x^my^n/m!\,n!$ in $$\log\biggl(\sum_{m,n=0}^\infty 2^{mn} ...
3
votes
3answers
88 views

Finding a planar graph satisfying these properties

I need to construct a 3-regular connected planar graph with a planar embedding where each face has degree 4 and 6. In addition, each vertex must be incident with exactly one face of degree 4. seems ...
3
votes
1answer
170 views

Why does every undirected graph have at least one cut of size $|E| / 2$?

In an undirected graph $G = (V, E)$, a global maximum cut in $G$ is a pair $(S, V - S)$ with the largest possible number of edges with one endpoint in $S$ and another endpoint in $V - S$ (this ...
1
vote
1answer
47 views

Is a graph with only one node a connected graph?

I need to know if a graph contain only a single node is considered a connected graph.
1
vote
1answer
157 views

Given average network diameter, how many nodes are three hops away.

The University of Milan found in 2011 that everyone on the Internet was, on average, 4.74 steps away from anyone else.. is that information sufficient to answer this question: What proportion of ...
6
votes
2answers
93 views

Number of connected labeled graphs (mod 2)

Let $c(n)$ denote the number of connected vertex labeled graphs on $n$ vertices. For example, $c(3) = 4$. The sequence begins $$ 1, 1, 4, 38, 728, 26704, \ldots $$ It is straightforward to ...
2
votes
1answer
289 views

Proving that a planar graph is bipartite [duplicate]

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. It is quite easy to prove the converse, but how to do ...
0
votes
1answer
118 views

what will be the maximum value of the given formula

$G$ is the product of $n$ graphs $G_i$, $1\leq i\leq n$. In particular its tensor product. $x = (x_1,x_2,...,x_n)$ and $y = (y_1,y_2,...,y_n)$ are two vertices of $G$. Distance between x and y is: ...
4
votes
1answer
472 views

Girth of undirected $k$- regular graph has number d of vertices more than $k^{2} + 1$

I have found this: Graph with girth 5 and exactly $k^2+1$ vertices The author however does not say how he proved the lemma (my title). Trying to work this out from (#3) here: ...
1
vote
0answers
133 views

Prove a general version of Euler's formula

For a planar embedding of a graph $G$ with $n$ vertices, $m$ edges, $s$ faces and $c$ components, prove that: $n-m+s=1+c$ I have no real clue as to how to prove this, can someone help me?
0
votes
1answer
91 views

Algorithm for finding set of all parents recursively

Suppose I have a directed graph $G=\{V,E\}$, with edges $E$ and vertices $V$. I am interested in subsets of vertices $A\subset V$ with the following properties: $\forall x\in A, Pa(x)\in A$ ...
4
votes
1answer
179 views

What's so special about a 2D plane in graph theory?

See, we can divide graphs into planar ones and non-planar ones. This seems to make a lot of sense until you find that this seems to only work in two dimensions. I can't think of any graph that cannot ...
0
votes
1answer
112 views

Tutte's Theorem for infinite graphs

Can Tutte's theorem be extended for infinite graphs? If so, what is the proof? The theorem: A graph G = (V, E) has a perfect matching if and only if for every subset U of V, the subgraph induced by ...
2
votes
1answer
393 views

Proving bipartition in a connected planar graph

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. Any hints/tips will be greatly appreciated.
0
votes
2answers
98 views

How can I prove this?

Let $G$ be a graph with edge weight $w$. Let $T^\ast$ be a minimum spanning tree, and let $e$ be an edge in $G$ but not in $T^\ast$. We know that $T^\ast + e$ contains exactly $1$ cycle $C$. Prove ...
0
votes
0answers
72 views

Counting cards, with a tree

I propose the following problem. Suppose you and I are playing a game of cards in which a winner is decided upon the cards we draw. This game of cards consist of colored cards: Yellow, red, ...
3
votes
2answers
182 views

To find maximum of the given formula

I am reading about graph operations. $G$ is the product of $n$ graphs $G_i$, $1\leq i\leq n$. In particular its strong product. $x = (x_1,x_2,...,x_n)$ and $y = (y_1,y_2,...,y_n)$ are two vertices of ...
4
votes
2answers
120 views

How to understand the automorphism group of a very symmetric graph (related to sylow intersections)

For a group $G$ and subgroup $H$, consider the relation on $G$ defined $x \sim y$ if $H^x \cap H^y = 1$. This defines a graph on $G$. It is always fairly symmetric: $N_G(H)$ acts on the left and $G$ ...
0
votes
2answers
154 views

Enumeration of labeled connected bipartite graphs given partite sets

What would be the closed-form expression defining number of all possible labelled connected bipartite graphs given $\mid X \mid = m, \mid Y \mid = n - m $?
2
votes
1answer
294 views

Decomposing a directed graph into disjoint cycles and paths.

Given a directed graph $G$ such that $\text{indeg}_{G}(x)$ and $\text{outdeg}_{G}(x)$ have the same parity for all $x \in V(G)$. Let $$X = \{x \in V(G) : \text{outdeg}(x) - \text{indeg}(x) > 0 \}$$ ...
1
vote
2answers
135 views

Counting the number of subgraphs isomorphic with the following digraph

Suppose $H$ is the following 4-vertex digraph : $$\langle V=\{a,b,c,d\}, E=\{ab,bd,ac,cd\}\rangle .$$ The digraph is drawn below: Can one help me to prove upper bound $n^4/55$ on the number of ...
1
vote
0answers
99 views

Subset of graph with minimum nodes minimum edges pointing out of the subset

Given a Directed Graph $G$ and a node $n$ in that graph I'd like to find a subgraph $S$ of $G$ with the following conditions: $n \in S$ $a * $ number of nodes in $S$ + $ b * $ number of edges going ...
0
votes
1answer
206 views

Induced sub graph

I am working on graph labeling problem. I want to know , Given two graphs G1 and G2, Is there any algorithm to check whether G1 is Induced subgraph of G2 ? Preferably polynomial time algorithm.
3
votes
0answers
81 views

Eigenvalues of weighted Laplacian

Let $L_{n \times n}$ be a Laplacian matrix of a directed graph, for example, $$ L = \begin{bmatrix} 2 & -1 & -1\\ 0 & 1 & -1\\ -1 & 0 &1 \end{bmatrix}. $$ Gersgorin disc ...
1
vote
1answer
354 views

Eulerian graph in two color

How can we prove the Eulerian Map can be color in 2 colors. I know the Eulerian graph can be colored at most 4, which is Four color problem. But I have no idea how to prove into 2 colors. Anyone can ...
1
vote
1answer
254 views

Perfect matching in a graph

Assuming I have a bipartite graph with the following property: for each subgroup of nodes $s \subseteq {V} $ : $$ \sum_{v\epsilon N(S),z\epsilon N(N(S)) }{} {(v,z) \geq 2\left \| S \right \|} $$ ...
2
votes
1answer
45 views

How many distinct copies of $P_m$ are in $K_n$?

Let $K_n$ be the complete graph of order $n$ and $P_m$ a path with $m$ distinct vertices, $1 \leq m \leq n$. Question: How many distinct copies of $P_m$ are contained in $K_n$? Given that a ...
1
vote
1answer
605 views

A cardinality of a graph

If I have graph $G=(V,E)\\$ What is the meaning of $|G|$? (The cardinality of G). I'd like to few words about it... Thank you!
2
votes
1answer
84 views

Prove that there exists walks that each edge is in $G$ [duplicate]

For some $k \in\mathbb{N}$, let $G$ be a connected graph with $2k$ odd-degree vertices, and any number of even-degree vertices. Prove that there exists $k$ walks such that each edge in $G$ is used in ...
3
votes
1answer
66 views

Prove that $T$ is a subgraph of $G$

Let $T$ be a tree with $k$ edges, and let $G$ be a graph where every vertex has degree at least $k$. Prove that $T$ is a subgraph of $G$. Can someone give me tips/help on how to solve this problem?
1
vote
2answers
41 views

Help with another graph theory question please

Let G be a graph with n vertices where every vertex has degree at least n/2. Prove that G is connected. (Note: Do not use the result on Hamilton cycles.)
2
votes
1answer
547 views

Proving the existence of a bridge in a tree

Let $G$ be a connected graph, and let $e \in E(G)$. Prove that $e$ is a bridge if and only if every spanning tree of $G$ contains $e$. Can someone help me with this please? Thank you!
1
vote
2answers
192 views

Draw Graph from distance to other nodes

I have a matrix that shows the distance from a node to another node: A B C D E A 0 2 4 3 1 B 2 0 2 1 3 C 4 2 0 2 1 D 3 1 2 0 2 E 1 3 1 2 0 To clearify: The 2 ...