Skip to main content
added 192 characters in body
Source Link
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

Let $e_6(n)$ be the greatest number of edges in a simple graph with $n$ vertices and girth at least 6. Let $G_6(n)$ be the set of simple graphs of order $n$ with girth at least 6 and $e_6(n)$ edges.

My question: Is there any $n$ for which none of the graphs in $G_6(n)$ is bipartite?

From computer experiments, I have found that the only values of $n\le 50$ for which $G_6(n)$ has any non-bipartite graphs at all are 7 (7 edges), 9 (10 edges), 15 (22 edges), 27 (53 edges), and 43 (106 edges). However, in all those cases $G_6(n)$ includes bipartite graphs as well.

A table (needs checking, please don't cite yet): "[n=44,e=108,g=12]" means $e_6(44)=108$ and there are 12 graphs. All the graphs are bipartite unless the notation is like "[n=15,e=22,g=2+1]" which means there are two bipartite graphs and one non-bipartite graph.

[n=5,e=4,g=3], [n=6,e=6,g=1], [n=7,e=7,g=1+1], [n=8,e=9,g=1], [n=9,e=10,g=3+1], [n=10,e=12,g=3], [n=11,e=14,g=1], [n=12,e=16,g=1], [n=13,e=18,g=1], [n=14,e=21,g=1], [n=15,e=22,g=2+1], [n=16,e=24,g=4], [n=17,e=26,g=4], [n=18,e=29,g=1], [n=19,e=31,g=1], [n=20,e=34,g=1], [n=21,e=36,g=3], [n=22,e=39,g=2], [n=23,e=42,g=1], [n=24,e=45,g=1], [n=25,e=48,g=1], [n=26,e=52,g=1], [n=27,e=53,g=2+2], [n=28,e=56,g=1], [n=29,e=58,g=1], [n=30,e=61,g=1], [n=31,e=64,g=1], [n=32,e=67,g=5], [n=33,e=70,g=3], [n=34,e=74,g=1], [n=35,e=77,g=1], [n=36,e=81,g=1], [n=37,e=84,g=3], [n=38,e=88,g=2], [n=39,e=92,g=1], [n=40,e=96,g=1], [n=41,e=100,g=1], [n=42,e=105,g=1], [n=43,e=106,g=2+3], [n=44,e=108,g=12], [n=45,e=110,g=183], [n=46,e=115,g=1], [n=47,e=118,g=1], [n=48,e=122,g=1], [n=47,e=118,g=1], [n=48,e=122,g=1], [n=49,e=126,g=1], [n=50,e=130,g=1].

Update Nov 2015: For $51\le n\le 63$, all extremal graphs are bipartite except for $n=63$, where there are 3 bipartite extremal graphs and 4 non-bipartite extremal graphs (187 edges).

Let $e_6(n)$ be the greatest number of edges in a simple graph with $n$ vertices and girth at least 6. Let $G_6(n)$ be the set of simple graphs of order $n$ with girth at least 6 and $e_6(n)$ edges.

My question: Is there any $n$ for which none of the graphs in $G_6(n)$ is bipartite?

From computer experiments, I have found that the only values of $n\le 50$ for which $G_6(n)$ has any non-bipartite graphs at all are 7 (7 edges), 9 (10 edges), 15 (22 edges), 27 (53 edges), and 43 (106 edges). However, in all those cases $G_6(n)$ includes bipartite graphs as well.

A table (needs checking, please don't cite yet): "[n=44,e=108,g=12]" means $e_6(44)=108$ and there are 12 graphs. All the graphs are bipartite unless the notation is like "[n=15,e=22,g=2+1]" which means there are two bipartite graphs and one non-bipartite graph.

[n=5,e=4,g=3], [n=6,e=6,g=1], [n=7,e=7,g=1+1], [n=8,e=9,g=1], [n=9,e=10,g=3+1], [n=10,e=12,g=3], [n=11,e=14,g=1], [n=12,e=16,g=1], [n=13,e=18,g=1], [n=14,e=21,g=1], [n=15,e=22,g=2+1], [n=16,e=24,g=4], [n=17,e=26,g=4], [n=18,e=29,g=1], [n=19,e=31,g=1], [n=20,e=34,g=1], [n=21,e=36,g=3], [n=22,e=39,g=2], [n=23,e=42,g=1], [n=24,e=45,g=1], [n=25,e=48,g=1], [n=26,e=52,g=1], [n=27,e=53,g=2+2], [n=28,e=56,g=1], [n=29,e=58,g=1], [n=30,e=61,g=1], [n=31,e=64,g=1], [n=32,e=67,g=5], [n=33,e=70,g=3], [n=34,e=74,g=1], [n=35,e=77,g=1], [n=36,e=81,g=1], [n=37,e=84,g=3], [n=38,e=88,g=2], [n=39,e=92,g=1], [n=40,e=96,g=1], [n=41,e=100,g=1], [n=42,e=105,g=1], [n=43,e=106,g=2+3], [n=44,e=108,g=12], [n=45,e=110,g=183], [n=46,e=115,g=1], [n=47,e=118,g=1], [n=48,e=122,g=1], [n=47,e=118,g=1], [n=48,e=122,g=1], [n=49,e=126,g=1], [n=50,e=130,g=1].

Let $e_6(n)$ be the greatest number of edges in a simple graph with $n$ vertices and girth at least 6. Let $G_6(n)$ be the set of simple graphs of order $n$ with girth at least 6 and $e_6(n)$ edges.

My question: Is there any $n$ for which none of the graphs in $G_6(n)$ is bipartite?

From computer experiments, I have found that the only values of $n\le 50$ for which $G_6(n)$ has any non-bipartite graphs at all are 7 (7 edges), 9 (10 edges), 15 (22 edges), 27 (53 edges), and 43 (106 edges). However, in all those cases $G_6(n)$ includes bipartite graphs as well.

A table (needs checking, please don't cite yet): "[n=44,e=108,g=12]" means $e_6(44)=108$ and there are 12 graphs. All the graphs are bipartite unless the notation is like "[n=15,e=22,g=2+1]" which means there are two bipartite graphs and one non-bipartite graph.

[n=5,e=4,g=3], [n=6,e=6,g=1], [n=7,e=7,g=1+1], [n=8,e=9,g=1], [n=9,e=10,g=3+1], [n=10,e=12,g=3], [n=11,e=14,g=1], [n=12,e=16,g=1], [n=13,e=18,g=1], [n=14,e=21,g=1], [n=15,e=22,g=2+1], [n=16,e=24,g=4], [n=17,e=26,g=4], [n=18,e=29,g=1], [n=19,e=31,g=1], [n=20,e=34,g=1], [n=21,e=36,g=3], [n=22,e=39,g=2], [n=23,e=42,g=1], [n=24,e=45,g=1], [n=25,e=48,g=1], [n=26,e=52,g=1], [n=27,e=53,g=2+2], [n=28,e=56,g=1], [n=29,e=58,g=1], [n=30,e=61,g=1], [n=31,e=64,g=1], [n=32,e=67,g=5], [n=33,e=70,g=3], [n=34,e=74,g=1], [n=35,e=77,g=1], [n=36,e=81,g=1], [n=37,e=84,g=3], [n=38,e=88,g=2], [n=39,e=92,g=1], [n=40,e=96,g=1], [n=41,e=100,g=1], [n=42,e=105,g=1], [n=43,e=106,g=2+3], [n=44,e=108,g=12], [n=45,e=110,g=183], [n=46,e=115,g=1], [n=47,e=118,g=1], [n=48,e=122,g=1], [n=47,e=118,g=1], [n=48,e=122,g=1], [n=49,e=126,g=1], [n=50,e=130,g=1].

Update Nov 2015: For $51\le n\le 63$, all extremal graphs are bipartite except for $n=63$, where there are 3 bipartite extremal graphs and 4 non-bipartite extremal graphs (187 edges).

add a table
Source Link
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

Let $e_6(n)$ be the greatest number of edges in a simple graph with $n$ vertices and girth at least 6. Let $G_6(n)$ be the set of simple graphs of order $n$ with girth at least 6 and $e_6(n)$ edges.

My question: Is there any $n$ for which none of the graphs in $G_6(n)$ is bipartite?

From computer experiments, I have found that the only values of $n\le 47$$n\le 50$ for which $G_6(n)$ has any non-bipartite graphs at all are 7 (7 edges), 9 (10 edges), 15 (22 edges), 27 (53 edges), and 43 (106 edges). However, in all those cases $G_6(n)$ includes bipartite graphs as well.

A table (needs checking, please don't cite yet): "[n=44,e=108,g=12]" means $e_6(44)=108$ and there are 12 graphs. All the graphs are bipartite unless the notation is like "[n=15,e=22,g=2+1]" which means there are two bipartite graphs and one non-bipartite graph.

[n=5,e=4,g=3], [n=6,e=6,g=1], [n=7,e=7,g=1+1], [n=8,e=9,g=1], [n=9,e=10,g=3+1], [n=10,e=12,g=3], [n=11,e=14,g=1], [n=12,e=16,g=1], [n=13,e=18,g=1], [n=14,e=21,g=1], [n=15,e=22,g=2+1], [n=16,e=24,g=4], [n=17,e=26,g=4], [n=18,e=29,g=1], [n=19,e=31,g=1], [n=20,e=34,g=1], [n=21,e=36,g=3], [n=22,e=39,g=2], [n=23,e=42,g=1], [n=24,e=45,g=1], [n=25,e=48,g=1], [n=26,e=52,g=1], [n=27,e=53,g=2+2], [n=28,e=56,g=1], [n=29,e=58,g=1], [n=30,e=61,g=1], [n=31,e=64,g=1], [n=32,e=67,g=5], [n=33,e=70,g=3], [n=34,e=74,g=1], [n=35,e=77,g=1], [n=36,e=81,g=1], [n=37,e=84,g=3], [n=38,e=88,g=2], [n=39,e=92,g=1], [n=40,e=96,g=1], [n=41,e=100,g=1], [n=42,e=105,g=1], [n=43,e=106,g=2+3], [n=44,e=108,g=12], [n=45,e=110,g=183], [n=46,e=115,g=1], [n=47,e=118,g=1], [n=48,e=122,g=1], [n=47,e=118,g=1], [n=48,e=122,g=1], [n=49,e=126,g=1], [n=50,e=130,g=1].

Let $e_6(n)$ be the greatest number of edges in a simple graph with $n$ vertices and girth at least 6. Let $G_6(n)$ be the set of simple graphs of order $n$ with girth at least 6 and $e_6(n)$ edges.

My question: Is there any $n$ for which none of the graphs in $G_6(n)$ is bipartite?

From computer experiments, I have found that the only values of $n\le 47$ for which $G_6(n)$ has any non-bipartite graphs at all are 7 (7 edges), 9 (10 edges), 15 (22 edges), 27 (53 edges), and 43 (106 edges). However, in all those cases $G_6(n)$ includes bipartite graphs as well.

Let $e_6(n)$ be the greatest number of edges in a simple graph with $n$ vertices and girth at least 6. Let $G_6(n)$ be the set of simple graphs of order $n$ with girth at least 6 and $e_6(n)$ edges.

My question: Is there any $n$ for which none of the graphs in $G_6(n)$ is bipartite?

From computer experiments, I have found that the only values of $n\le 50$ for which $G_6(n)$ has any non-bipartite graphs at all are 7 (7 edges), 9 (10 edges), 15 (22 edges), 27 (53 edges), and 43 (106 edges). However, in all those cases $G_6(n)$ includes bipartite graphs as well.

A table (needs checking, please don't cite yet): "[n=44,e=108,g=12]" means $e_6(44)=108$ and there are 12 graphs. All the graphs are bipartite unless the notation is like "[n=15,e=22,g=2+1]" which means there are two bipartite graphs and one non-bipartite graph.

[n=5,e=4,g=3], [n=6,e=6,g=1], [n=7,e=7,g=1+1], [n=8,e=9,g=1], [n=9,e=10,g=3+1], [n=10,e=12,g=3], [n=11,e=14,g=1], [n=12,e=16,g=1], [n=13,e=18,g=1], [n=14,e=21,g=1], [n=15,e=22,g=2+1], [n=16,e=24,g=4], [n=17,e=26,g=4], [n=18,e=29,g=1], [n=19,e=31,g=1], [n=20,e=34,g=1], [n=21,e=36,g=3], [n=22,e=39,g=2], [n=23,e=42,g=1], [n=24,e=45,g=1], [n=25,e=48,g=1], [n=26,e=52,g=1], [n=27,e=53,g=2+2], [n=28,e=56,g=1], [n=29,e=58,g=1], [n=30,e=61,g=1], [n=31,e=64,g=1], [n=32,e=67,g=5], [n=33,e=70,g=3], [n=34,e=74,g=1], [n=35,e=77,g=1], [n=36,e=81,g=1], [n=37,e=84,g=3], [n=38,e=88,g=2], [n=39,e=92,g=1], [n=40,e=96,g=1], [n=41,e=100,g=1], [n=42,e=105,g=1], [n=43,e=106,g=2+3], [n=44,e=108,g=12], [n=45,e=110,g=183], [n=46,e=115,g=1], [n=47,e=118,g=1], [n=48,e=122,g=1], [n=47,e=118,g=1], [n=48,e=122,g=1], [n=49,e=126,g=1], [n=50,e=130,g=1].

small update
Source Link
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

Let $e_6(n)$ be the greatest number of edges in a simple graph with $n$ vertices and girth at least 6. Let $G_6(n)$ be the set of simple graphs of order $n$ with girth at least 6 and $e_6(n)$ edges.

My question: Is there any $n$ for which none of the graphs in $G_6(n)$ is bipartite?

From computer experiments, I have found that the only values of $n\le 44$$n\le 47$ for which $G_6(n)$ has any non-bipartite graphs at all are 7 (7 edges), 9 (10 edges), 15 (22 edges), 27 (53 edges), and 43 (106 edges). However, in all those cases $G_6(n)$ includes bipartite graphs as well.

Let $e_6(n)$ be the greatest number of edges in a simple graph with $n$ vertices and girth at least 6. Let $G_6(n)$ be the set of simple graphs of order $n$ with girth at least 6 and $e_6(n)$ edges.

My question: Is there any $n$ for which none of the graphs in $G_6(n)$ is bipartite?

From computer experiments, I have found that the only values of $n\le 44$ for which $G_6(n)$ has any non-bipartite graphs at all are 7 (7 edges), 9 (10 edges), 15 (22 edges), 27 (53 edges), and 43 (106 edges). However, in all those cases $G_6(n)$ includes bipartite graphs as well.

Let $e_6(n)$ be the greatest number of edges in a simple graph with $n$ vertices and girth at least 6. Let $G_6(n)$ be the set of simple graphs of order $n$ with girth at least 6 and $e_6(n)$ edges.

My question: Is there any $n$ for which none of the graphs in $G_6(n)$ is bipartite?

From computer experiments, I have found that the only values of $n\le 47$ for which $G_6(n)$ has any non-bipartite graphs at all are 7 (7 edges), 9 (10 edges), 15 (22 edges), 27 (53 edges), and 43 (106 edges). However, in all those cases $G_6(n)$ includes bipartite graphs as well.

Source Link
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147
Loading